Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Sudoku Generator

by turo (Friar)
on Dec 13, 2005 at 03:27 UTC ( [id://516224]=sourcecode: print w/replies, xml ) Need Help??
Category: Fun Stuff
Author/Contact Info Arturo Escudero Z. <darkturo@gmail.com>
Description: This program generates a random Sudoku table, and prints it out to the screen so you can copy it to the paper and try to solve it. It has different levels of difficulty, and is, in general terms, a funny program (or should i call it 'a funny hack'?).
Maybe future versions (if any) will have sudoku generator, sudoku solver, and a nice sudoky curses game? hahaha ... I invite perlmonks users to play with it and, of course, to modify it ;)
Happy Sudoking!
turo

PS: The difficulty implementation is no so well balanced :'( ... some times it generates a multiple solutions sudokus ... this is really annoying!		 
#!/usr/bin/perl 
# sudoku
#       A text-based sudoku game generator written in perl.
# Copyright (C) 2005  Arturo Escudero
# 
# This program is free software; you can redistribute it and/or
# modify it under the terms of the GNU General Public License
# as published by the Free Software Foundation; either version 2
# of the License, or (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU General Public License for more details.
#
use List::Util qw(shuffle reduce sum);
use threads;
use Thread::Queue;
use POSIX;
use Time::HiRes qw( usleep gettimeofday tv_interval );

###
my $MAX_RETRIES = 50;
my $queue = new Thread::Queue;
my $level = 0; #there are three levels: novice(0),medium(1),expert(2)
my $seed  = 0;
my $print_solution = 0;
my $no_print_sdk = 0;
my $verbose = 0;
$| = 1;

### Main Program
parseArgs($#ARGV + 1, @ARGV);

$seed = time if ( not $seed ); #simple seed
srand($seed);

my $t1 = [gettimeofday()];
my @sudoku = generateSudokuTable();
printSudokuSol(@sudoku) if ( $print_solution or $no_print_sdk );
if ( not $no_print_sdk ) {
        print "\n" if ( $print_solution );
        printSudoku(@sudoku)
}
print "\nElapsed time: ", tv_interval($t1), " secs\n";
print "Turo 2005\n";

### Subroutines!
sub whichCell9x9 {
        return ((9 * $_[0]) + $_[1]);
}

sub generateSudokuTable {
        my @sdk = (0)x81;
        my ($number, $retries);

        my $thr = threads->create("progressDots","");
        $SIG{ALRM} = sub {} ;
        for (my $i = 0; $i < 9; $i++ ) {
                for (my $j = 0; $j < 9; $j++ ) {
                        $number = chooseNumber($i,$j,@sdk);
                        if ( $number ) {
                                $sdk[whichCell9x9($i,$j)] = $number;
                        } else {
                                $j = 0;
                                $retries ++;
                                if ( $retries > $MAX_RETRIES ) {
                                        $j=9; $i = -1; $retries = 0;
                                        @sdk = (); @sdk = (0)x81;
                                }
                        }
                }
        }
        $queue->enqueue("token");
        kill SIGALRM, getpid();
        $thr->join();
        return @sdk;
}

sub chooseNumber {
        my ( $i, $j, @sdk ) = @_;
        my ($element, %yetChoosed);


        $element = int(rand(9) + 1);
        $yetChoosed{$element} = $element;
        while ( not ( checkRow($i, $j, $element, @sdk)
                and   checkColumn($i, $j, $element, @sdk)
                and   checkSubSquare($i, $j, $element, @sdk ) ) )  {
                $element = int(rand(9) + 1);
                while ( exists $yetChoosed{$element} ) {
                        $element = ($element % 9) + 1; #next?
                        return undef if ( 45 == sum keys %yetChoosed )
                }
                $yetChoosed{$element} = $element;
        }
        return $element;
}

sub checkRow {
        my ($i, $j, $element, @sdk) = @_;

        for ( my $k = 0; $k < $j; $k++ ) {
                return 0 if ( $sdk[whichCell9x9($i, $k)] == $element )
+;
        }
        return 1;
}

sub checkColumn {
        my ($i, $j, $element, @sdk) = @_;

        for ( my $k = 0; $k < $i; $k++ ) {
                return 0 if ( $sdk[whichCell9x9($k, $j)] == $element )
+;
        }
        return 1;
}

sub checkSubSquare {
        my ($i, $j, $element, @sdk) = @_;
        my ($sum, $pivot_element, $num_elements);

        # We decide in which square we are
        my $row_i = (($i < 3)? 0 : (($i >= 3  and $i < 6)? 1 : 2)) * 3
+;
        my $column_j = (($j < 3)? 0 : (($j >= 3  and $j < 6)? 1 : 2)) 
+* 3;


        $sum = $pivot_element = $num_elements = 0;
        my @list = (0)x9;
        for ( my $k = $row_i; $k < ($row_i + 3); $k++ ) {
                for ( my $l = $column_j; $l < ($column_j + 3); $l++ ) 
+{
                        $pivot_element = ( $i == $k and $j == $l )?
                                                $element :
                                                $sdk[whichCell9x9($k,$
+l)];
                        if ( $pivot_element != 0 ) {
                                $list[$pivot_element] +=
                                        (($list[$pivot_element])? 45: 
+1);
                                $num_elements++;
                        }
                }
        }

        $sum = sum @list;
        return ($sum == $num_elements);
}

sub printSudokuSol {
        my @sdk = @_;
        for (my $i = 0; $i < 9; $i++ ) {
                for (my $j = 0; $j < 9; $j++ ) {
                        printf "%3d%s", $sdk[whichCell9x9($i,$j)],
                                        (( $j == 2 or $j == 5 )? "  |"
+ : "");
                }
                printf "\n%s", (($i == 2 or $i == 5)? "-"x35 . "\n" : 
+"");
        }
}

sub printSudoku {
        my @sdk = @_;
        my ($n, $levelElements);
        local $counter;
        my $sum_row, @sum_cols, @frequencies;

        @q = (0)x9;
        $counter = $levelElements = howMany4Level($level);
        for (my $i = 0; $i < 9; $i++ ) {
                $sum_row = 0;
                for (my $j = 0; $j < 9; $j++ ) {
                        $n = $sdk[whichCell9x9($i,$j)];
                        if ( mayIPrint( $i,
                                        $j,
                                        $levelElements,
                                        \@q,
                                        $frequencies[$n] + 1) ) {
                                if ( $verbose ) {
                                        $sum_row += $n;
                                        $sum_cols[$j] += $n;
                                }
                                $frequencies[$n] ++;
                                printf "%3d%s", $n,
                                        (($j == 2 or $j == 5 )? "  |" 
+: "");
                        } else {
                                printf "   %s",
                                        (($j == 2 or $j == 5 )? "  |" 
+: "");
                        }
                }
                print "  = $sum_row" if ( $verbose );
                printf "\n%s", (($i == 2 or $i == 5)? "-"x35 . "\n" : 
+"");
        }
        if ( $verbose ) {
                for (my $i = 0; $i < 9; $i++ ) {
                        printf " ||%s", (($i == 2 or $i == 5 )? "   " 
+: "");
                }
                print "\n";
                for (my $i = 0; $i < 9; $i++ ) {
                        printf "%3d%s",
                                $sum_cols[$i],
                                (($i == 2 or $i == 5 )? "   " : "");
                }
                print "\n\nFrequencies:\n";
                for (my $i = 1; $i <= 9; $i++ ) {
                        print "\t\tnum($i) = ", $frequencies[$i], "\n"
+;
                }
        }
}

sub howMany4Level {
        if ( $_[0] == 0 ) {
                #novice
                return (45 + int(rand(10)));
        } elsif ( $_[0] == 1 ) {
                #medium
                return (36 + int(rand(7)));
        } elsif ( $_[0] == 2 ) {
                #advanced
                return (27 + int(rand(4)));
        }
}

sub mayIPrint {
        # this is a little tricky; i've defined $counter as a global v
+ar.
        my ($i, $j, $levelElements, $quadList, $freq) = @_;

        my $quad = (($i < 3)? 0 : (($i >= 3  and $i < 6)? 3 : 6)) +
                   (($j < 3)? 0 : (($j >= 3  and $j < 6)? 1 : 2));

        if ($counter > 0) {
                if ( $quadList->[$quad] <= (int($levelElements/9)) ) {
                        if ( int(rand(100)+1) > 50 ) {
                                if ( $freq <= int(rand(2) + 3)) {
                                        $counter--;
                                        $quadList->[$quad] ++;
                                        return 1;
                                }
                        }
                }
        }
        return 0;
}

sub progressDots {
        print "Generating (seed: $seed) ";
        while ( not ($queue->dequeue_nb())) {
                print ".";
                usleep (50000);
        }
        print " [Done]\n\nSudoku!\n"
}

sub parseArgs {
        my ($argc, @argv) = @_;
        my $need_help = 0;

#       usage () if ( $argc == 0 );

        for (my $i = 0; $i < $argc; $i++) {
                if ( @argv[$i] eq '-level' ) {
                        my $lvl = @argv[++$i];
                        for ( $lvl ) {
                                if (/novice/) {
                                        $level = 0;
                                } elsif (/normal/) {
                                        $level = 1;
                                } elsif (/master/) {
                                        $level = 2;
                                } else {
                                        print "Bad level: '$lvl'!\n";
                                        usage();
                                }
                        }
                } elsif ( @argv[$i] eq '-seed' ) {
                        $seed = @argv[++$i];
                } elsif ( @argv[$i] =~ /^-solution$|^-s$/ ) {
                        $print_solution = 1;
                } elsif ( @argv[$i] =~ /^-solution-only$|^-so$/ ) {
                        $no_print_sdk = 1;
                } elsif ( @argv[$i] =~ /^-verbose$|^-v$/ ) {
                        $verbose = 1;
                } elsif ( @argv[$i] =~ /^--help$|^-help$|^-h$/ ) {
                        $need_help = 1;
                } else {
                        print "Bad parameter: '", @argv[$i], "'\n";
                        $need_help = 1;
                }
        }
        usage() if ( $need_help );
}

sub usage {
        print <<EOF ;
usage: sudoku [-level (novice|normal|master)] [-seed seed_num] [-solut
+ion]
        -level lvl
                Specifies the game level (default is novice).
        -seed sn
                To generate the sudoku's tables, we must take random n
+umbers.
                By controlling this seed you can regenerate the same s
+udoku 
                table, and demand its solution.
        -s
        -solution
                Prints out the solution of a speficied sudoku (you mus
+t use 
                the seed). If you don't use the seed param, then the p
+rogram
                will generate a new sudoku and it will print its solut
+ion. 
        
        -so
        -solution-only
                Like the above, but it only prints the solution.
        -v
        -verbose
                Verbose output.
        --help
                Prints this helpfully screen :-P

turo 2005
EOF
        exit 0;
}
Replies are listed 'Best First'.
Re: Sudoku Generator
by planetscape (Chancellor) on Dec 13, 2005 at 11:15 UTC
[reply]
      Ohhh daemons!!! i forgot to use the perlmonks' supersearch before submitting my modest sudoku-perl generator :'( ...
      Solve Sudokus are a trendy vice! thanks for the link to the SadMan Sudoku, it has a list of interesting ''techniques''

      I can bet that in future there were more sudoku-perl on the perlmonks code-pool :-) ...

      Best regards

      perl -Te 'print map { chr((ord)-((10,20,2,7)$i++)) } split //,"turo"'
[reply]
      Howdy!

      Sudoku Susser has become my tool of choice...and it's free.

      yours,
      Michael
[reply]

        Ooh... thanks!

        planetscape
[reply]
Re: Sudoku Generator
by Anonymous Monk on Dec 15, 2005 at 16:02 UTC
    You don't check for neighbours. In every sudoku are at least four cells that are 2 in the same subsquare each neighbour to the other (or with a gap between, which is neighbouring over the edge) which are repeated with the same 2 values and neighbouring in another subsquare. One of these 4 cells has to be printed, otherwise there would be 2 solutions.
[reply]

      Interesting, i'm going to include this later :-)

      a lot of thanks

      regards

      turo

      perl -Te 'print map { chr((ord)-((10,20,2,7)[$i++])) } split //,"turo"'
[reply]
[d/l]

Back to Code Catacombs

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: sourcecode [id://516224]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? • Last hour • Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (1)
As of 2024-04-25 00:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found