php 数独求解,php求解数独

喜欢ヅ旅行 2023-01-16 04:47 111阅读 0赞

<?php /\*     php数独求解，时间大约在1分钟 \*/ $nums\[0\] = array(0, 5, 0, 0, 1, 0, 0, 0, 9, ); $nums\[1\] = array(0, 1, 0, 0, 0, 0, 6, 0, 0, ); $nums\[2\] = array(2, 0, 0, 0, 9, 0, 0, 0, 0, ); $nums\[3\] = array(0, 4, 0, 0, 0, 3, 7, 0, 0, ); $nums\[4\] = array(0, 2, 0, 0, 0, 0, 0, 8, 0, ); $nums\[5\] = array(0, 0, 5, 7, 0, 0, 0, 2, 0, ); $nums\[6\] = array(0, 0, 0, 0, 5, 0, 0, 0, 1, ); $nums\[7\] = array(0, 0, 3, 0, 0, 0, 0, 4, 0, ); $nums\[8\] = array(9, 0, 0, 0, 8, 0, 0, 3, 0, ); findShuDu($nums); exit; function findShuDu($arr) \{   $paramArray = array($arr);   //向$paramArray增加数组, 参数用引用传递   cycleArray($paramArray);   $resultArray = $paramArray\[count($paramArray) - 1\];   echo "\\n";   showArray($arr);   echo "\\n";   showArray($resultArray);   if (calcArray($resultArray))   \{     //echo 'success' . "\\n";   \}   else   \{     echo 'fail' . "\\n";   \} \} //验证结果是否有效 function calcArray($arr) \{   for($i = 0; $i < 9; $i ++)   \{     $sum1 = 0;     $sum2 = 0;     for($j = 0; $j < 9; $j ++)     \{       $sum1 += $arr\[$i\]\[$j\];       $sum2 += $arr\[$j\]\[$i\];     \}     if (         $sum1 != 45 || $sum2 != 45          )     \{       echo 'check fail: ' . $i . ' ' . $j . "\\n";       return false;     \}   \}   return true; \} //显示结果数组 function showArray($arrLast) \{   for($i = 0; $i < 9; $i ++)   \{     //echo "array(";     for($j = 0; $j < 9; $j ++)     \{       echo $arrLast\[$i\]\[$j\];       echo ', ';     \}     echo "\\n";     //echo "),\\n";   \} \} //获取一个位置有效的可选数字的数组 function getPositionAvailArray($arr) \{   $arrNew = array();   for($i = 0; $i < 9; $i ++)   \{     for($j = 0; $j < 9; $j ++)     \{       //不为0的位置跳过       if ($arr\[$i\]\[$j\] > 0)       \{         continue;       \}       //可用数字       $hv = array(1, 2, 3, 4, 5, 6, 7, 8, 9);       //取消行已有数字       for($k = 0; $k < 9; $k ++)       \{         $a = $arr\[$i\]\[$k\];         if ($a > 0)         \{           $key = array\_search($a, $hv);           if (false !== $key)           \{             //$key 为false时不能用unset，不然会出错             unset($hv\[$key\]);           \}         \}       \}       //取消列已有数字       for($k = 0; $k < 9; $k ++)       \{         $a = $arr\[$k\]\[$j\];         if ($a > 0)         \{           $key = array\_search($a, $hv);           if (false !== $key)           \{             unset($hv\[$key\]);           \}         \}       \}       //取消小方块中已有数字       $otherI1 = intval($i / 3);       $otherJ1 = intval($j / 3);       $otherI = $otherI1 \* 3;       $otherJ = $otherJ1 \* 3;       for ($ii = $otherI; $ii 0)           \{             $key = array\_search($a, $hv);             if (false !== $key)             \{               unset($hv\[$key\]);             \}           \}         \}       \}       if (empty($hv))       \{         /\*              echo '出现无效数字 ';              echo sprintf("行: %s列: %s\\n", $i + 1, $j + 1);              showArray($arr);          \*/         return false;       \}       $arrNew\[$i\]\[$j\] = $hv;     \}   \}   return $arrNew; \} //递归循环得到有效数组,参数用引用传递，每次得到有效数组后增加到最后 function cycleArray(&$numArray) \{   //取最后一个数组   $arr = $numArray\[count($numArray) - 1\];   $info = getPositionAvailArray($arr);   if (false === $info)   \{     return false;   \}   $positionI = -1;   $positionJ = -1;   $availCountMin = 9;   //找出可选数字最少的位置   for($i = 0; $i < 9; $i ++)   \{     for($j = 0; $j < 9; $j ++)     \{       $availCount = count($info\[$i\]\[$j\]);       if ($availCount > 0 && $availCount < $availCountMin)       \{         $positionI = $i;         $positionJ = $j;         $availCountMin = $availCount;       \}     \}   \}   if ($positionI >= 0 && $positionJ >= 0)   \{     $newInfo = $info\[$positionI\]\[$positionJ\];     foreach ($newInfo as $key => $value)     \{       echo sprintf("\[%s\]\[%s\]: %s;\\t", $positionI, $positionJ, $value);       $arr\[$positionI\]\[$positionJ\] = $value;       //unset的bug存在的地方, 如果用\[\]构建数组, 同时之前用unset取消一些元素，那么key值可能并不是按顺序递增，所以用count()得到数组元素个数来作为key值.被注释的代码是有问题的代码.       //var\_dump(array\_keys($numArray));       //$numArray\[\] = $arr;       //var\_dump(array\_keys($numArray));       //------------------------------       $numArray\[count($numArray)\] = $arr;       $ret = cycleArray($numArray);       if ($ret)       \{         return true;       \}       else       \{         //取消最后一个数组元素         unset($numArray\[count($numArray) - 1\]);       \}     \}     return false;   \}   return true; \}