use Tk;
use Tk::Table;

use strict;
use warnings;

my $mw = MainWindow->new;
my $table = $mw->Table(-rows => 9, -columns => 9, -fixedrows => 9, fixedcolumns => 9)->pack;
foreach my $row (0 .. 8) {
    foreach my $col (0 .. 8) {
	    if ((int($row/3) + int($col/3)) % 2) {
			$table->put($row, $col, $mw->Entry(-width => 1, -font=>"Adobe 30 bold", -background => "grey"));
		} else {
			$table->put($row, $col, $mw->Entry(-width => 1, -font=>"Adobe 30 bold", -background => "white"));
		}
	}
}
$mw->Button(-text => "Think", -command => \&think)->pack();


MainLoop;


sub think {
	my $board;
	foreach my $row (0 .. 8) {
		foreach my $col (0 .. 8) {
			$board->[$row][$col] = $table->get($row, $col)->get();
			$board->[$row][$col] = undef if (!($board->[$row][$col]));
		}
	}
	try($board);
}

sub try {
    my $board = shift;
    my ($x, $y, @options) = find_blank_with_least_options($board);
    if (defined($x)) {
        for (@options) {
            $board->[$x][$y] = $_;
            try($board);
        }
        $board->[$x][$y] = undef;
    } else {
        print "find solution:\n";
        display($board);
    }
}

sub find_blank_with_least_options {
    my $board = shift;
    my ($x_to_return, $y_to_return, @options_to_return);
    my $least = 9;
    for my $x (0 .. 8) {
        for my $y (0 .. 8) {
            if (!defined($board->[$x][$y])) {
                my @options = (0,1,1,1,1,1,1,1,1,1);
                for (0 .. 8) {
                    $options[$board->[$x][$_]] = 0 if defined($board->[$x][$_]);
                    $options[$board->[$_][$y]] = 0 if defined($board->[$_][$y]);
                }
                for my $i (int($x/3) * 3 .. int($x/3) * 3 + 2) {
                    for my $j (int($y/3) * 3 .. int($y/3) * 3 + 2) {
                        $options[$board->[$i][$j]] = 0 if defined($board->[$i][$j]);
                    }
                }
                my $sum;
                $sum += $options[$_] for (0 .. 9);
                if ($sum < $least) {
                    $x_to_return = $x;
                    $y_to_return = $y;
                    $least = $sum;
                    $#options_to_return = -1;
                    for (1 .. 9) {
                        push @options_to_return, $_ if ($options[$_]);
                    }
                }
            }
        }
    }
    return ($x_to_return, $y_to_return, @options_to_return);
}

sub display {
    my $board = shift;
    for my $row (0 .. 8) {
        for my $col (0 .. 8) {
			if (!$table->get($row, $col)->get()) {
				$table->get($row, $col)->configure(-foreground => "red");
				$table->get($row, $col)->insert('@0', $board->[$row][$col]);
			}
		}
    }
}