#!/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;
}
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.