PHP sudoku solver bug
Posted: Sat May 02, 2009 10:02 am
Good afternoon !!
I have transformed a Sudoku Solver code from C++ to PHP.Allthough the C++ code works fine, the respective in PHP gets into an infinite loop when the function solveIt() is called.
I think that $i and $j variables which are the array indexes of a[] and b[][] become negative!!
I would be grateful if someone could help me!
Thank you,
Simon
The PHP script:
The C++ code:
I have transformed a Sudoku Solver code from C++ to PHP.Allthough the C++ code works fine, the respective in PHP gets into an infinite loop when the function solveIt() is called.
I think that $i and $j variables which are the array indexes of a[] and b[][] become negative!!
I would be grateful if someone could help me!
Thank you,
Simon
The PHP script:
Code: Select all
class SudokuSolver
{
// member declaration
public $calctime; //this variable stores the calculation time
public $numarr; //this is an array (1 x dimension) that stores the Puzzle numbers
public $mdnumarr; //this is an array (2 x dimensions) that stores the Puzzle numbers
//Constructor
public function __construct($inputstr) {
if(strlen($inputstr) < 81)
echo "Worng!!";
for($i=0; $i<81; $i++){
$this->numarr[$i] = (int) $inputstr[$i];
}
$k=0;
for($i=0; $i<9; $i++){
for($j=0; $j<9; $j++)
$this->mdnumarr[$i][$j] = $this->numarr[$k++];
}
// echo "Done good";
//
// echo "<br>".$inputstr;
// print_r($this->numarr);
}
public function solveIt(){
$i = 0;
$j = 0;
$k = 0;
$ri = 0;
$ci = 0;
$sr = 0;
$sc = 0;
$flag = 0;
//temporary arrays
$b = $this->numarr;
$a = $this->dmnumarr;
for($i=0; $i<81; $i++){
$ri = (int) $i/9;
$ci = (int) $i%9;
echo "ri".$ri;
echo "\tci".$ci."<br>";
if($b[$i]!=0)
continue;
do{
$flag=1; //made true as if the value in a[ri][ci] is valid;
$a[$ri][$ci]++;
//row check if an duplicate is found then flag is made false
for($j=0; $j<9; $j++){
if($j!=$ci && $a[$ri][$ci]==$a[$ri][$j]){
$flag = 0;
break;
}
}
//column check if an duplicate is found then flag is made false
for($j=0; $j<9; $j++){
if($j!=$ri && $a[$ri][$ci]==$a[$j][$ci]){
$flag = 0;
break;
}
}
//square check if an duplicate is found then flag is made false
$sr=((int) $ri/3)*3;
$sc=((int)$ci/3)*3;
for($j=0; $j<3; $j++){
for($k=0; $k<3; $k++){
$booltmp = ((($sr+$j) != $ri)||($sc+$k!=$ci));
$booltmp2 = $a[$ri][$ci] == $a[$sr+$j][$sc+$k];
if( $booltmp && $booltmp2){
$flag=0;
break;
}
}
if($flag==0)
break;
}
}while($flag==0 && $a[$ri][$ci]<10);
if($a[$ri][$ci]==10){
$a[$ri][$ci]=0;
$i-=2;
echo $i."<br>";
while($b[$i+1]!=0){
$i--;
echo $i."<br>";
}
}
}
}
public function showEnd(){
echo "<br><br>HELLO!!<br>";
$oyti = "";
for($i=0; $i<9; $i++){
for($j=0; $j<9; $j++){
$oyti .= $this->mdnumarr[$i][$j];
}
$oyti .= "<br>";
echo $oyti;
$oyti = "";
}
}
}Code: Select all
#include<stdio.h>
#include<string.h>
using namespace std;
class sudoku
{ int a[9][9],b[81];
public:
sudoku(int[]);
void solve();
void show();
};
sudoku::sudoku(int g[]){
for(int i=0; i<81; i++)
b[i] = g[i];
int p=0;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++)
a[i][j]=b[p++];
}
}
void sudoku::solve()
{ int i,j,k,ri,ci,sr,sc;
/*If i is the index of the 1D array, then ri and ci are the row and
column of the equivalent pos of the 2D array. sr and sc are the row and
column of the top left element the cell's 3x3 square.
*/
int flag;
for(i=0;i<81;i++)
{ ri=i/9;
ci=i%9;
if(b[i]!=0)
continue;
do
{ flag=1; //made true as if the value in a[ri][ci] is valid;
a[ri][ci]++; //Increment to try the next value. 1st time it becomes 1
//row check if an duplicate is found then flag is made false
for(j=0;j<9;j++)
{ if(j!=ci&& a[ri][ci]==a[ri][j])
{ flag=0;
break;
}
}
//column check if an duplicate is found then flag is made false
for(j=0;j<9;j++)
{ if(j!=ri&& a[ri][ci]==a[j][ci])
{ flag=0;
break;
}
}
//square check if an duplicate is found then flag is made false
sr=(ri/3)*3;
sc=(ci/3)*3;
for(j=0;j<3;j++)
{ for(k=0;k<3;k++)
{ if((sr+j!=ri||sc+k!=ci) && a[ri][ci]==a[sr+j][sc+k])
{ flag=0;
break;
}
}
if(flag==0)
break;
}
}while(flag==0 && a[ri][ci]<10);
if(a[ri][ci]==10)
{ a[ri][ci]=0;
i-=2;
while(b[i+1]!=0)
i--;
}
}
}
void sudoku::show()
{ int i,j;
cout<<"\n";
for(i=0;i<9;i++)
{ for(j=0;j<9;j++)
cout<<a[i][j]<<"\t";
cout<<"\n\n";
}
}
int main()
{
int d[] = {0,0,3,0,0,0,0,5,1,5,0,2,0,0,6,4,0,0,0,0,7,0,5,0,0,0,0,0,0,0,6,3,0,7,0,0,2,0,0,7,0,8,0,0,6,0,0,4,0,2,1,0,0,0,0,0,0,0,7,0,8,0,0,0,0,8,1,0,0,6,0,9,1,7,0,0,0,0,5,0,0};
sudoku ob(d);
ob.solve();
ob.show();
getch();
return 0;
}