sudoku.php

<?php

/**
* Bootstrap file
*
* This is an example of how to use the SudokuSolver Class
* Here the input array has been hardcoded. It could be send
* as get or post in the real application.
*
* @author Anush Prem <[email protected]>
* @package Solver
* @subpackage Sudoku
* @version 0.1
*/

/**
* Required Class files
*/
	include_once "SudokuSolver.class.php";
	
	// The application could take longer than normal php execution
	// time. So set the execution time limit to 0(unlimited).
	set_time_limit(0);
	
	// input sudoku array in the format row == col array mapping
	$sudoku = array(
		array(0,4,0,0,5,3,1,0,2),
		array(2,0,8,1,0,0,7,0,0),
		array(5,0,1,4,2,0,6,0,0),
		array(8,1,4,0,3,0,2,0,7),
		array(0,6,0,2,0,5,0,1,9),
		array(0,5,0,7,4,0,0,6,3),
		array(0,0,0,0,7,4,5,8,1),
		array(1,8,5,9,0,2,0,0,0),
		array(4,0,3,0,0,8,0,2,6)
	);
	
	// create an object of SudokuSolver.
	$solver = new SudokuSolver();
	
	// Pass the input sudoku to the $solver object.
	$solver -> input ($sudoku);
	
	// Solve the sudoku and return the solved sudoku.
	$solved = $solver -> solve ();
	
	// printing the formated input sudoku
	print "<B>Input Sudoku:</B><br />";
	foreach ($sudoku as $row){
		foreach ($row as $col ){
			print $col . "&nbsp;&nbsp;";
		}
		print "<br />";
	}
	
	print "<hr />";
	
	// printing the formated solved sudoku.
	print "<B>Solved Sudoku:</B><br />";
	foreach ($solved as $row){
		foreach ($row as $col ){
			print $col . "&nbsp;&nbsp;";
		}
		print "<br />";
	}
?>

SudokuSolver.class.php

<?php

/**
* @author Anush Prem <[email protected]>
* @package Solver
* @subpackage Sudoku
* @version 0.1
*/

/**
* <i>Sudoku Solver</i> class
* 
* This class solves the sudoku in my own logic.
*
* This solver takes time to execute according to the 
* complexity of the sudoku.
*
* @author Anush Prem <[email protected]>
* @package Solver
* @subpackage Sudoku
* @version 0.1
*/

	Class SudokuSolver{
	
		/**
		* To store the input Sudoku
		* @access private
		* @var array $_input row == column mapping
		*/
		private $_input;
		
		/**
		* To store the currently solved sudoku at any moment of time
		* @access private
		* @var array $_currentSudoku row == column mapping
		*/
		private $_currentSudoku;
		
		/**
		* To store the probable values for each cell
		* @access private
		* @var array $_probable [row][col] == possible values array mapping
		*/
		private $_probable;
		
		/**
		* to store weather the sudoku have been solved or not
		* @access private
		* @var bool
		*/
		private $_solved = false;
		
		/**
		* store weather each cell is solved or not
		* @access private
		* @var array $_solvedParts row == column (bool) values
		*/
		private $_solvedParts = array (
			array ( false, false, false, false, false, false, false, false, false ),
			array ( false, false, false, false, false, false, false, false, false ),
			array ( false, false, false, false, false, false, false, false, false ),
			array ( false, false, false, false, false, false, false, false, false ),
			array ( false, false, false, false, false, false, false, false, false ),
			array ( false, false, false, false, false, false, false, false, false ),
			array ( false, false, false, false, false, false, false, false, false ),
			array ( false, false, false, false, false, false, false, false, false ),
			array ( false, false, false, false, false, false, false, false, false )
		);
		
		/**
		* SudokuSolver constructor
		*
		* If the input sudoku is provided it will store to the {@link _input} property.
		* 
		* @access public
		* @param array $input row == column mapping
		* @return void
		*/
		public function __construct($input = null){
			
			// check if the input sudoku is provided, if yes then
			// store it in $_input
			if ( $input !== null ) $this -> _input = $input;
		}
		
		/**
		* Input Method
		*
		* Explictly give a new input array if its not already provided in 
		* the constructor. If already provieded in the constructore then
		* it will be replaced
		*
		* @access public
		* @param array $input row == column mapping
		* @return void
		*/
		public function input($input){
			
			// store the received input into $_input
			$this -> _input = $input;
		}
		
		/**
		* Solve Method
		*
		* The main function to start solving the sudoku and return the
		* solved sudoku
		*
		* @access public
		* @return array row == column mapping of solved sudoku
		*/
		public function solve (){
		
			// Copy the input sudoku to _currentSudoku
			$this -> _currentSudoku = $this -> _input;
			
			// update _solvedParts of the given sudoku
			$this -> _updateSolved ();
			
			// Start solving the sudoku
			$this -> _solveSudoku();
			
			// return the solved sudoku
			return $this -> _currentSudoku;
		}
		
		/**
		* updateSolved Method
		*
		* Update the _solvedParts array to match the values of 
		* _currentSudoku.
		*
		* @access private
		* @return void
		*/
		private function _updateSolved(){
			
			// loop for rows
			for ($i = 0; $i < 9; $i++ )
			
				// loop for columns
				for ($j = 0; $j < 9; $j++ )
				
					// if the value exists for the corresponding row, column
					// then update the _solvedParts corresponding row, column
					// to true
					if ( $this -> _currentSudoku[$i][$j] != 0 )
						$this -> _solvedParts[$i][$j] = true;
		}
		
		/**
		* _solveSudoku Method
		*
		* Main sudoku solving method
		*
		* @access private
		* @return void
		*/
		private function _solveSudoku(){
			
			// continue running untill the sudoku is completly solved
			do{
				// calculate the probable values for each cell an solve 
				// available cells
				$this -> _calculateProbabilityAndSolve();
				
				// check weather the sudoku is completly solved
				$this -> _checkAllSolved();
			}while (!$this -> _solved); // run till the _solved value becomes true
			
		}
		
		/**
		* _calculateProbabilityAndSolve Method
		*
		* Find the possible values for each cell and
		* solve it if possible
		*
		* @access private
		* @return void
		*/
		private function _calculateProbabilityAndSolve(){
			
			// find possible values for each cell
			$this -> _findPosibilites();
			
			// check if each cell is solveable and if yes solve it
			$this -> _solvePossible();
			
		}
		
		/**
		* _findPosibilites Method
		*
		* Find possible values for each cell
		*
		* @access private
		* @return void
		*/
		private function _findPosibilites(){
		
			// loop for rows
			for ($i = 0; $i < 9; $i++ ){
			
				// loop for columns
				for ($j = 0; $j < 9; $j++ ){
					
					// if the ixj cell is not solved yet
					if ( !$this -> _solvedParts[$i][$j] ){
						
						// find all possible values for cell ixj
						$this -> _findAllProbables ($i, $j);
					}
				}
			}
		}
		
		/**
		* _solvePossible Method
		*
		* Solve possible cells using probable values calculated
		*
		* @access private
		* @return void
		*/
		private function _solvePossible(){
		
			// loop for rows
			for ($i = 0; $i < 9; $i++ ){
			
				// loop for column
				for ($j = 0; $j < 9; $j++ ){
					
					// if cell ixj is not solved yet
					if ( !$this -> _solvedParts[$i][$j] ){
						
						// solve the cell ixj if possible using probable values
						// calculated
						$this -> _solveIfSolveable ($i, $j);
					}
				}
			}
		}
		
		/**
		* _checkAllSolved Method
		*
		* check if all the cells have been solved
		*
		* @access private
		* @return void
		*/
		private function _checkAllSolved(){
		
			// pre assign all solved as true
			$allSolved = true;
			
			// loop for rows
			for ($i = 0; $i < 9; $i++ ){
			
				// loop for columns
				for ($j = 0; $j < 9; $j++ ){
				
					// if allSolved is still true an the cell iXj is not
					if ( $allSolved and !$this -> _solvedParts[$i][$j] ){
						// set all solved as false
						$allSolved = false;
					}
				}
			}
			
			// copy the value of allSolved into _solved.
			$this -> _solved = $allSolved;
		}
		
		/**
		* _solveIfSolveable Method
		*
		* Solve a single cell $rowx$col if it is solveable using
		* available probable datas
		*
		* @access private
		* @param int $row 0-8
		* @param int $col 0-8
		* @return bool
		*/
		private function _solveIfSolveable ($row, $col){
			
			// if there is only one probable value for the cell $rowx$col
			if ( count ($this -> _probable[$row][$col]) == 1 ){
				
				// copy the only possible value to $value
				$value = $this -> _probable[$row][$col][0];
				
				// set the value of cell $rowx$col as $value an update solvedParts
				$this -> _setValueForCell ($row, $col, $value);
				
				// return true as solved
				return true;
			}
			
			// pre assign $value as 0. ie; not solved
			$value = 0;
			
			// loop through all the possible values for $row x $col
			// and check if any possiblity can be extracted from it
			// by checking if its possible for the same number to be
			// positioned anywhere else thus confilicting with current
			// cell. If a possibility is not a possibility for any other
			// cell in the confilicting places then it is the value for 
			// current cell
			foreach ($this -> _probable[$row][$col] as $possible){
			
				// a try-catch exception handling used here
				// as a control statement for continuing the main loop 
				// if a value is possible in some place.
				try{
				
					// loop through the current column
					for ($i = 0; $i < 9; $i++ ){
						// if the cell is solved continue the loop
						if ($this -> _currentSudoku[$i][$col] != 0)
							continue;
						
						// if the possible is also possible in the $i x $col cell
						// then throw a ContinueException to continue the outer loop
						if (in_array($possible, $this -> _probable[$i][$col]))
							throw new ContinueException ("Exists");
						
					}
					
					// loop through the current row
					for ($i = 0; $i < 9; $i++ ){
						// if the cell is solved continue the loop
						if ($this -> _currentSudoku[$row][$i] != 0)
							continue;
						
						// if the possible is also possible in the $i x $col cell
						// then throw a ContinueException to continue the outer loop
						if (in_array($possible, $this -> _probable[$row][$i]))
							throw new ContinueException ("Exists");
						
					}
					
					// find the start of the 3x3 grid with $row x $col cell
					$gridRowStart = $this -> _findGridStart($row);
					$gridColStart = $this -> _findGridStart($col);
					
					// loop row through the current 3x3 grid
					for ($i = $gridRowStart; $i < $gridRowStart + 3; $i++){
						
						// loop column through the current 3x3 gri
						for ($j = $gridColStart; $j < $gridColStart + 3; $j++){
						
							// if its the current $row x $col cell then 
							// continue the loop
							if ($i == $row && $j == $col ) 
								continue; 
								
							// if the cell is already solved then 
							// continue the loop
							if ($this -> _currentSudoku[$row][$i] != 0)
								continue;

							// if the possible is also possible in the 
							// $i x $j cell then throw a ContinueException
							// to continue the outer loop
							if (in_array($possible, $this -> _probable[$i][$j]))
								throw new ContinueException ("Exists");
						}
					}
					
					// if the loop is not continued yet,
					// then that means this possible value is
					// not possible in any other conflicting 
					// cells. So assign the value of $value to 
					// $possible and break the loop.
					$value = $possible;
					break;
				}catch (ContinueException $e){
					// if a ContinueException is thrown then contine
					// the outer loop
					continue;
				}
			}
			
			// if the value of $value is not 0 then the value of 
			// the cell is $value.
			if ($value != 0){
				
				// set the value of cell $rowx$col as $value an update solvedParts
				$this -> _setValueForCell ($row, $col, $value);
				
				// return true as solved
				return true;
			}
			
			// return false as not solved yet.
			return false;
		}
		
		/**
		* _setValueForCell Method
		*
		* If a cell is solved then update the value for 
		* that cell, and also update the {@link _solvedParts}.
		*
		* @access private
		* @param int $row 0-8
		* @param int $col 0-8
		* @param int $value 1-9
		* @return void		
		*/
		private function _setValueForCell($row, $col, $value){
		
			// update the solved parts in _currentSudoku.
			$this -> _currentSudoku[$row][$col] = $value;
			
			// update the corresponding _solvedParts.
			$this -> _solvedParts[$row][$col] = true;
		}
		
		/**
		* _findAllProbables Method
		*
		* Find all possible values for any given cell using
		* other already solved or given cell values.
		*
		* @access private
		* @param int $row 0-8
		* @param int $col 0-8
		* @return void
		*/
		private function _findAllProbables ($row, $col){
		
			// initially set the $probable as array 1 to 9.
			$probable = range(1,9);
			
			// loop through current column
			for ($i = 0; $i < 9; $i++ )
			
				// if the cell $i x $col is solved and the value of
				// cell $ix$col is in the $probable array then remove
				// that element.
				if ( 
					( $current = $this -> _currentSudoku[$i][$col] ) != 0  
					and 
					( $key = array_search($current, $probable) ) !== false 
				)
					unset ($probable[$key]);
					
			// loop through the current row
			for ($i = 0; $i < 9; $i++ )
			
				// if the cell $row x $i is solved and the value of
				// cell $rowx$i is in the $probable array then remove
				// that element.
				if ( 
					( $current = $this -> _currentSudoku[$row][$i] ) != 0  
					and 
					( $key = array_search($current, $probable) ) !== false 
				)
					unset ($probable[$key]);
				
			// find the start of the 3x3 grid with $row x $col cell
			$gridRowStart = $this -> _findGridStart($row);
			$gridColStart = $this -> _findGridStart($col);
			
			// loop row through the current 3x3 grid
			for ($i = $gridRowStart; $i < $gridRowStart + 3; $i++)
			
				// loop column through the current 3x3 grid
				for ($j = $gridColStart; $j < $gridColStart + 3; $j++)
				
					// if the cell $i x $j is solved and the value of
					// cell $ix$j is in the $probable array then remove
					// that element.
					if ( 
						( $current = $this -> _currentSudoku[$i][$j] ) != 0  
						and 
						( $key = array_search($current, $probable) ) !== false 
					)
						unset ($probable[$key]);
				
			// Store the rest of the probable values to 
			// _probable[$row][$col]
			$this -> _probable[$row][$col] = array_values($probable);
			
		}
		
		/**
		* _findGridStart Method
		*
		* Find the start of the 3x3 grid in which the value
		* comes
		*
		* @access private
		* @param int $value 0-9
		* @return int
		*/
		private function _findGridStart ($value){
		
			// return the start of the current 3x3 grid
			return floor( $value / 3 ) * 3;
		}
	}
	
/**
* <i>ContinueException</i> class
* 
* Extends Exception. Used to throw exception for 
* continue the outer most loop.
* 
*/	
	Class ContinueException extends Exception{}

?>