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.
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 "Wrong values entered!!!
"
;
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 "
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 .= '. $grid[$i][$j] .'" name="' . "grid[$i][$j]" . '" /> '
. (($j+1)%3 ? '' : ' ');
}
$tr .= "$td " . (($i+1)%3 ? '' : ' ');
}
?>
Replies
-
Kaustubh KatdareAwesome, dude!
I set it up and hit 'solve' - all the boxes got filled with "1,2,3,4,5,6,7,8,9". Maybe this needs to be fixed?
PS: Or am I just being dumbass here? 😁 -
uday.bidkarThat's strange, did you fill the matrix with sudoku first?
-
uday.bidkarPut the known values in the matrix at appropriate location and keep the unknown values as zeros
-
Kaustubh KatdareAlrighty. Will do. Folks, what's your feedback?
-
ms_csgood idea..
-
DifferentialYou mean, this code solves the sudoku puzzle. So it needs a puzzle with some boxes prefilled. okay. What if a puzzle has multiple solution. Does this code throw such message or gives one of the answers or fails.
But anyway writing such code is amazing thing! Hats off ! -
swapnakumaruday amazing you are a brainee!!!!
-
Kaustubh KatdareGuys, help in improving this solver. Once it's ready, we'll make it officially available for download! 😀
-
uday.bidkarHere goes the final cut. Removed couple of bugs and improved it to get the final solution at one go. Plz test it out further and let me know the bugs if any
@Big K, Can we host this on CE so that people can easily test it out?
php
class Sudoku {
public $cell = array();
public $small_grid = array();
public $grid = array();
public function Solve($grid){
$this->grid = $grid;
$this->Noramlize();
$this->ResolveAmbiguity();
}
private function Noramlize(){
do{
$values_before = $this->TotalValues();
if(!$this->NormalizeCells())
return false;
if(!$this->NormalizeRows())
return false;
if(!$this->NormalizeColumns())
return false;
if(!$this->NormalizeSubgrid())
return false;
$values_after = $this->TotalValues();
}while($values_before != $values_after);
return true;
}
private function ResolveAmbiguity($i=0,$j=0){
for($r=$i; $r<9;$r++){
for($c=$j; $c<9;$c++){
if(strlen($this->grid[$r][$c])>1)
break;
}
if(strlen($this->grid[$r][$c])>1)
break;
}
if($r!=9 && $c != 9){
$values = explode(',',$this->grid[$r][$c]);
foreach($values as $value){
$ori_grid = $this->grid;
$this->grid[$r][$c] = $value;
if(!$this->Noramlize()){
$this->grid = $ori_grid;
if(0!=$i || 0!=$j)
return false;
continue;
}
if($this->TotalValues() == 81)
return true;
if($this->ResolveAmbiguity($r,$c+1))
return true;
$this->grid = $ori_grid;
}
return false;
}
return true;
}
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" ;
}
}
public function GetHTMLGridTable(){
for($i=0; $i<9;$i++){
unset($td);
for($j=0; $j<9;$j++){
$td .= '. $this->grid[$i][$j] .'" name="' . "grid[$i][$j]" . '" /> '
. (($j+1)%3 ? '' : '
}
$tr .= "$td " . (($i+1)%3 ? '' : ' ');
}
return "";$tr
}
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 "Wrong Values !!!
";
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)!==false)
break;
}
if($i==9){
$this->grid[$r][$c] = $value;
if(!$this->NormalizeCells())
return false;
}
}
}
}
return true;
}
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==$r || empty($value))
continue;
if(strstr($this->grid[$i][$c],(string)$value)!==false)
break;
}
if($i==9){
$this->grid[$r][$c] = $value;
if(!$this->NormalizeCells())
return false;
}
}
}
}
return true;
}
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(strstr($this->grid[$gr][$gc],(string)$value)!==false)
break;
}
if($gc != $gce)
break;
}
if($gr==$gre && $gc==$gce){
$this->grid[$r][$c] = $value;
if(!$this->NormalizeCells())
return false;
}
}
}
}
return true;
}
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;
}
}
$htmlgrid = "";
$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) );
$obj = new Sudoku;
$obj->grid = $grid;
if(isset($_REQUEST['grid']) && $_REQUEST['action'] != 'Reset'){
$obj->Solve($_REQUEST['grid']);
}
$htmlgrid .= $obj->GetHTMLGridTable();
?>
-
Kaustubh KatdareYep, surely. Give me some time though.
You are reading an archived discussion.
Related Posts
Here i am going to show some Crop Circle images...
among them mostly are really puzzle for scientist who made it? no one knows i read one article on that...
Hey CEans how many of you are aware of the listings of the India Budget 09-10..
Among great expectations Pranab Mukherjee, Finance Minister of Congress 2
released the budget that...
hey all the pro's engineer out there, i am a degree student doing a final project. My group is doing the whole AGV for a FMS. The automated guided vehicle...
Hi All,
Following is an interesting puzzle i found while browsing,
Every weekday at 6 PM sharp Nawab Gulzarilal arrives by rail at the Lucknow station, and every weekday at...
Hello everyone,
i just joined the CE forum and was browsing through when i came across this thread. First of all let me introduce my self, i am Asher Khan...