Page 1 of 1

PHP sudoku solver bug

Posted: Sat May 02, 2009 10:02 am
by simonpapad
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. :banghead:

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 = "";
        }
        
    }
}
The C++ code:

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;
}

Re: PHP sudoku solver bug

Posted: Sat May 02, 2009 9:35 pm
by McInfo
Line 43 is not doing what you intend it to do. Most of the time, $ri is set to a float, not an integer.

Code: Select all

$ri = (int) $i / 9;
is the same as

Code: Select all

$ri = ((int) $i) / 9;
What you want it to do is

Code: Select all

$ri = (int) ($i / 9);
Edit: This post was recovered from search engine cache.

Re: PHP sudoku solver bug

Posted: Sun May 03, 2009 4:21 am
by simonpapad
:D :D :D :D :D
Thank you so much !!! I had also written wrong names to my 2dimensional array......
Problem solved!!