Najkrótszy Sudoku Solver w Pythonie - jak to działa?

Bawiłem się własnym solwerem Sudoku i szukałem wskazówek do dobrego i szybkiego projektowania, kiedy natknąłem się na to:

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

Moja własna implementacja rozwiązuje Sudokus w taki sam sposób, w jaki rozwiązuję je w mojej głowie, ale jak działa ten tajemniczy algorytm?

http://scottkirkwood.blogspot.com/2006/07/shortest-sudoku-solver-in-python.html

Cóż, możesz trochę ułatwić, poprawiając składnię:

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

Trochę sprzątania:

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

Okej, więc ten skrypt oczekuje argumentu wiersza poleceń i wywołuje na nim funkcję r. Jeśli w tym łańcuchu nie ma zer, r kończy działanie i wyświetla swój argument.

(Jeśli przekazano inny typ obiektu, None jest równoznaczne z przekazaniem zera, a każdy inny obiekt jest wypisywany do sys.stderr i skutkuje kodem zakończenia 1. W szczególności sys.exit ("jakiś komunikat o błędzie") jest szybki sposób na zamknięcie programu w przypadku wystąpienia błędu. Zobacz http://www.python.org/doc/2.5.2/lib/module-sys.html )

Myślę, że oznacza to, że zera odpowiadają otwartej przestrzeni, a łamigłówka bez zer jest rozwiązana. Potem jest to okropne, rekurencyjne wyrażenie.

Pętla jest interesująca: for m in'%d'%5**18

Dlaczego 5 ** 18? Okazuje się, że '%d'%5**18ocenia się do '3814697265625'. Jest to ciąg, który ma każdą cyfrę 1-9 przynajmniej raz, więc może próbuje umieścić każdą z nich. W rzeczywistości wygląda na to, co r(a[:i]+m+a[i+1:])robi: rekurencyjne wywołanie r, z pierwszym odstępem wypełnionym cyfrą z tego ciągu. Ale dzieje się tak tylko wtedy, gdy wcześniejsze wyrażenie jest fałszywe. Spójrzmy na to:

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

Tak więc umieszczanie jest wykonywane tylko wtedy, gdy m nie ma na liście potworów. Każdy element jest liczbą (jeśli pierwsze wyrażenie jest różne od zera) lub znakiem (jeśli pierwsze wyrażenie ma wartość zero). m jest wykluczone jako możliwe podstawienie, jeśli występuje jako znak, co może się zdarzyć tylko wtedy, gdy pierwsze wyrażenie ma wartość zero. Kiedy wyrażenie ma wartość zero?

Ma trzy części, które są pomnożone:

• (i-j)%9 czyli zero, jeśli i i j są od siebie wielokrotnością 9, czyli ta sama kolumna.
• (i/9^j/9) czyli zero, jeśli i / 9 == j / 9, czyli ten sam wiersz.
• (i/27^j/27|i%9/3^j%9/3) czyli zero, jeśli oba są zerowe:
• • i/27^j^27 czyli zero, jeśli i / 27 == j / 27, czyli ten sam blok trzech wierszy
• • i%9/3^j%9/3 co jest zerem, jeśli i% 9/3 == j% 9/3, czyli ten sam blok trzech kolumn

Jeśli którakolwiek z tych trzech części wynosi zero, całe wyrażenie wynosi zero. Innymi słowy, jeśli i i j mają wspólny wiersz, kolumnę lub blok 3x3, to wartość j nie może być użyta jako kandydat na puste miejsce w 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])

Zwróć uwagę, że jeśli żadne z miejsc docelowych nie zadziała, r powróci i powróci do punktu, w którym można wybrać coś innego, więc jest to podstawowy algorytm głębokości.

Bez heurystyki nie jest to szczególnie wydajne. Wziąłem tę układankę z Wikipedii ( http://en.wikipedia.org/wiki/Sudoku ):

$ time python sudoku.py 530070000600195000098000060800060003400803001700020006060000280000419005000080079
534678912672195348198342567859761423426853791713924856961537284287419635345286179

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

Dodatek: Jak przepisałbym to jako programista konserwacyjny (ta wersja ma około 93x przyspieszenie :)

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'

odszyfrowanie go:

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

Więc musimy tylko wypracować wyrażenie listy wewnętrznej. Wiem, że zbiera cyfry ustawione w linii - w przeciwnym razie kod wokół niego nie ma sensu. Jednak nie mam pojęcia, jak to się dzieje (i jestem zbyt zmęczony, by teraz wypracować tę binarną fantazję, przepraszam)

r(a)to funkcja rekurencyjna, która próbuje wypełnić 0tablicę w każdym kroku.

i=a.find('0');~i or exit(a)jest zakończeniem sukcesu. Jeśli 0na tablicy nie ma już żadnych wartości, to wszystko.

mjest bieżącą wartością, którą spróbujemy wypełnić 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)]ocenia jako zgodne z prawdą, jeśli wprowadzenie mprądu jest oczywiste 0. Nazwijmy to „is_bad”. To jest najtrudniejsza część. :)

is_bad or r(a[:i]+m+a[i+1:]jest warunkowym krokiem rekurencyjnym. Będzie rekurencyjnie próbować ocenić następny 0 na tablicy, jeśli obecny kandydat na rozwiązanie wydaje się rozsądny.

for m in '%d'%5**18 wylicza wszystkie liczby od 1 do 9 (nieefektywnie).

Wiele krótkich rozwiązujących sudoku po prostu rekurencyjnie wypróbowuje każdą możliwą dozwoloną liczbę, dopóki nie wypełnią komórek. Nie rozbierałem tego na części, ale przeglądając to, wygląda na to, że tak właśnie działa.

Kod w rzeczywistości nie działa. Możesz to sprawdzić samodzielnie. Oto przykład nierozwiązanej łamigłówki sudoku:

807000003602080000000200900040005001000798000200100070004003000000040108300000506

Możesz skorzystać z tej strony ( http://www.sudokuwiki.org/sudoku.htm ), kliknąć import puzzle i po prostu skopiować powyższy ciąg. Dane wyjściowe programu w języku Python to: 8173112136224823221312249344435441555798655266156777774663869988847188399979596

co nie odpowiada rozwiązaniu. W rzeczywistości widać już sprzeczność, dwie jedynki w pierwszym rzędzie.