PHP sudoku solver bug

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
simonpapad
Forum Newbie
Posts: 2
Joined: Sat May 02, 2009 9:54 am

PHP sudoku solver bug

Post 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;
}
Last edited by Benjamin on Sat May 02, 2009 12:24 pm, edited 1 time in total.
Reason: Changed code type from text to php.
User avatar
McInfo
DevNet Resident
Posts: 1532
Joined: Wed Apr 01, 2009 1:31 pm

Re: PHP sudoku solver bug

Post 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.
Last edited by McInfo on Tue Jun 15, 2010 3:15 pm, edited 1 time in total.
simonpapad
Forum Newbie
Posts: 2
Joined: Sat May 02, 2009 9:54 am

Re: PHP sudoku solver bug

Post by simonpapad »

:D :D :D :D :D
Thank you so much !!! I had also written wrong names to my 2dimensional array......
Problem solved!!
Post Reply