我正在玩我自己的数独解算器,并正在寻找一些指针,以良好和快速的设计时,我遇到了这个:
def r(a):i=a.find('0');~i or exit(a);[m
in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for
j in range(81)]or r(a[:i]+m+a[i+1:])for m in'%d'%5**18]
from sys import*;r(argv[1])
我自己的实现解决数独问题的方式和我在脑海中解决它们的方式一样,但这个神秘的算法是如何工作的呢?
http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html
5条答案
按热度按时间sxpgvts31#
那么,您可以通过修改语法来使事情变得简单一些:
稍微清理一下:
好的,这个脚本需要一个命令行参数,并在其上调用函数r,如果字符串中没有零,r退出并打印出它的参数。
(If传递另一种类型的对象,None相当于传递零,任何其他对象都将打印到sys.stderr,并导致退出代码1。特别是,sys.exit(“某个错误消息”)是发生错误时退出程序的快速方法。请参见http://www.python.org/doc/2.5.2/lib/module-sys.html)
我想这意味着零对应于开放空间,一个没有零的谜题就解决了,然后就是那个讨厌的递归表达式。
这个循环很有趣:
for m in'%d'%5**18
为什么是5**18呢?结果
'%d'%5**18
的计算结果是'3814697265625'
。这是一个字符串,其中每个数字1-9至少出现一次,所以它可能试图放置它们中的每一个。实际上,看起来r(a[:i]+m+a[i+1:])
是这样做的:递归地调用r,用字符串中的数字填充第一个空格,但这只在前面的表达式为假时发生,让我们来看一下:m in [(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3) or a[j] for j in range(81)]
因此,只有当m不在那个怪物列表中时,才能进行替换。每个元素要么是数字(如果第一个表达式为非零),要么是字符(如果第一个表达式为零)。如果m以字符的形式出现,就排除了它作为可能的替换。只有当第一个表达式为零时,才可能发生这种情况。表达式何时为零?
它有三个相乘的部分:
(i-j)%9
,如果i和j相隔9的倍数,即在同一列,则其为零。(i/9^j/9)
,如果i/9 == j/9,即相同的行,则其为零。(i/27^j/27|i%9/3^j%9/3)
,如果这两个都为零,则为零:i/27^j^27
,如果i/27 == j/27,即三行的相同块,则为零i%9/3^j%9/3
,如果i%9/3 == j%9/3,即三列的相同块,则为零如果这三个部分中的任何一个为零,则整个表达式为零。换句话说,如果i和j共享一行、一列或3x 3块,则j的值不能用作i处空格的候选项。啊哈!
注意,如果没有一个放置成功,r将返回到可以选择其他东西的点,所以这是一个基本的深度优先算法。
没有使用任何启发式,它不是特别有效。我从维基百科(http://en.wikipedia.org/wiki/Sudoku)这个难题:
附录:作为一名维护程序员,我将如何重写它(这个版本的加速比大约为93倍:)
6yoyoihd2#
使其清晰:
所以,我们只需要计算出内部列表表达式。我知道它收集行中设置的数字--否则,它周围的代码就没有意义了。然而,我不知道它是如何做到这一点的(对不起,我现在太累了,无法计算出二进制的幻想)
nbysray53#
r(a)
是一个递归函数,它尝试在每一步中填充电路板中的0
。i=a.find('0');~i or exit(a)
是成功时终止。如果板中不再存在0
值,则我们完成。m
是我们将尝试填充0
的当前值。如果将
m
放入当前0
明显不正确,则m in[(i-j)%9*(i/9^j/9)*(i/27^j/27|i%9/3^j%9/3)or a[j]for j in range(81)]
的值为truthy。我们将其命名为“is_bad”。这是最棘手的一点。:)is_bad or r(a[:i]+m+a[i+1:]
是一个条件递归步骤。如果当前候选解看起来是正常的,它将递归地尝试评估棋盘中的下一个0
。for m in '%d'%5**18
枚举从1到9的所有数字(效率低下)。twh00eeo4#
很多的短数独解算器只是递归地尝试每一个可能的法律的数字,直到他们成功地填满了单元格,我没有把它拆开,只是略读一下,看起来它就是这样做的。
7uhlpewt5#
代码实际上并不工作。你可以自己测试一下。下面是一个未解数独谜题的例子:
807000003602080000000200900040005001000798000200100070004003000000040108300000506
你可以使用这个网站(http://www.sudokuwiki.org/sudoku.htm),点击import puzzle,简单地复制上面的字符串,python程序的输出是:817311213622482322131224934443535441555798655266156777774663869988847188399979596
这与解不对应。事实上你已经可以看到一个矛盾,第一行有两个1。