#! /usr/bin/perl
#
#   psudoku-solver.pl
#   Created by Murphy Stein, May 2006
#
#   This program creates and solves 9x9 sudoku puzzles

#	PSUDOKU-SOLVER
#	Begin
#		Read in board
#		Convert 0's to 123456789
#		Recurse(0,0);
#	End

#	Recurse(row,col):
#		assume board is valid
#		check cell's row, column, and block
#		If there is duplicate
#			return false (board is invalid)
#		Else If cell is bottomright-most [8,8]
#			return true (board is solved)
#		Else
#			If length([row,col]) == 1 then
#				if cell value has dupes in row, column, or block
#					return false
#				end if
#				move to next cell (top->bottom, left->right)
#				set "old" = value at [row,col]
#				Recurse(row,col)
#			Else
#				set "old" = value at [row,col]
#				Change cell value to first char at [row,col]
#				If Recurse returns false remove first char from "old"
#				set [row,col] value to "old"
#				Recurse(row,col);
#		End if
#	End Recurse
#
#
#
###################################################

use POSIX;

print "\n++++++++++++++++++++++++++++++++++++++++++++++\n";
print "Welcome to seduko-solver\n";
print "Reading in board from command-line...\n\n";

$debug_flag = false;
$board[9][9];
$board_copy[9][9];
$input_file = $ARGV[0];

open(hFILE, $input_file) || die ("Can't open specified file!\n");

$row = 0;
$i = 0;
foreach $line (<hFILE>) {
    $line =~ s/(\n|\r)//;
    @values = split(/,/, $line);
    if (scalar(@values) > 9) {
        print "Alert, misformatted file... Too many columns!";
        exit(0);
    }

    for ($i = 0; $i < scalar(@values); $i++) {
        $board[$row][$i] = $values[$i];
        $board_copy[$row][$i] = $values[$i];
    }
    $row++;
    if ($row > 9) {
        print "Alert, misformatted file... Too many rows!";
        exit(0);
    }
}
close(hFILE);

SetupBoard();
$recursions = 0;
if (SolveBoard(0,0) eq true)
{
	print "\n$recursions recursions later, the completed board is as follows...\n";
	PrintBoard();
} else {
	print "\n-----This board has no solution------\n";
}
print "\n++++++++++++++++++++++++++++++++++++++++++++++\n\n";

sub SetupBoard()
{
    #fill-up blanks with placeholders
    $symbol_string="123456789";
    for ($r = 0; $r <= 8; $r++) {
        for ($c = 0; $c <= 8; $c++) {
            if ($board[$r][$c] == "0") {
                $board[$r][$c] = $symbol_string;
            }
        }
    }
}

sub SolveBoard()
{
	my $id = $recursions;
	if (($recursions++ % 5000) == 0) {
		print "   ";
		print $recursions - 1 . " recursion(s) so far\n";
		PrintBoard();
	}
	my ($row, $col) = ($_[0], $_[1]);

	debug("**Entering SolveBoard() loop #$id at cell $row,$col\n");
	if ($debug_flag eq true) { PrintBoard(); }
	if ($col > 8) {
		return true;
	}
	if ($row > 8) {
		die ("Can't be at row position > 8.  row is currently $row\n");
	}
	
	my $keep = ValueAt($row,$col);
	if (HasNoDoubt($keep)) {        
		debug("Cell is already filled in.\n");

        if (CellIsValid($row,$col) eq true) {
        #board is still valid, recurse from next position
			if ($row == 8) {
				debug("row is $row, col is $col, jumping to next column...\n");
				$col++;
				$row = 0;
			} else {
				$row++;
			}			
			if (SolveBoard($row, $col) eq true) {
				debug("--Exiting SolveBoard() #$id with true\n");
				return true;
			} else {
				debug("--Exiting SolveBoard() #$id with false\n");
				return false;
			}
		} else {
			debug("--Uh-Oh, input board must have been invalid\n");
			return false;
		}
        
     } else {
		debug("Cell needs to be filled in... ");   
     	# cell has doubt, recurse through all options
	  	for (my $k = 1; $k <= 9; $k++) {
	  		debug("Trying $k at $row, $col...\n");
	  		$board[$row][$col] = $k;

			if (CellIsValid($row,$col) eq true) {
				debug("It's not a dupe.  Recursing...\n");
				if (SolveBoard($row, $col) eq true) {
					debug("--Exiting SolveBoard() #$id with true\n");
					return true;
				}
			} else {
				debug("Oops, it's a dupe.\n");
			}
		}
		debug("Dead-end, restoring original contents of cell to...$keep\n");
		$board[$row][$col] = $keep;
		debug("--Exiting SolveBoard() #$id with false\n");
		return false;
     }
}

sub PrintBoard()
{
    my ($r, $c);
    print "  -------------------------------------------------\n";
    for ($r = 0; $r <= 8; $r++) {
    	for ($c = 0; $c <= 8; $c++) {
        	$s = $board[$r][$c];
        	if (($c % 3) == 0) {
        		print "  |  ";
        	} else {	
        		print "    ";
        	}
            HasNoDoubt($s) ? print $s : print " ";
         }
         print "  |\n";
         if ((($r + 1) % 3) == 0) {
         	print "  -------------------------------------------------\n";
         }
     }
}

sub CellIsValid()
{
	my ($row, $col) = ($_[0],$_[1]);
	my ($i, $j);
	debug("Checking cell at $row,$col\n");
	debug("Checking column...");
	for ($i = 0; $i < 9; $i++) {
		if ($i != $row) {
			if (ValueAt($i,$col) eq ValueAt($row,$col)) {
				debug("There is a dupe\n");
				return false;
			}
		}
	}
	debug("OK\n");
	debug("Checking row...");
	for ($i = 0; $i < 9; $i++) {
		if ($i != $col) {
			if (ValueAt($row,$i) eq ValueAt($row,$col)) {
				debug("There is a dupe\n");					
				return false;
			}
		}
	}
	debug("OK\n");
	debug("Checking block...");
	my ($top, $left);
	$top = (floor($row/3) * 3);
	$left = (floor($col/3) * 3);
	for ($i = $top; $i <= $top + 2; $i++) {
		for ($j = $left; $j <= $left + 2; $j++) {
			if (($i != $row) && ($j != $col)) {
				if (ValueAt($i,$j) eq ValueAt($row,$col)) {
					debug("There is a dupe\n");					
					return false;
				}
			}
		}
	}
	debug("OK\n");
	return true;
}

sub HasNoDoubt()
{
    return (!(HasDoubt($_[0])));
}

sub HasDoubt()
{
    return (length($_[0]) > 1);
}

sub ValueAt()
{
    return $board[$_[0]][$_[1]];
}

sub debug()
{
	if ($debug_flag eq true) {
		$m = $_[0];
		print "$m";
	}
}