Sudoku solver
Wrote a sudoku solver. It does solve some sudokus (may be "easy" level) but gets stuck while solving few sudokus giving user multiple options for one cell and continues if user chooses one of the possible values for cell.
This is just first cut (with not much testing) and I am still working on improving it but thought it's a good time to have other brains involved
The code is in PHP, hence u'll have to run it on a LAMP/WAMP/XAMP stack to test it out.
<?php
class Sudoku {
public $cell = array();
public $small_grid = array();
public $grid = array();
public function Solve($grid){
$this->grid = $grid;
$i=0;
do{
$values_before = $this->TotalValues();
if(!$this->NormalizeCells())
break;
$this->NormalizeRows();
$this->NormalizeColumns();
$this->NormalizeSubgrid();
$values_after = $this->TotalValues();
}while($values_before != $values_after);
}
public function PrintGrid(){
for($i=0; $i<9;$i++){
for($j=0; $j<9;$j++){
echo $this->grid[$i][$j]."\t";
}
echo (($i+1)%3)? "\n" : "\n\n" ;
}
}
private function NormalizeCells(){
for($r=0; $r<9;$r++){
for($c=0; $c<9;$c++){
if($this->grid[$r][$c]!=0 && strlen($this->grid[$r][$c])==1){
continue;
}
unset($possible_values);
$possible_values = array(0,1,2,3,4,5,6,7,8,9);
for($i=0;$i<9;$i++){
if(strlen($this->grid[$r][$i])==1){
$possible_values[$this->grid[$r][$i]] = 0;
}
if(strlen($this->grid[$i][$c])==1){
$possible_values[$this->grid[$i][$c]] = 0;
}
}
$gr = ((int)($r/3))*3;
$gc = ((int)($c/3))*3;
for($i=$gr;$i<($gr+3);$i++){
for($j=$gc;$j<($gc+3);$j++){
if(strlen($this->grid[$i][$j])==1){
$possible_values[$this->grid[$i][$j]] = 0;
}
}
}
$possible_values = array_unique($possible_values);
array_shift($possible_values);
if(empty($possible_values)){
echo "<p>Wrong values entered!!!<br>";
return false;
}
$this->grid[$r][$c] = implode(',',$possible_values);
}
}
return true;
}
function NormalizeRows(){
for($r=0; $r<9;$r++){
for($c=0; $c<9;$c++){
if($this->grid[$r][$c]!=0 && strlen($this->grid[$r][$c])==1){
continue;
}
$values = explode(',', $this->grid[$r][$c]);
foreach($values as $value){
for($i=0;$i<9;$i++){
if($i==$c || empty($value))
continue;
if(strstr($this->grid[$r][$i],(string)$value))
break;
}
if($i==9)
$this->grid[$r][$c] = $value;
}
}
}
}
function NormalizeColumns(){
for($r=0; $r<9;$r++){
for($c=0; $c<9;$c++){
if($this->grid[$r][$c]!=0 && strlen($this->grid[$r][$c])==1){
continue;
}
$values = explode(',', $this->grid[$r][$c]);
foreach($values as $value){
for($i=0;$i<9;$i++){
if($i==$c || empty($value))
continue;
if(strstr($this->grid[$i][$c],(string)$value))
break;
}
if($i==9)
$this->grid[$r][$c] = $value;
}
}
}
}
function NormalizeSubgrid(){
for($r=0; $r<9;$r++){
for($c=0; $c<9;$c++){
if($this->grid[$r][$c]!=0 && strlen($this->grid[$r][$c])==1){
continue;
}
$values = explode(',', $this->grid[$r][$c]);
foreach($values as $value){
$grs = ((int)($r/3))*3;
$gre = ((int)($r/3))*3 + 3;
$gcs = ((int)($c/3))*3;
$gce = ((int)($c/3))*3 + 3;
for($gr=$grs;$gr<$gre;$gr++){
for($gc=$gcs;$gc<$gce;$gc++){
if($gr==$r && $gc==$c || empty($value))
continue;
/*if($grs==6&&gcs==0&&$r==7&&$c==1){
echo "<br>Finding $value in " . $this->grid[$gr][$gc];
}*/
if(strstr($this->grid[$gr][$gc],(string)$value))
break;
}
if($gc != $gce)
break;
}
if($gr==$gre && $gc==$gce)
$this->grid[$r][$c] = $value;
}
}
}
}
private function TotalValues(){
for($i=0; $i<9;$i++){
for($j=0; $j<9;$j++){
if($this->grid[$i][$j] == 0)
continue;
$cell_elements = strlen($this->grid[$i][$j]);
$total_elements += $cell_elements;
}
}
return $total_elements;
}
}
$grid = array( array(0,0,0, 0,0,0, 0,0,0),
array(0,0,0, 0,0,0, 0,0,0),
array(0,0,0, 0,0,0, 0,0,0),
array(0,0,0, 0,0,0, 0,0,0),
array(0,0,0, 0,0,0, 0,0,0),
array(0,0,0, 0,0,0, 0,0,0),
array(0,0,0, 0,0,0, 0,0,0),
array(0,0,0, 0,0,0, 0,0,0),
array(0,0,0, 0,0,0, 0,0,0) );
if(isset($_REQUEST['grid']) && $_REQUEST['action'] != 'Reset'){
$obj = new Sudoku;
$obj->Solve($_REQUEST['grid']);
$grid = $obj->grid;
}
for($i=0; $i<9;$i++){
unset($td);
for($j=0; $j<9;$j++){
$td .= '<td align="left" colspan="2" ><input style="width:50px" type="text" value="' . $grid[$i][$j] .'" name="' . "grid[$i][$j]" . '" /></td>'
. (($j+1)%3 ? '' : '<td> </td>');
}
$tr .= "<tr>$td</tr>" . (($i+1)%3 ? '' : '<tr><td> </td></tr>');
}
?>
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<form action="sudoku.php" method="post">
<table width="50%" border="0" align="left" cellpadding="1" cellspacing="1">
<? echo $tr ?>
</table>
<input type="submit" name="action" value="Solve">
<input type="submit" name="action" value="Reset">
</form>
</html>
