#!/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 var.
        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] [-solution]
        -level lvl
                Specifies the game level (default is novice).
        -seed sn
                To generate the sudoku's tables, we must take random numbers.
                By controlling this seed you can regenerate the same sudoku 
                table, and demand its solution.
        -s
        -solution
                Prints out the solution of a speficied sudoku (you must use 
                the seed). If you don't use the seed param, then the program
                will generate a new sudoku and it will print its solution. 
        
        -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;
}