数独求解程序 php版
转载请注明出处：
1 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 ));