sudoku_solver.php

<?php
/**
 * Sudoku Solver
 * 
 * Usage: php sudoku_solver.php challenge.txt
 * Sample contents of challenge.txt:
 * 097600000
 * 861000000
 * 000080000
 * 030000001
 * 004500700
 * 000060805
 * 080090004
 * 400005000
 * 009801006
 * 
 * @author Gabriel U. <[email protected]>
 * @copyright Copyright (c) 2010, Gabriel U.
 */

error_reporting(E_ALL);
set_time_limit(0);

/**
 * Print grid in a user friendly way
 * 
 * @param $grid {array}
 * @param $plain {optional boolean} Default: TRUE. Display pretty table?
 * @return void
 */
function printGrid($grid, $plain = TRUE)
{
	if (!$plain) echo "---------------------\n";
	for ($i=0, $leni=count($grid); $i<$leni; $i++) {
		if (!$plain) echo "| ";
		for ($j=0, $lenj=count($grid[$i]); $j<$lenj; $j++) {
			if ($j > 0 && !$plain)
				echo " ";
			if (count($grid[$i][$j]) > 1 || count($grid[$i][$j]) == 0) {
				if ($plain) echo '0'; else echo ' ';
			} else {
				echo implode('', $grid[$i][$j]);
			}
		}
		if (!$plain) echo " |";
		echo "\n";
		if ($i < $leni - 1 && !$plain)
			echo "---------------------\n";
	}
	if (!$plain) echo "---------------------\n";
}

/**
 * Print grid possibilities in a user friendly way
 * 
 * @param $grid {array}
 * @return void
 */
function printPossibilities($grid)
{
	for ($i=0, $leni=count($grid); $i<$leni; $i++) {
		for ($j=0, $lenj=count($grid[$i]); $j<$lenj; $j++) {
			if ($j > 0) echo ' ';
			echo str_pad(implode('', $grid[$i][$j]), 9, ' ');
		}
		echo "\n";
	}
}

/**
 * Clean rows
 * 
 * Remove numbers from cells of possibilities using challenge numbers
 *
 * @param $grid {array}
 * @return {boolean} If a change was made/found
 */
function cleanRows(&$grid)
{
	$cell_changed = FALSE;
	
	for ($i=0, $leni=count($grid); $i<$leni; $i++) { // loop through each row
		for ($j=0, $lenj=count($grid[$i]); $j<$lenj; $j++) { // loop through each column
			$num = '';
			
			// find single value column within row
			if (count($grid[$i][$j]) == 1) {
				// we have a single value on cell
				$num = implode('', $grid[$i][$j]);
			}
			
			// remove found value from all columns in row
			if ($num != '') {
				for ($j2=0; $j2<$lenj; $j2++) {
					// skip the current column we're on when clearing
					if ($j == $j2) continue;
					if (in_array($num, $grid[$i][$j2]) && count($grid[$i][$j2]) > 1) {
						unset($grid[$i][$j2][$num]);
						$cell_changed = TRUE;
					}
				}
			}
		}
	
	}
	
	return $cell_changed;
}

/**
 * Clean columns
 * Remove numbers from cells of possibilities using challenge numbers
 * 
 * @param $grid {array}
 * @return {boolean} If a change was made/found
 */
function cleanColumns(&$grid)
{
	$cell_changed = FALSE;
	
	for ($j=0, $lenj=count($grid[0]); $j<$lenj; $j++) { // loop through each column
		for ($i=0, $leni=count($grid); $i<$leni; $i++) { // loop through each row
			$num = '';
			
			// find single value row within column
			if (count($grid[$i][$j]) == 1) {
				// we have a single value on cell
				$num = implode('', $grid[$i][$j]);
			}
			
			// remove found value from all rows in column
			if ($num != '') {
				for ($i2=0; $i2<$leni; $i2++) {
					// skip the current row we're on when clearing
					if ($i == $i2) continue;
					if (in_array($num, $grid[$i2][$j]) && count($grid[$i2][$j]) > 1) {
						unset($grid[$i2][$j][$num]);
						$cell_changed = TRUE;
					}
				}
			}
		}
	
	}
	
	return $cell_changed;
}

/**
 * Find/clean singletons within rows and columns
 *
 * Finds cells with multiple possibilities that contain a number not possible on
 * any other cell within the same row/column.
 *
 * @param $grid {array}
 * @return {boolean} If a change was made/found
 */
function cleanSingletons(&$grid)
{
	$cell_changed = FALSE;
	
	// loop through rows
	for ($i=0, $leni=count($grid); $i<$leni; $i++) {
		// hold number occurrences '$number' => $occurrence_count
		$occurences = array('1' => 0, '2' => 0, '3' => 0, '4' => 0, '5' => 0, '6' => 0, '7' => 0, '8' => 0, '9' => 0);
		for ($j=0, $lenj=count($grid[$i]); $j<$lenj; $j++) {
			foreach ($grid[$i][$j] as $num) {
				$occurences[$num]++;
			}
		}
		
		foreach ($occurences as $num=>$count) {
			// find numbers that only occured once on this row
			if ($count == 1) {
				for ($j=0; $j<$lenj; $j++) {
					if (in_array($num, $grid[$i][$j]) && count($grid[$i][$j]) > 1) {
						$grid[$i][$j] = array($num => $num);
						$cell_changed = TRUE;
						break;
					}
				}
			}
		}
	}
	
	
	// loop through columns
	for ($j=0, $lenj=count($grid[0]); $j<$lenj; $j++) {
		$occurences = array('1' => 0, '2' => 0, '3' => 0, '4' => 0, '5' => 0, '6' => 0, '7' => 0, '8' => 0, '9' => 0);
		for ($i=0, $leni=count($grid); $i<$leni; $i++) {
			foreach ($grid[$i][$j] as $num) {
				$occurences[$num]++;
			}
		}
		
		foreach ($occurences as $num=>$count) {
			if ($count == 1) {
				for ($i=0; $i<$leni; $i++) {
					if (in_array($num, $grid[$i][$j]) && count($grid[$i][$j]) > 1) {
						$grid[$i][$j] = array($num => $num);
						$cell_changed = TRUE;
						break;
					}
				}
			}
		}
	}
	
	
	return $cell_changed;
}

/**
 * Find/clean 3x3 cell groups
 * 
 * Finds cells with values and removes value from possibilities of cells within
 * surrounding 3x3 cells.
 *
 * @param $grid {array}
 * @return {boolean} If a change was made/found
 */
function cleanGroups(&$grid)
{	
	$cell_changed = FALSE;
	
	for ($i=0, $leni=count($grid); $i<$leni; $i++) {
		for ($j=0, $lenj=count($grid[$i]); $j<$lenj; $j++) {
			// find box with only 1 possibility
			if (count($grid[$i][$j]) == 1) {
				// remove this number from surrounding cells
				$num = implode('', $grid[$i][$j]);
				
				$starting_row = 0;
				if ($i >= 0 && $i <= 2) { // first 3 rows
				} elseif ($i >= 3 && $i <= 5) { // second 3 rows
					$starting_row = 3;
				} elseif ($i >= 6 && $i <= 9) { // third 3 rows
					$starting_row = 6;
				}
				
				$starting_column = 0;
				if ($j >= 0 && $j <= 2) { // first 3 columns
				} elseif ($j >= 3 && $j <= 5) { // second 3 columns
					$starting_column = 3;
				} elseif ($j >= 6 && $j <= 9) { // third 3 columns
					$starting_column = 6;
				}
				
				for ($i2=$starting_row; $i2<$starting_row+3; $i2++) {
					for ($j2=$starting_column; $j2<$starting_column+3; $j2++) {
						// skip the cell which we originally found the number on
						if ($i == $i2 && $j == $j2) continue;
						if (in_array($num, $grid[$i2][$j2])) {
							unset($grid[$i2][$j2][$num]);
							$cell_changed = TRUE;
						}
					}
				}
			}
		}
	}
	
	return $cell_changed;
}

/**
 * Find/clean pair of values
 * 
 * When cells on the same row/column have only two possibilities, the rest of
 * the cells on the row/column cannot contain these values.
 * 
 * @param $grid {array}
 * @return {boolean} If a change was made/found
 */
function cleanPairs(&$grid)
{
	$cell_changed = FALSE;
	
	// clean rows
	for ($i=0, $leni=count($grid); $i<$leni; $i++) {
		for ($j=0, $lenj=count($grid[$i]); $j<$lenj; $j++) {
			if (count($grid[$i][$j]) == 2) {
				for ($j2=$j+1; $j2<$lenj; $j2++) {
					if ($grid[$i][$j2] == $grid[$i][$j]) {
						// only these cells could possibly have this value so remove these values from other
						// cell columns on this row
						$possibilities = $grid[$i][$j];
						for ($j3=0; $j3<$lenj; $j3++) {
							if ($j3 == $j || $j3 == $j2) continue;
							foreach ($possibilities as $num) {
								if (in_array($num, $grid[$i][$j3])) {
									unset($grid[$i][$j3][$num]);
									$cell_changed = TRUE;
								}
							}
						}
					}
				}
			}
		}
	}
	
	// clean columns
	for ($j=0, $lenj=count($grid[0]); $j<$lenj; $j++) {
		for ($i=0, $leni=count($grid); $i<$leni; $i++) {
			if (count($grid[$i][$j]) == 2) {
				for ($i2=$i+1; $i2<$leni; $i2++) {
					if ($grid[$i][$j] == $grid[$i2][$j]) {
						$possibilities = $grid[$i][$j];
						for ($i3=0; $i3<$leni; $i3++) {
							if ($i3 == $i || $i3 == $i2) continue;
							foreach ($possibilities as $num) {
								if (in_array($num, $grid[$i3][$j])) {
									unset($grid[$i3][$j][$num]);
									$cell_changed = TRUE;
								}
							}
						}
					}
				}
			}
		}
	}
	
	return $cell_changed;
}

/**
 * Check whether the grid was solved
 *
 * @param $grid {array}
 * @return {boolean} Grid solved?
 */
function isSolved($grid)
{
	$rows = $columns = array();
	
	for ($i=0, $leni=count($grid); $i<$leni; $i++) {
		$rows[$i] = 0;
		for ($j=0, $lenj=count($grid); $j<$lenj; $j++) {
			if (count($grid[$i][$j]) != 1)
				return FALSE;
			$rows[$i] += implode('', $grid[$i][$j]);
			if (!isset($columns[$j]))
				$columns[$j] = 0;
			$columns[$j] += implode('', $grid[$i][$j]);
		}
	}
	
	// make sure that all rows and columns add up to 45
	foreach ($rows as $sum) {
		if ($sum != 45) return FALSE;
	}
	foreach ($columns as $sum) {
		if ($sum != 45) return FALSE;
	}
	
	return TRUE;
}

/**
 * Make guesses on grid possibilities
 *
 * @param $grid {array}
 * @param $possibilities_start {optional integer} Number of cell possibilities we will start checking from
 * @param $tier {optional integer} The level of guess tiers we're in (branches of solutions)
 * @return {array} Guessed grid array
 */
// TODO: Speed up guessing by focusing on cells with least possibilities first
function guess($grid, $possibilities_start = 2, $tier = 1)
{
	$guess_grid = $grid;
	
	do {
		for ($i=0, $leni=count($grid); $i<$leni; $i++) {
			for ($j=0, $lenj=count($grid[$i]); $j<$lenj; $j++) {
				
				$possibilities = count($grid[$i][$j]);
				
				if ($possibilities > 1 && $possibilities <= $possibilities_start) {
					// we have multiple possibilities on this cell
					
					// let's try each possibility and see how it affects the rest of the grid
					foreach ($grid[$i][$j] as $num) {
						$guess_grid[$i][$j] = array($num => $num);
						
						while (cleanRows($guess_grid) || cleanColumns($guess_grid) || cleanSingletons($guess_grid) || cleanGroups($guess_grid) || cleanPairs($guess_grid)) {}
						
						// check if we got any empty cells to try the next guess
						if (hasEmptyCell($guess_grid)) {
							// let's return the guess grid to it's normal state
							$guess_grid = $grid;
							// this guess is no good. skip to the next guess
							continue;
						}
					
						if (isSolved($guess_grid)) {
							return $guess_grid;
						} else {
							$guess_grid = guess($guess_grid, $possibilities_start, $tier + 1);
							if (isSolved($guess_grid)) {
								return $guess_grid;
							}
						}
					}
					
					// none of the guesses worked. let's move on in the upper tier. return the grid we 
					// originally received
					if ($tier > 1)
						return $grid;
				}
			}
		}
		$possibilities_start++;
	} while ($possibilities_start < 9 && !isSolved($guess_grid));
	
	return $guess_grid;
}

/**
 * Check for cells with empty values/possibilities
 *
 * This is used for checking guesses
 *
 * @param $grid {array}
 * @return {boolean} Whether we have an empty cell
 */
function hasEmptyCell($grid)
{
	for ($i=0, $leni=count($grid); $i<$leni; $i++) {
		for ($j=0, $lenj=count($grid[$i]); $j<$lenj; $j++) {
			if (empty($grid[$i][$j]))
				return TRUE;
		}
	}
	
	return FALSE;
}




/**
 * Runtime
 *
 * Command line: php sudoku_solver.php challenge.txt
 */

// start time tracking
$mtime = microtime(); 
$mtime = explode(' ', $mtime); 
$mtime = $mtime[1] + $mtime[0]; 
$starttime = $mtime;

$file = '';

// get file name/path from arguments
$file = $argv[1];
if (!file_exists($file)) {
	die("Error: File does not exist.\n");
} else {
	if (!is_file($file))
		die("Error: File does not appear to be a regular file.\n");
}

// TODO: Verify that file contents are valid
$challenge = trim(file_get_contents($file));
/*
$challenge = <<<END
000508007
154039006
000260300
000320508
040070030
501086000
009053000
200140983
700602000
END;
*/

$grid = array();

// prepare sudoku grid of possibilities
for ($i=0; $i<9; $i++) {
	for ($j=0; $j<9; $j++) {
		$grid[$i][$j] = array();
		for ($k=1; $k<=9; $k++) {
			$grid[$i][$j][$k] = $k;
		}
	}
}

// update sudoku grid with values from challenge
$arr = explode("\n", $challenge);
for ($i=0, $leni=count($arr); $i<$leni; $i++) {
	$arr[$i] = trim($arr[$i]);
	for ($j=0, $lenj=strlen($arr[$i]); $j<$lenj; $j++) {
		$num = $arr[$i][$j];
		if ($num != 0) {
			$grid[$i][$j] = array($num => $num);
		}
	}
}

// echo "\nChallenge\n=========\n";
// printGrid($grid);
// echo "\n\n";

while (cleanRows($grid) || cleanColumns($grid) || cleanSingletons($grid) || cleanGroups($grid) || cleanPairs($grid)) {}

if (!isSolved($grid)) {
	// we didn't solve, time to guess
	$guess_grid = guess($grid);
	if (isSolved($guess_grid))
		$grid = $guess_grid;
}

// end time tracking
$mtime = microtime();
$mtime = explode(' ', $mtime);
$mtime = $mtime[1] + $mtime[0];
$endtime = $mtime;
$totaltime = ($endtime - $starttime);

// did we solve the grid?
if (isSolved($grid)) {
	//echo "Solution\n=========\n";
	printGrid($grid);
	//echo 'Solved in ' . $totaltime . " seconds\n";
} else {
	echo "Sorry, could not solve challenge.\n";
	echo "Possibilities\n=============\n";
	printPossibilities($grid);
}
?>