Monthly Archives: 二月 2021

Hello World

一个生成数独数组的暴力算法

这是一个通过随机数生成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/数独发生器