[解決済み] Pythonで最短数独ソルバー - どのように動作するのですか？

質問

私は自分自身の数独ソルバーで遊んでいて、良い、高速な設計へのいくつかのポインタを探していたとき、これに出会いました。

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

どのように解決するのですか？

まあ、構文を修正することで、少しは楽になります。

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は終了し、その引数をプリントアウトします。

(別の種類のオブジェクトが渡された場合。 Noneはゼロを渡すのと同じです。 それ以外のオブジェクトは に出力され、終了コード1が返されます。 のコードになります。特に sys.exit("some error message")は、特に は、エラーが発生したときにプログラムを終了させる素早い方法です。 は、エラーが発生したときにプログラムを終了させる簡単な方法です。参照 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がそのモンスターリストにない場合にのみ、配置が行われる。 各要素は数字（最初の式が0でない場合）か文字（最初の式が0の場合）です。mは文字として現れた場合、代入可能なものとして除外されますが、これは最初の式が0の場合にのみ起こり得ます。 式がゼロである場合は？

乗算される3つの部分を持っています。

• (i-j)%9 で、i と j が 9 の倍数離れている場合、つまり同じ列の場合は 0 になります。
• (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の場合は0、つまり同じ3行のブロックです。
• • i%9/3^j%9/3 i%9/3 == j%9/3 の場合は 0、つまり同じ 3 列のブロックです。

これら3つの部分のいずれかが0であれば、式全体が0となります。 言い換えれば、i と j が行、列、または 3x3 のブロックを共有している場合、j の値は i の空白の候補として使用できません。

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は戻って他のものが選択できるところまで戻るので、基本的な深さ優先のアルゴリズムと言えます。

ヒューリスティックを使用しないので、特に効率的ではありません。 このパズルはWikipediaから引用しました( http://en.wikipedia.org/wiki/Sudoku ):

$ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079
534678912672195348198342567859761423426853791713924856961537284287419635345286179

real    0m47.881s
user    0m47.223s
sys 0m0.137s

追記：メンテナンスプログラマとしての私ならどう書き換えるか（このバージョンでは約93倍のスピードアップを実現しました :)

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'