最短的数独解算器在Python - 它是如何工作的？ [英] Shortest Sudoku Solver in Python - How does it work?

问题描述

我是用我自己的数独解算器玩耍，并一直在寻找一些指针，以又好又快的设计，当我遇到这样的：

I was playing around with my own Sudoku solver and was looking for some pointers to good and fast design when I came across this:

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])

我自己的实现解决数独相同的方式，我解决他们在我的头上，但如何做到这一点神秘的算法的工作？

My own implementation solves Sudokus the same way I solve them in my head but how does this cryptic algorithm work?

<一个href="http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html">http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html

推荐答案

那么，你可以把事情通过固定起来的语法更容易一些：

Well, you can make things a little easier by fixing up the syntax:

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])

清理一点：

from sys import exit, argv
def r(a):
  i = a.find('0')
  if i == -1:
    exit(a)
  for m in '%d' % 5**18:
    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:])

r(argv[1])

好了，所以这个脚本需要一个命令行参数，并调用函数r就可以了。如果没有零点在该字符串，R退出并打印出它的参数。

Okay, so this script expects a command-line argument, and calls the function r on it. If there are no zeros in that string, r exits and prints out its argument.

（如果另一种类型的对象的传递，   无等同于传递零，   和任何其他对象被打印到   sys.stderr来并导致一个出口   1.特别code，   sys.exit（一些错误信息）是一个   快速的方式来退出程序时的   发生错误。看到   <一href="http://www.python.org/doc/2.5.2/lib/module-sys.html">http://www.python.org/doc/2.5.2/lib/module-sys.html)

(If another type of object is passed, None is equivalent to passing zero, and any other object is printed to sys.stderr and results in an exit code of 1. In particular, sys.exit("some error message") is a quick way to exit a program when an error occurs. See http://www.python.org/doc/2.5.2/lib/module-sys.html)

我想这意味着零对应的开放空间，并没有零点一个难题就解决了​​。再有就是那讨厌的递归EX pression。

I guess this means that zeros correspond to open spaces, and a puzzle with no zeros is solved. Then there's that nasty recursive expression.

循环有趣的是：的米'％D'％5 ** 18

为什么5 ** 18？事实证明，'％D'％5 ** 18 的计算结果为3814697265625。这已是每个数字1-9至少一次的字符串，所以也许它试图把他们每个人。事实上，它看起来这是什么 R（A [我] + M + A [1 + 1：]）是这样做的：递归调用R，与第一从该字符串数字空白填充。但是，这只是发生如先前的前pression是假的。让我们看一下：

Why 5**18? It turns out that '%d'%5**18 evaluates to '3814697265625'. This is a string that has each digit 1-9 at least once, so maybe it's trying to place each of them. In fact, it looks like this is what r(a[:i]+m+a[i+1:]) is doing: recursively calling r, with the first blank filled in by a digit from that string. But this only happens if the earlier expression is false. Let's look at that:

米[（九）％9 *（I / 9 ^焦耳/ 9）*（I / 27 ^焦耳/ 27 | I％9/3 ^Ĵ％9/3）或一个在范围[J]对于j（81）]

因此​​位置只能做，如果m不是在该怪物列表。每个元素可以是一个数字（如果第一前pression是非零）或字符（如果第一前pression为零）。 m的排除作为一个可能的替代，如果它显示为一个字符，它只能发生，如果第一八佰伴pression为零。如果是前pression零？

So the placement is done only if m is not in that monster list. Each element is either a number (if the first expression is nonzero) or a character (if the first expression is zero). m is ruled out as a possible substitution if it appears as a character, which can only happen if the first expression is zero. When is the expression zero?

它有三个部分乘以：

• （九）％9 这是零，如果i和j是9的倍数分开，即同一列。
• （I / 9 ^焦耳/ 9）这是零，如果I / 9 ==焦耳/ 9，即在同一行。
• （I / 27 ^焦耳/ 27 | I％9/3 ^Ĵ％9/3）这是零，如果两者都为零：
• • I / 27 ^ J（1）27 这是零，如果我/ 27 ==焦耳/ 27，即三排同一块
  • (i-j)%9 which is zero if i and j are a multiple of 9 apart, i.e. the same column.
  • (i/9^j/9) which is zero if i/9 == j/9, i.e. the same row.
  • (i/27^j/27|i%9/3^j%9/3) which is zero if both of these are zero:
  • • i/27^j^27 which is zero if i/27 == j/27, i.e. the same block of three rows
    • I％9/3 ^Ĵ％9/3 这是零，如果我％，9/3 ==Ĵ％9/3，即三个相同的块列
    • i%9/3^j%9/3 which is zero if i%9/3 == j%9/3, i.e. the same block of three columns

    如果任何这三个部分是零，整个前pression为零。换言之，如果i和j共享一个行，列，或者3x3的块，则j的值不能用作在我的候选为空白。啊哈！

    If any of these three parts is zero, the entire expression is zero. In other words, if i and j share a row, column, or 3x3 block, then the value of j can't be used as a candidate for the blank at i. Aha!

    from sys import exit, argv
    def r(a):
      i = a.find('0')
      if i == -1:
        exit(a)
      for m in '3814697265625':
        okay = True
        for j in range(81):
          if (i-j)%9 == 0 or (i/9 == j/9) or (i/27 == j/27 and i%9/3 == j%9/3):
            if a[j] == m:
              okay = False
              break
        if okay:
          # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
          r(a[:i]+m+a[i+1:])
    
    r(argv[1])
    

    请注意，如果没有的展示位置的工作了，R将返回和备份到别的东西可以选择的地步，所以这是一个基本的深度优先算法。

    Note that if none of the placements work out, r will return and back up to the point where something else can be chosen, so it's a basic depth first algorithm.

    不使用任何启发式，这不是特别有效。我把这个难题从维基百科（ http://en.wikipedia.org/wiki/Sudoku ）：

    Not using any heuristics, it's not particularly efficient. I took this puzzle from Wikipedia (http://en.wikipedia.org/wiki/Sudoku):

    $ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079
    534678912672195348198342567859761423426853791713924856961537284287419635345286179
    
    real    0m47.881s
    user    0m47.223s
    sys 0m0.137s
    

    附录：我会如何改写它作为一个维护程序员（此版本有大约93X加速：）

    Addendum: How I would rewrite it as a maintenance programmer (this version has about a 93x speedup :)

    import sys
    
    def same_row(i,j): return (i/9 == j/9)
    def same_col(i,j): return (i-j) % 9 == 0
    def same_block(i,j): return (i/27 == j/27 and i%9/3 == j%9/3)
    
    def r(a):
      i = a.find('0')
      if i == -1:
        sys.exit(a)
    
      excluded_numbers = set()
      for j in range(81):
        if same_row(i,j) or same_col(i,j) or same_block(i,j):
          excluded_numbers.add(a[j])
    
      for m in '123456789':
        if m not in excluded_numbers:
          # At this point, m is not excluded by any row, column, or block, so let's place it and recurse
          r(a[:i]+m+a[i+1:])
    
    if __name__ == '__main__':
      if len(sys.argv) == 2 and len(sys.argv[1]) == 81:
        r(sys.argv[1])
      else:
        print 'Usage: python sudoku.py puzzle'
        print '  where puzzle is an 81 character string representing the puzzle read left-to-right, top-to-bottom, and 0 is a blank'
    

    这篇关于最短的数独解算器在Python - 它是如何工作的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！