提到随机生成, 不由有2种随机算法映入脑海:
(1)固定的随机: 在固定的位置, 随机填入随机生成的数(1-9之间)
(2)随机的随机: 在随机的位置, 随机填入随机生成的数(1-9之间)
>>> 把(1)的思路贯彻下去, 就有了:
在{1,1}的位置填入i(随机数), 在{1,2}的位置填入j(随机数, 受已填入的数限制), 在{1,3}的位置填入..., 在{9,9}的位置填入m(随机数, 但是由于只有一种可能了).
(注: {i, j}表示在第i行, 第j列)
试着分析一下,这种状况很容易一下子就夭折了...
例如, 如果不幸的随机到
看来, 在这样的情况下, 能存活到最后的随机题目实在少之又少...
>>> 把(2)的思路贯彻下去, 又有了:
在{i0, i1}的位置(随机位置)填入i(随机数), 在{j0,j1}的位置(随机位置, 受已填入位置的限制)填入j(随机数, 受已填入的数限制), ...
唉, 不用分析了, 夭折的可能性肯定不小...虽然不是女生, 在这里还是该说"直觉"了 --- 一个程序员分析问题时该有的直觉....
那么, 怎么办呢? 第一种方法可控性强(易于控制), 第二种方法易于变通... 两种方法结合起来怎么样呢?
先在特定的位置随机一些数, 然后开始有限制的随机...为了降低失败的可能性, 后期的"随机的随机"应用"'有限制随机'的随机"(既在有最少可填入数的位置随机填入)...
那么该先随机哪些特定的位置而效果最好呢?
^_^为了让大家不晕下去, 我还是直接写出算法吧
步骤1: 在第一行, 第一列, 和中心的3X3方格 依次随机填入随机产生的数
步骤2: 检查每个未被填入的位置, 看它能填入的数有多少(假设为n个). 选择n最小的位置随机填入可以被填入的数(若最小的n=1, 那么就填入吧; 若>1, 随机填入; 若=0, 恭喜你, 这次随机可以废了)
步骤3: 重复步骤2直到得到一个完整九宫或者无解为止(也就是"废")了. 若得到完整九宫, 到步骤4; 若无解, 重复步骤1-3直到得到完整九宫为止.
步骤4: 简化得到的完整九宫
理论上讲, 这样的随机存在永远得不到完整九宫的可能性. 但事实上, 在10000次的实验结果中发现: 平均1.08次重复可以得到一个完整九宫. 大多数情况下1次就能搞定, 最坏的情况为4次搞定. 也就是说: 这种算法, 在编程中, 完全是可以被接受的. PC上行, 手机上也行...
No comments:
Post a Comment