PHP实现的数独求解问题示例
本文实例讲述了PHP实现的数独求解问题。分享给大家供大家参考，具体如下：
一、数独问题描述：
对于给出的数字二维数组，要求每行每列的数字不能重复。
二、实现代码：
clear();
}else{
$this->matrix=$arr;
}
}
functionclear(){
for($i=0;$i<9;$i++){
for($j=0;$j<9;$j++){
$this->matrix[$i][$j]=array();
for($k=1;$k<=9;$k++){
$this->matrix[$i][$j][$k]=$k;
}
}
}
}
functionsetCell($row,$col,$value){
$this->matrix[$row][$col]=array($value=>$value);
//row
for($i=0;$i<9;$i++){
if($i!=$col){
if(!$this->removeValue($row,$i,$value)){
returnfalse;
}
}
}
//col
for($i=0;$i<9;$i++){
if($i!=$row){
if(!$this->removeValue($i,$col,$value)){
returnfalse;
}
}
}
//square
$rs=intval($row/3)*3;
$cs=intval($col/3)*3;
for($i=$rs;$i<$rs+3;$i++){
for($j=$cs;$j<$cs+3;$j++){
if($i!=$row&&$j!=$col){
if(!$this->removeValue($i,$j,$value))
returnfalse;
}
}
}
returntrue;
}
functionremoveValue($row,$col,$value){
$count=count($this->matrix[$row][$col]);
if($count==1){
$ret=!isset($this->matrix[$row][$col][$value]);
return$ret;
}
if(isset($this->matrix[$row][$col][$value])){
unset($this->matrix[$row][$col][$value]);
if($count-1==1){
return$this->setCell($row,$col,current($this->matrix[$row][$col]));
}
}
returntrue;
}
functionset($arr){
for($i=0;$i<9;$i++){
for($j=0;$j<9;$j++){
if($arr[$i][$j]>0){
$this->setCell($i,$j,$arr[$i][$j]);
}
}
}
}
functiondump(){
for($i=0;$i<9;$i++){
for($j=0;$j<9;$j++){
$c=count($this->matrix[$i][$j]);
if($c==1){
echo"".current($this->matrix[$i][$j])."";
}else{
echo"(".$c.")";
}
}
echo"\n";
}
echo"\n";
}
functiondumpAll(){
for($i=0;$i<9;$i++){
for($j=0;$j<9;$j++){
echoimplode('',$this->matrix[$i][$j]),"\t";
}
echo"\n";
}
echo"\n";
}
functioncalc($data){
$this->clear();
$this->set($data);
$this->_calc();
$this->dump();
}
function_calc(){
for($i=0;$i<9;$i++){
for($j=0;$j<9;$j++){
if(count($this->matrix[$i][$j])==1){
continue;
}
foreach($this->matrix[$i][$j]as$v){
$flag=false;
$t=newSudoku($this->matrix);
if(!$t->setCell($i,$j,$v)){
continue;
}
if(!$t->_calc()){
continue;
}
$this->matrix=$t->matrix;
returntrue;
}
returnfalse;
}
}
returntrue;
}
}
$sd=newSudoku;
$sd->calc(array(
array(0,5,0,0,0,6,0,9,0),
array(0,4,7,0,8,2,6,0,0),
array(0,8,0,0,0,7,0,5,2),
array(7,0,1,0,3,4,0,0,6),
array(0,3,0,0,2,0,0,8,0),
array(2,0,0,0,0,1,9,0,4),
array(4,7,0,1,0,0,0,6,0),
array(0,0,9,4,6,0,3,7,0),
array(0,1,0,2,0,0,0,4,0),
));
$sd->calc(array(
array(1,0,0,0,0,6,9,0,0),
array(0,0,0,9,0,0,0,0,5),
array(2,0,0,1,0,0,0,0,3),
array(0,0,5,3,0,7,0,2,0),
array(3,0,0,6,0,0,0,0,1),
array(0,1,0,4,0,0,8,0,0),
array(9,0,0,0,0,2,0,0,7),
array(5,0,0,0,0,9,0,0,0),
array(0,0,3,7,0,0,0,0,4),
));
$sd->calc(array(
array(7,0,0,1,0,0,0,0,5),
array(0,0,6,0,4,0,0,8,0),
array(0,0,1,0,0,0,0,0,0),
array(0,6,0,0,8,0,0,0,3),
array(0,8,0,0,0,9,0,7,0),
array(1,0,0,0,0,0,0,5,0),
array(0,0,0,0,0,0,9,0,0),
array(0,4,0,0,3,0,1,0,0),
array(9,0,0,0,0,7,0,0,2),
));
$sd->calc(array(
array(0,5,0,0,0,0,0,2,0),
array(0,0,3,1,0,0,5,0,0),
array(0,0,6,0,0,8,0,0,0),
array(6,0,0,0,0,0,0,1,0),
array(8,0,0,6,0,0,0,0,4),
array(0,3,0,0,0,9,0,0,7),
array(0,0,0,5,0,0,3,0,0),
array(0,0,8,0,0,6,9,0,0),
array(0,9,0,0,0,0,0,7,0),
));
?>
运行结果如下：
152346798 947582613 386917452 791834526 534629187 268751934 473198265 829465371 615273849 137256948 468973215 259184673 685317429 394628751 712495836 946532187 571849362 823761594 738196425 296345781 451278396 569784213 382519674 174623859 627451938 845932167 913867542 951367428 783142569 246958731 629475813 875613294 134289657 467591382 318726945 592834176
更多关于PHP相关内容感兴趣的读者可查看本站专题：《PHP数据结构与算法教程》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《php程序设计算法总结》、《php排序算法总结》、《PHP常用遍历算法与技巧总结》、《PHP数学运算技巧总结》及《php常见数据库操作技巧汇总》
希望本文所述对大家PHP程序设计有所帮助。