这是一个通过随机数生成9*9矩阵,然后判断是否符合数独条件的算法,成功率大概在0.3%
这个方法比较暴力,生成随机数时没有做过多的判断,不过。。。可用,php,30秒内跑50000次毫无压力
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 | //入口方法,循环调取t1 function t0(){ $dr = []; $poolCount = 50000; for($i = 0; $i < $poolCount; $i++){ $dr[$i] = t1($i); } $succ = 0; //打印成功数组 foreach ($dr as $j => $sar){ if(!$sar) continue; $succ++; echo $j.':<br>'; foreach($sar as $ar){ echo implode(', ', $ar).'<br> '; } } echo $poolCount.'次循环,共'.$succ.'成功,成功率 '.(round(($succ*10000)/$poolCount)/100).'% :<br>'; exit; } //核心方法,成功生成符合条件的数独数组,返回数组 //如不成功,返回false private function t1($poolNo){ //准备记录速度数组的二位数组,初始化都是0 $sar = build2ArrZero(9); $don = 0;//当前循环次数 //数独数组生成思路: 按格填数,单个格填数失败,退出 $sl = [1, 2, 3, 4, 5, 6, 7, 8, 9]; $sx = build2ArrZero(9+1); //按行,$x, 标记每个数有没有出现过 $sy = build2ArrZero(9+1); //按行,$y, 标记每个数有没有出现过 $s33 = [];//标记小33矩阵是否出现过 for($x = 0; $x < 9; $x++){ for($y = 0; $y < 9; $y++){ $dx = $x > 2 ? ($x > 5 ? 6 : 3) : 0;//小33矩阵范围判断 $dy = $y > 2 ? ($y > 5 ? 6 : 3) : 0; if(empty($s33[$dx.'-'.$dy])){ $s33[$dx.'-'.$dy] = build2ArrZero(10)[0]; } for($nsn = 0; ; $nsn++){ if($don > 10000) break;//循环次数限制 $don++; if($nsn > 12){ echo '第'.$poolNo.'次----, ', $x, ', ', $y.',过循环出错, 循环次数:', $don, '<br>'; return false; //随机两次、累加10次,在不成功,既视为此次循环失败 退出 }else if($nsn > 2){ $n = (($n+1)%9)+1; }else{ $n = (rand(1, 9999)%9)+1; } $backRea = ''; //行列检查 if($sx[$x][$n] == 1){ // echo $poolNo.'--x, ', $don, ', ', $x, ', ', $y, ', ', $n.',$x跳出', '<br>'; continue; } if($sy[$y][$n] == 1){ // echo $poolNo.'--y, ', $don, ', ', $x, ', ', $y, ', ', $n.',$y跳出', '<br>'; continue; } //小33矩阵检查 if($s33[$dx.'-'.$dy][$n] == 1){ // echo $poolNo, '--', $dx.'-'.$dy, ', ', $n.',小 3-3 检查跳出', '<br>'; continue; } $sar[$x][$y] = $n; $sx[$x][$n] = 1; $sy[$y][$n] = 1; $s33[$dx.'-'.$dy][$n] = 1; break; } } } echo $poolNo.'--------------------成功', ', 循环次数:', $don, '<br>'; return $sar; } //辅助方法,生成00数组 function build2ArrZero($llen){ for($i = 0; $i < $llen; $i++){ $sar[$i] = []; for($j = 0; $j < $llen; $j++){ $sar[$i][] = 0; } } return $sar; } |
转载请注明出处:http://www.jiangkl.com/2021/02/数独发生器