数独求解程序 php版

  1 <?php
  2 class Sudoku {
  3     var $matrix;
  4 
  5     function __construct($arr = null) {
  6         if ($arr == null) {
  7             $this->clear();
  8         } else {
  9             $this->matrix = $arr;
 10         }
 11     }
 12     
 13     function clear() {
 14         for($i=0; $i<9; $i++) {
 15             for($j=0; $j<9; $j++) {
 16                 $this->matrix[$i][$j] = array();
 17                 for ($k = 1; $k <= 9; $k++) {
 18                     $this->matrix[$i][$j][$k] = $k;
 19                 }
 20             }
 21         }
 22     }
 23 
 24     function setCell($row, $col, $value){
 25         $this->matrix[$row][$col] = array($value => $value);
 26         //row
 27         for($i = 0; $i < 9; $i++){
 28             if($i != $col){
 29                 if(! $this->removeValue($row, $i, $value)) {
 30                     return false;
 31                 }
 32             }
 33         }
 34         //col
 35         for($i = 0; $i < 9; $i++){
 36             if($i != $row){
 37                 if(! $this->removeValue($i, $col, $value)) {
 38                     return false;
 39                 }
 40             }
 41         }
 42         //square
 43         $rs=intval($row / 3) * 3;
 44         $cs=intval($col / 3) * 3;
 45 
 46         for($i = $rs; $i < $rs + 3; $i++){
 47             for($j = $cs; $j < $cs + 3; $j++){
 48                 if($i != $row && $j != $col){
 49                     if(! $this->removeValue($i, $j, $value))
 50                         return false;
 51                 }
 52             }
 53         }
 54         return true;
 55     }
 56     
 57     function removeValue($row, $col, $value) {
 58         $count = count($this->matrix[$row][$col]);
 59         if($count == 1){
 60             $ret = !isset($this->matrix[$row][$col][$value]);
 61             return $ret;
 62         }
 63         if (isset($this->matrix[$row][$col][$value])) {
 64             unset($this->matrix[$row][$col][$value]);
 65             if($count - 1 == 1) {
 66                 return $this->setCell($row, $col, current($this->matrix[$row][$col]));
 67             }
 68         }
 69         return true;
 70     }
 71     
 72     function set($arr) {
 73         for ($i = 0; $i < 9; $i++) {
 74             for ($j = 0; $j < 9; $j++) {
 75                 if ($arr[$i][$j] > 0) {
 76                     $this->setCell($i, $j, $arr[$i][$j]);
 77                 }
 78             }
 79         }
 80     }
 81 
 82     function dump() {
 83         for($i = 0; $i < 9; $i++){
 84             for($j = 0; $j < 9; $j++){
 85                 $c = count($this->matrix[$i][$j]);
 86                 if($c == 1){
 87                     echo " ".current($this->matrix[$i][$j])." ";
 88                 } else {
 89                     echo "(".$c.")";
 90                 }
 91             }
 92             echo "\n";
 93         }
 94         echo "\n";
 95     }
 96 
 97     function dumpAll() {
 98         for($i = 0; $i < 9; $i++){
 99             for($j = 0; $j < 9; $j++){
100                 echo implode(\'\', $this->matrix[$i][$j]), "\t";
101             }
102             echo "\n";
103         }
104         echo "\n";
105     }
106 
107     function calc($data) {
108         $this->clear();
109         $this->set($data);
110         $this->_calc();
111         $this->dump();
112     }
113 
114     function _calc() {
115         for($i = 0; $i < 9; $i++){
116             for($j = 0; $j < 9; $j++){
117                 if(count($this->matrix[$i][$j]) == 1) {
118                     continue;
119                 }
120                 foreach($this->matrix[$i][$j] as $v){
121                     $flag = false;
122                     $t = new Sudoku($this->matrix);
123                     if(!$t->setCell($i, $j, $v)){
124                         continue;
125                     }
126                     if(!$t->_calc()){
127                         continue;
128                     }
129                     $this->matrix = $t->matrix;
130                     return true;
131                 }
132                 return false;
133             }
134         }
135         return true;
136     }
137 }
138 
139 $sd=new Sudoku;
140 $sd->calc(array(
141 array(0,5,0,0,0,6,0,9,0),
142 array(0,4,7,0,8,2,6,0,0),
143 array(0,8,0,0,0,7,0,5,2),
144 array(7,0,1,0,3,4,0,0,6),
145 array(0,3,0,0,2,0,0,8,0),
146 array(2,0,0,0,0,1,9,0,4),
147 array(4,7,0,1,0,0,0,6,0),
148 array(0,0,9,4,6,0,3,7,0),
149 array(0,1,0,2,0,0,0,4,0),
150 ));
151 
152 $sd->calc(array(
153 array(1,0,0,0,0,6,9,0,0),
154 array(0,0,0,9,0,0,0,0,5),
155 array(2,0,0,1,0,0,0,0,3),
156 array(0,0,5,3,0,7,0,2,0),
157 array(3,0,0,6,0,0,0,0,1),
158 array(0,1,0,4,0,0,8,0,0),
159 array(9,0,0,0,0,2,0,0,7),
160 array(5,0,0,0,0,9,0,0,0),
161 array(0,0,3,7,0,0,0,0,4),
162 ));
163 
164 $sd->calc(array(
165 array(7,0,0,1,0,0,0,0,5),
166 array(0,0,6,0,4,0,0,8,0),
167 array(0,0,1,0,0,0,0,0,0),
168 array(0,6,0,0,8,0,0,0,3),
169 array(0,8,0,0,0,9,0,7,0),
170 array(1,0,0,0,0,0,0,5,0),
171 array(0,0,0,0,0,0,9,0,0),
172 array(0,4,0,0,3,0,1,0,0),
173 array(9,0,0,0,0,7,0,0,2),
174 ));
175 
176 $sd->calc(array(
177 array(0,5,0,0,0,0,0,2,0),
178 array(0,0,3,1,0,0,5,0,0),
179 array(0,0,6,0,0,8,0,0,0),
180 array(6,0,0,0,0,0,0,1,0),
181 array(8,0,0,6,0,0,0,0,4),
182 array(0,3,0,0,0,9,0,0,7),
183 array(0,0,0,5,0,0,3,0,0),
184 array(0,0,8,0,0,6,9,0,0),
185 array(0,9,0,0,0,0,0,7,0),
186 ));