数独随机生成探讨

| Comments

思路

数独游戏应该很多人都玩过,规则也很简单。以前写过数独的程序解法,最近考虑了一下数独的随机生成。毕竟,每个数独一开始都是残缺的,它是怎么生成的?

如果通过正向生成的话,还需要判断剩余的空格是否能够满足数独的问题。所以,我认为应该通过反向来创建,意思是通过一个完整的数独,然后随机从上面抠取,抠得越多,表明完成的难度越大。

具体方案

问题就变成,如何生成一个完整的随机的数独?根据数独的特点,我认为可以通过一个已有的数独来生成其他数独。方案如下:

row1

  1. 首先看看上面的图案,对于一个完整的数独,1,2,3行调换次序,仍然可以保证变换后的数独是成立。 同理,456,789也是同样的道理。行是如此,列也是可以成立的,abc,def,ghi的内部调换都是可以成立的。 row2
  2. 还有上图所示的情况,123和456整三行一起调换也是可以的。同样,在列上面也是一样的道理。
  3. 还有其他一些思路,例如进行旋转操作,或者反过来的做法。

关于重复性

对于上述1,2两种方案,会不会出现重复的情况呢?我们进行下面的分析:

row3

  1. 假设A1是x,B1是y,C1是z,我们想找到某个变化可以达到同样的效果。
  2. 如果通过行变换的话,因为数独的限制,不可能有某一行在同样的列上有xyz存在,所以不能做到。
  3. 同理,如果是列变化的话,在第一行的位置也不可能再有xyz存在,所以也是不能做到的。

意思就是说,如果从某个变化开始,每做一次变换,都能得到一个新的数独,这样我们可以统计一下,一共可以有多少种变换方式。每三行中的行内的变化有6种排列,三行三行的也是有6中排列,计算上列的变换,就有 6X6X6X6X6X6X6X6=1679616种。

Comments