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]!=&& 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]!=&& 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]!=&& 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]!=&& 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;
                 
$gcs = ((int)($c/3))*3;
                 
$gce = ((int)($c/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,00,0,00,0,0),
               array(
0,0,00,0,00,0,0),
               array(
0,0,00,0,00,0,0),

               array(
0,0,00,0,00,0,0),
               array(
0,0,00,0,00,0,0),
               array(
0,0,00,0,00,0,0),

               array(
0,0,00,0,00,0,0),
               array(
0,0,00,0,00,0,0),
               array(
0,0,00,0,00,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)%'' ' ');
    }
    
$tr .= "$td. (($i+1)%'' ' ');
}

?>












                              
                        

Replies

  • Kaustubh Katdare
    Kaustubh Katdare
    Awesome, 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.bidkar
    uday.bidkar
    That's strange, did you fill the matrix with sudoku first?
  • uday.bidkar
    uday.bidkar
    Put the known values in the matrix at appropriate location and keep the unknown values as zeros
  • Kaustubh Katdare
    Kaustubh Katdare
    Alrighty. Will do. Folks, what's your feedback?
  • ms_cs
    ms_cs
    good idea..
  • Differential
    Differential
    You 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 !
  • swapnakumar
    swapnakumar
    uday amazing you are a brainee!!!!
  • Kaustubh Katdare
    Kaustubh Katdare
    Guys, help in improving this solver. Once it's ready, we'll make it officially available for download! 😀
  • uday.bidkar
    uday.bidkar
    Here 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!=&& $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)%'' ' ');
                }
                
    $tr .= "$td. (($i+1)%'' ' ');
            }
            return 
    " $tr 
    ";
       }
       private function 
    NormalizeCells(){
         for(
    $r=0$r<9;$r++){
               for(
    $c=0$c<9;$c++){
                     if(
    $this->grid[$r][$c]!=&& 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]!=&& 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]!=&& 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]!=&& 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;
                     
    $gcs = ((int)($c/3))*3;
                     
    $gce = ((int)($c/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,00,0,00,0,0),
                   array(
    0,0,00,0,00,0,0),
                   array(
    0,0,00,0,00,0,0),
     
                   array(
    0,0,00,0,00,0,0),
                   array(
    0,0,00,0,00,0,0),
                   array(
    0,0,00,0,00,0,0),
     
                   array(
    0,0,00,0,00,0,0),
                   array(
    0,0,00,0,00,0,0),
                   array(
    0,0,00,0,00,0,0) );
     

    $obj = new Sudoku;
    $obj->grid $grid;
    if(isset(
    $_REQUEST['grid']) && $_REQUEST['action'] != 'Reset'){
        
    $obj->Solve($_REQUEST['grid']);


    $htmlgrid .= $obj->GetHTMLGridTable();
    ?>
     
     









  • Kaustubh Katdare
    Kaustubh Katdare
    Yep, 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...