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

조금 정리 :

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을 호출합니다. 해당 문자열에 0이 없으면 r이 종료되고 인수를 인쇄합니다.

(다른 유형의 객체가 전달되면 None은 0을 전달하는 것과 동일하며 다른 객체는 sys.stderr에 인쇄되고 종료 코드 1이됩니다. 특히 sys.exit ( “some error message”)는 오류 발생시 프로그램을 종료하는 빠른 방법.
http://www.python.org/doc/2.5.2/lib/module-sys.html 참조 )

이것은 0이 열린 공간에 해당하고 0이없는 퍼즐이 해결된다는 것을 의미한다고 생각합니다. 그런 다음 불쾌한 재귀 표현이 있습니다.

루프는 흥미 롭습니다. 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 인 경우에만 발생할 수 있습니다. 식이 언제 0입니까?

곱해지는 세 부분이 있습니다.

• (i-j)%9 i와 j가 9의 배수, 즉 동일한 열이면 0입니다.
• (i/9^j/9) i / 9 == j / 9, 즉 동일한 행이면 0입니다.
• (i/27^j/27|i%9/3^j%9/3) 둘 다 0이면 0입니다.
• • i/27^j^27 i / 27 == j / 27이면 0, 즉 3 개 행의 동일한 블록
• • i%9/3^j%9/3 i % 9 / 3 == j % 9 / 3 인 경우 0입니다. 즉, 3 개 열의 동일한 블록

이 세 부분 중 하나가 0이면 전체 표현식은 0입니다. 즉, i와 j가 행, 열 또는 3×3 블록을 공유하면 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'