Here is my PHP class for solving Sudoku:GitHubSudoku<?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 <goku.anush@gmail.com>* @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 sudokuprint <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 />;}?>Sudoku Solver<?php/*** @author Anush Prem <goku.anush@gmail.com>* @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 <goku.anush@gmail.com>* @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 $_inputif ( $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 sudokureturn $this -> _currentSudoku;}/*** updateSolved Method** Update the _solvedParts array to match the values of* _currentSudoku.** @access private* @return void*/private function _updateSolved(){// loop for rowsfor ($i = 0; $i < 9; $i++ )// loop for columnsfor ($j = 0; $j < 9; $j++ )// if the value exists for the corresponding row, column// then update the _solvedParts corresponding row, column// to trueif ( $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 solveddo{// 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 rowsfor ($i = 0; $i < 9; $i++ ){// loop for columnsfor ($j = 0; $j < 9; $j++ ){// if the ixj cell is not solved yetif ( !$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 rowsfor ($i = 0; $i < 9; $i++ ){// loop for columnfor ($j = 0; $j < 9; $j++ ){// if cell ixj is not solved yetif ( !$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 rowsfor ($i = 0; $i < 9; $i++ ){// loop for columnsfor ($j = 0; $j < 9; $j++ ){// if allSolved is still true an the cell iXj is notif ( $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$colif ( 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 solvedreturn 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 cellforeach ($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 columnfor ($i = 0; $i < 9; $i++ ){// if the cell is solved continue the loopif ($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 loopif (in_array($possible, $this -> _probable[$i][$col]))throw new ContinueException (Exists);}// loop through the current rowfor ($i = 0; $i < 9; $i++ ){// if the cell is solved continue the loopif ($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 loopif (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 gridfor ($i = $gridRowStart; $i < $gridRowStart + 3; $i++){// loop column through the current 3x3 grifor ($j = $gridColStart; $j < $gridColStart + 3; $j++){// if its the current $row x $col cell then// continue the loopif ($i == $row && $j == $col )continue;// if the cell is already solved then// continue the loopif ($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 loopif (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 loopcontinue;}}// 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 solvedreturn 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 columnfor ($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] ) != 0and( $key = array_search($current, $probable) ) !== false)unset ($probable[$key]);// loop through the current rowfor ($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] ) != 0and( $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 gridfor ($i = $gridRowStart; $i < $gridRowStart + 3; $i++)// loop column through the current 3x3 gridfor ($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] ) != 0and( $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 gridreturn floor( $value / 3 ) * 3;}}/*** <i>ContinueException</i> class** Extends Exception. Used to throw exception for* continue the outer most loop.**/Class ContinueException extends Exception{}?>
Sudoku solving class in PHP
php;php5;sudoku