파이썬에서 가장 짧은 스도쿠 솔버-어떻게 작동합니까?

파이썬에서 가장 짧은 스도쿠 솔버-어떻게 작동합니까?

---

나는 내 자신의 스도쿠 솔버를 가지고 놀고 있었고 이것을 발견했을 때 좋고 빠른 디자인에 대한 몇 가지 포인터를 찾고 있었다.

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을 호출합니다. 해당 문자열에 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가 행, 열 또는 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

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'

---

unobfuscating it:

def r(a):
    i = a.find('0') # returns -1 on fail, index otherwise
    ~i or exit(a) # ~(-1) == 0, anthing else is not 0
                  # thus: if i == -1: exit(a)
    inner_lexp = [ (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)]  # r appears to be a string of 81 
                                        # characters with 0 for empty and 1-9 
                                        # otherwise
    [m in inner_lexp or r(a[:i]+m+a[i+1:]) for m in'%d'%5**18] # recurse
                            # trying all possible digits for that empty field
                            # if m is not in the inner lexp

from sys import *
r(argv[1]) # thus, a is some string

So, we just need to work out the inner list expression. I know it collects the digits set in the line -- otherwise, the code around it makes no sense. However, I have no real clue how it does that (and Im too tired to work out that binary fancyness right now, sorry)

---

r(a) is a recursive function which attempts to fill in a 0 in the board in each step.

i=a.find('0');~i or exit(a) is the on-success termination. If no more 0 values exist in the board, we're done.

m is the current value we will try to fill the 0 with.

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)] evaluates to truthy if it is obivously incorrect to put m in the current 0. Let's nickname it "is_bad". This is the most tricky bit. :)

is_bad or r(a[:i]+m+a[i+1:] is a conditional recursive step. It will recursively try to evaluate the next 0 in the board iff the current solution candidate appears to be sane.

for m in '%d'%5**18 enumerates all the numbers from 1 to 9 (inefficiently).

---

A lot of the short sudoku solvers just recursively try every possible legal number left until they have successfully filled the cells. I haven't taken this apart, but just skimming it, it looks like that's what it does.

---

The code doesn't actually work. You can test it yourself. Here is a sample unsolved sudoku puzzle:

807000003602080000000200900040005001000798000200100070004003000000040108300000506

You can use this website (http://www.sudokuwiki.org/sudoku.htm), click on import puzzle and simply copy the above string. The output of the python program is: 817311213622482322131224934443535441555798655266156777774663869988847188399979596

which does not correspond to the solution. In fact you can already see a contradiction, two 1s in the first row.

참고URL : https://stackoverflow.com/questions/201461/shortest-sudoku-solver-in-python-how-does-it-work