06 mar Marzec 06, 2011

Sudoku – algorytm rozwiązujący łamigłówkę

lukasz 0 Algorytmy, hack lang, Ruby

Zaprezentuję dzisiaj program łamiący sudoku. Co prawda nawet na wikipedii jest link do metody łamiącej (podobno) każde sudoku, lecz ja mam największą frajdę, jak sobie samemu coś wymyślę i to działa póżniej. Algorytm powinien sobie radzić z każdym sudoku które da się rozwiązać, aczkolwiek głowy nie daje i mogą się znaleźć takie, których nie rozwiążę. Testowałem na ponad 10 niby najtrudniejszych i radził sobie bez problemu.

Początkowo zacząłem pisać skrypt w JavaScript pod przeglądarką. Okazało się, że stos jest za płytki albo są jakieś inne ograniczenia ilości zagłębień bo nie pozwalały mi browsery na wykonanie wymaganych obliczeń. Więc przepisałem kod na ruby. Poszło całkiem gładko :)

Używam systemu Linux – Ubuntu 10.10 – ruby 1.9.2p136. Jeśli chcesz mieć 100% pewności, że wszystko zadziała tak jak w opisie, ogarnij podobną konfigurację, albo przynajmniej tą samą wersję rubiego. A więc do dzieła!


Wersje Alternatywne:

Rekurencyjna implementacja w hack lang


Tworzymy klasę sudoku, która zajmie się rozwiązywaniem łamigłówki

class Sudoku
end

Na początek stworzymy metodę konstruktora, który stworzy nam w pamięci planszę do gry

  # konstruktor
  def initialize
    # stwórz tablicę 10x10, będziemy korzystać dla wygody z indeksów 1..9 x 1..9
    @b = Array.new(10)
    @b.map! { Array.new(10) }
    (1..9).each do |i|
      (1..9).each do |j|
        # w każdym polu będzie numer 1..9, 0 to pusty, oraz lista możliwości 1..9
        @b[i][j] = { :number => 0, :list => (1..9).to_a }
      end
    end
  end

W zmiennej prywatnej klasy Sudoku @b (board) trzymamy teraz stan planszy. Każde z 9×9=81 pól pamięta pod hashem :number cyfrę od 1..9 lub 0 oznaczające jej brak, oraz pod hashem :list listę wszystkich możliwych wartości dla pola (również od 1 do 9)

pierwszą metodą która będzie potrzebna jest to_s zwracająca łańcuch tekstowy z polami planszy sudoku. Pozwoli nam to na wypisywanie stanu planszy na wyjście.

  # nasza plansza jako łańcuch znaków
  def to_s
    s = ''
    (1..9).each do |i|
      (1..9).each do |j|
        s += ' ' if j%3 == 1 and j != 1
        n = @b[i][j][:number]
        s += n == 0 ? '.' : n.to_s
      end
      s += "\n" if i%3 == 0 and i != 9
      s += "\n";
    end
    return s
  end

Spróbuj teraz uruchomić poniższy kod:

class Sudoku
  # konstruktor
  def initialize
    # stwórz tablicę 10x10, będziemy korzystać dla wygody z indeksów 1..9 x 1..9
    @b = Array.new(10)
    @b.map! { Array.new(10) }
    (1..9).each do |i|
      (1..9).each do |j|
        # w każdym polu będzie numer 1..9, 0 to pusty, oraz lista możliwości 1..9
        @b[i][j] = { :number => 0, :list => (1..9).to_a }
      end
    end
  end
 
  # nasza plansza jako łańcuch znaków
  def to_s
    s = ''
    (1..9).each do |i|
      (1..9).each do |j|
        s += ' ' if j%3 == 1 and j != 1
        n = @b[i][j][:number]
        s += n == 0 ? '.' : n.to_s
      end
      s += "\n" if i%3 == 0 and i != 9
      s += "\n";
    end
    return s
  end
end
 
puts Sudoku.new.to_s

Powinieneś uzyskać coś takiego:

... ... ...
... ... ...
... ... ...
 
... ... ...
... ... ...
... ... ...
 
... ... ...
... ... ...
... ... ...

Te kropki to zera, czyli puste pola. Wprowadziłem kropki jako, że znaki zapytania strasznie utrudniają czytelność

Przydałaby się też jakaś opcja na uzupełnienie wybranego przez nas pola liczbą

  # sprawdź czy x jest od 1 do 9, na takich liczbach operujemy
  def check(x)
    return (x >= 1 and x <= 9)
  end
 
  # ustaw pole, tylko jeżeli nie zostało wcześniej ustawione
  def set(x,y,z)
    if check(x) and check(y) and check(z) and @b[x][y][:number] == 0 # czy poprawne wartości i pole nie ustawione wcześniej
      @b[x][y][:number] = z # ustaw pole
      @b[x][y][:list] = [z] # na liście możliwych jest tylko ustawione pole od teraz
      return true
    end
  end

Metoda set zwraca prawdę lub fałsz jeśli się nie udało ustawić wartości. Przyda się, do zliczania ile pól zostało ustawionych przy wykonywaniu algorytmu rozwiązującego łamigłówkę. Widać też, że jak ustawiamy jakieś pole, to lista możliwych liczb dla tego pola jest ograniczana tylko do liczby z pola. Czyli ustawiając pole 2,2 liczbą 5 lista możliwych liczb to 5 a nie 1,2,3,4,5,6,7,8,9

Sprawdźmy to

class Sudoku
  # konstruktor
  def initialize
    # stwórz tablicę 10x10, będziemy korzystać dla wygody z indeksów 1..9 x 1..9
    @b = Array.new(10)
    @b.map! { Array.new(10) }
    (1..9).each do |i|
      (1..9).each do |j|
        # w każdym polu będzie numer 1..9, 0 to pusty, oraz lista możliwości 1..9
        @b[i][j] = { :number => 0, :list => (1..9).to_a }
      end
    end
  end
 
  # sprawdź czy x jest od 1 do 9, na takich liczbach operujemy
  def check(x)
    return (x >= 1 and x <= 9)
  end
 
  # ustaw pole, tylko jeżeli nie zostało wcześniej ustawione
  def set(x,y,z)
    if check(x) and check(y) and check(z) and @b[x][y][:number] == 0 # czy poprawne wartości i pole nie ustawione wcześniej
      @b[x][y][:number] = z # ustaw pole
      @b[x][y][:list] = [z] # na liście możliwych jest tylko ustawione pole od teraz
      return true
    end
  end
 
  # nasza plansza jako łańcuch znaków
  def to_s
    s = ''
    (1..9).each do |i|
      (1..9).each do |j|
        s += ' ' if j%3 == 1 and j != 1
        n = @b[i][j][:number]
        s += n == 0 ? '.' : n.to_s
      end
      s += "\n" if i%3 == 0 and i != 9
      s += "\n";
    end
    return s
  end
end
 
s = Sudoku.new
s.set(3,4,5)
s.set(1,2,3)
puts s.to_s

Daje nam wynik

.3. ... ...
... ... ...
... 5.. ...
 
... ... ...
... ... ...
... ... ...
 
... ... ...
... ... ...
... ... ...

Zostawmy na razie metody publiczne i stwórzmy kilka prywatnych pomocniczych

Pierwsza sprawa, jak będziemy identyfikować czy pole przynależy do małego kwadratu 3×3? Hmm… może sprawdzając czy współrzędne pola zawierają się we współrzędnych któregoś małego kwadratu? Sprawdźmy to…

Na początek określmy środki kwadratów 3×3. Są to kolejno: [2,2],[5,2],[8,2],[2,5],[5,5],[8,5],[2,8][5,8][8,8]. Pod tymi współrzędnymi (kolejno [x,y]) są wszystkie środki małych kwadratów.

  # pobierz tablicę środków wszystkich kwadratów
  def middleOptions
    [8,2,5].permutation(2).collect{ |p| p }+[[2,2],[5,5],[8,8]]
  end

Aby sprawdzić, czy pole p=[px,py] należy do kwadratu k o środku [kx,ky] należy:

  # znajdź współrzędne środka kwadratu do którego należy [@x,@y]
  def middle(x,y)
    m = middleOptions # tablica wszystkich możliwych środków kwadratów
    m.each do |t| # dla każdego środka kwadrata
      if x >= t[0] - 1 && x <= t[0] + 1 && y >= t[1] - 1 && y <= t[1] + 1 # jeżeli współrzędne zawierają się w kwardacie reprezentowanym przez bierzący środek
        return { :x => t[0], :y => t[1] } # zwróć współrzędne środka kwadratu
      end
    end
  end

Powyższy kod dla każdego małego kwadrata sprawdza czy pole o współrzędnych [x,y] się w nim zawiera. Metoda zwraca współrzędne środka tegoż kwadratu

Mamy już wystarczające zaplecze by zabrać się za algorytm rozwiązujący. Ja przyjąłem następującą drogę:

1. Dla każdego pola na planszy które ma wstawioną jakąś liczbę:
 
  a. dla wszystkich pól w wierszu tego pola, usuń liczbę z listy możliwych liczb
 
    .1. ... ... => wszystkie pola w wierszu w krórym jest 1 tracą z listy możliwych liczb 1
    4 2
    5 1
    1 =
    = 2
    4
    5
 
  b. dla wszystkich pól w kolumnie tego pola, usuń liczbę z listy możliwych liczb
 
    . 2,4,8,1 = 2,4,8
    1
    . 2,1 = 2
 
    .
    .
    .
 
    .
    .
    .
 
    => wszystkie pola w kolumnie w której jest 1 tracą z listy możliwych liczb 1
 
  c. dla wszystkich pól w kwadracie tego pola, usuń liczbę z listy możliwych liczb
 
    .1.
    ...
    ...
 
    => w żadnym polu już nie może być liczby 1
 
2. Uzupełnianie pól
 
  a. jeżeli w wierszu może być jakaś liczba tylko w jednym jedynym miejscu, to ją wstaw
 
    ... 4.. 2.7 => 1.. 4.. 2.7
    156 459 267
    2 9  6   3
 
    ^ w tym polu jako jedynym może być 1, więc ją wstawiamy
 
  b. jeżeli w kolumnie może być jakaś liczba tylko w jednym jedynym miejscu, to ją wstaw
 
    => analogicznie
 
  c. jeżeli w kwadracie może być jakaś liczba tylko w jednym jedynym miejscu, to ją wstaw
 
    => analogicznie

W sumie jest jeszcze kilka reguł, które moglibyśmy nauczyć nasz skrypt, ale nie będzie to potrzebne… o czym później

Zaimplementujmy metody z algorytmu

  # {1.b} usuń z listy możliwych liczbę spod [@x,@y] dla całej kolumny
  def filterByCol(x,y)
    l = 0 # licznik ile usunęliśmy cyfr z listy możliwych
    z = @b[x][y][:number] # pobierz liczbę która jest na polu @x,@y
    if z > 0 # jeżeli pole nie jest puste
      (1..9).each do |i| # od 1 do 9 po kolumnie
        if y != i # jeżeli nie stoimy na sprawdzamym polu
          l += 1 unless @b[x][i][:list].index(z).nil? # zwiększ licznik zmian jeśli liczba @z figuruje na liście możliwych liczb
          @b[x][i][:list] -= [z] # usuń @z z listy możliwych
        end
      end
    end
    l
  end
 
  # {1.a} usuń z listy możliwych liczbę spod [@x,@y] dla całego wiersza
  def filterByRow(x,y)
    # analogicznie jak filterByCol z tym, że lecimy po wierszu nie kolumnie
    l = 0
    z = @b[x][y][:number]
    if z > 0
      (1..9).each do |i|
        if x != i
          l += 1 unless @b[i][y][:list].index(z).nil?
          @b[i][y][:list] -= [z]
        end
      end
    end
    l
  end
 
    # {1.c} usuń z listy możliwych liczbę spod [@x,@y] dla całego kwadratu do którego należy [@x,@y]
  def filterByMiddle(x,y)
    # analogicznie jak filterByCol, opiszę tylko co jest inne
    l = 0
    z = @b[x][y][:number]
    if z > 0
      m = middle(x,y) # pobierz współrzędne środka
      # dla wszystkich pól w kwadracie do którego należą współrzędne środka
      ((m[:x] - 1)..(m[:x] + 1)).each do |i| # od m.x - 1 do m.x + 1 (czyli po wszystkich wierszach kwadratu)
        ((m[:y] - 1)..(m[:y] + 1)).each do |j| # od m.y - 1 do m.y + 1 (czyli po wszystkich kolumnach kwadratu)
          unless i == x and j == y # jeżeli nie jesteśmy na polu [@x,@y]
            l += 1 unless @b[i][j][:list].index(z).nil?
            @b[i][j][:list] -= [z]
          end
        end
      end
    end
    l
  end
 
  # {2.a} ustaw jedyną liczbę pasującą w wierszu (dla podanej kolumny), sprawdza wszystkie liczby od 1 do 9
  def setByRow(y)
    r = 0 # licznik zmian (l użyłem dalej, więc tutaj będzie r na licznik)
    (1..9).each do |l| # dla każdej liczby
      a = b = s = 0 # suma ile razy liczba l została znaleziona w wierszu
      (1..9).each do |i| # dla każdego wiersza
        unless @b[i][y][:list].index(l).nil? # jeżeli znalazł liczbę l na liście możliwych liczb
          a = i # zapamiętaj współrzędną x
          b = y # zapamiętaj współrzędną y
          s += 1
        end
      end
      if s == 1 # jeżeli znalazł daną liczbę tylko w 1 miejscu
        r += 1 if set(a,b,l) # zwiększ licznik zmian jeśli wstawiono nową liczbę
      end
    end
    r
  end
 
  # {2.b} ustaw jedyną liczbę pasującą w kolumnie (dla podanego wiersza), sprawdza wszystkie liczby od 1 do 9
  def setByCol(x)
    # analogicznie do setByRow
    r = 0
    (1..9).each do |l|
      a = b = s = 0
      (1..9).each do |i|
        unless @b[x][i][:list].index(l).nil?
          a = x
          b = i
          s += 1
        end
      end
      if s == 1
        r += 1 if set(a,b,l)
      end
    end
    r
  end
 
  # {2.c} ustaw jedyną liczbę pasującą w kwadracie dla podanego kwadrata
  def setByMiddle(m)
    # analogicznie do setByRow, opiszę tylko to, co jest inne
    r = 0
    (1..9).each do |l| # dla każdej liczby od 1 do 9
      a = b = s = 0
      # dla wszystkich pól w kwadracie
      ((m[:x] - 1)..(m[:x] + 1)).each do |i| # od m.x - 1 do m.x + 1 (czyli po wszystkich wierszach kwadratu)
        ((m[:y] - 1)..(m[:y] + 1)).each do |j| # od m.y - 1 do m.y + 1 (czyli po wszystkich kolumnach kwadratu)
          unless @b[i][j][:list].index(l).nil?
            a = i
            b = j
            s += 1
          end
        end
      end
      if s == 1
        r += 1 if set(a,b,l)
      end
    end
    r
  end

Każda ta metoda liczy ile wprowadzono zmian do planszy, dzięki temu możemy ją wykonywać, aż liczba zmian wyniesie 0. Wtedy mamy pewność, że algorytm dalej nie pójdzie i obliczymy wszystko co się da policzyć

Napiszmy więc metodę algorytm, która to wykonuje

  # rozwiąż ile potrafisz algorytmem
  def algoritm
    l = nil
    while l != 0 do # dopóki są jakieś zmiany (po to jest w każdej metodzie licznik zmian)
      l = 0
      # dla każdego pola na planszy
      (1..9).each do |i|
        (1..9).each do |j|
          l += filterByCol(i,j) # filtruj po kolumnie
          l += filterByRow(i,j) # filtruj po wierszu
          l += filterByMiddle(i,j) # filtruj po kwadracie
        end
      end
      # dla każdego wiersza / każdej kolumny
      (1..9).each do |i|
        l += setByCol(i) # ustaw unikaty dla kolumny
        l += setByRow(i) # ustaw unikaty dla wiersza
      end
      # dla każdego kwadrata
      middleOptions.each do |m|
        l += setByMiddle({ :x => m[0], :y => m[1] }) # ustaw unikaty
      end
    end
  end

Chciałoby się przetestować teraz, czy nasz algorytm umie coś rozwiązać. Dodajmy więc do metod publicznych taką, która wczyta nam planszę z pliku:

  # pobierz dane z pliku
  def from_file(file)
    initialize # odpal konstruktor jeszcze raz, żeby nadpisać ewentualne dane
    ln = 0
    open(file).read.split("\n").each do |l|
      if l != ''
        ln += 1
        cc = 0
        l.each_char.to_a.each_with_index do |c,i|
          if c != ' '
            cc += 1
            if (1..9).to_a.index(c.to_i)
              set(ln,cc,c.to_i)
            end
          end
        end
      end
    end
  end

Format pliku jest taki sam jak format wyjściowy na konsoli:

56. ..1 7.9
... ... .62
.2. 4.9 5.8
 
.39 ... 2..
2.5 .9. ..3
... .7. ...
 
.9. ... 6..
65. .1. .4.
7.8 .2. ...

Kopiując, mogą Ci się skopiować dodatkowe spacje między poziomymi separatorami. Należy je usunąć, gdyż z nimi program nie będzie działał prawidłowo

56. ..1 7.9
... ... .62
.2. 4.9 5.8
 <- tutaj
.39 ... 2..
2.5 .9. ..3
... .7. ...
 <- tutaj
.9. ... 6..
65. .1. .4.
7.8 .2. ...

Od razu z przykładowym sudoku na którym będziemy testować. Zapiszy to jako „sudoku.txt” w tym samy miejscu w którym odpalamy skrypt:

# encoding: utf-8
 
class Sudoku
 
  # konstruktor
  def initialize
    # stwórz tablicę 10x10, będziemy korzystać dla wygody z indeksów 1..9 x 1..9
    @b = Array.new(10)
    @b.map! { Array.new(10) }
    (1..9).each do |i|
      (1..9).each do |j|
        # w każdym polu będzie numer 1..9, 0 to pusty, oraz lista możliwości 1..9
        @b[i][j] = { :number => 0, :list => (1..9).to_a }
      end
    end
  end
 
  # pobierz dane z pliku
  def from_file(file)
    initialize # odpal konstruktor jeszcze raz, żeby nadpisać ewentualne dane
    ln = 0
    open(file).read.split("\n").each do |l|
      if l != ''
        ln += 1
        cc = 0
        l.each_char.to_a.each_with_index do |c,i|
          if c != ' '
            cc += 1
            if (1..9).to_a.index(c.to_i)
              set(ln,cc,c.to_i)
            end
          end
        end
      end
    end
  end
 
  # nasza plansza jako łańcuch znaków
  def to_s
    s = ''
    (1..9).each do |i|
      (1..9).each do |j|
        s += ' ' if j%3 == 1 and j != 1
        n = @b[i][j][:number]
        s += n == 0 ? '.' : n.to_s
      end
      s += "\n" if i%3 == 0 and i != 9
      s += "\n";
    end
    return s
  end
 
  # sprawdź czy x jest od 1 do 9, na takich liczbach operujemy
  def check(x)
    return (x >= 1 and x <= 9)
  end
 
  # ustaw pole, tylko jeżeli nie zostało wcześniej ustawione
  def set(x,y,z)
    if check(x) and check(y) and check(z) and @b[x][y][:number] == 0 # czy poprawne wartości i pole nie ustawione wcześniej
      @b[x][y][:number] = z # ustaw pole
      @b[x][y][:list] = [z] # na liście możliwych jest tylko ustawione pole od teraz
      return true
    end
  end
 
  # rozwiąż ile potrafisz algorytmem
  def algoritm
    l = nil
    while l != 0 do # dopóki są jakieś zmiany (po to jest w każdej metodzie licznik zmian)
      l = 0
      # dla każdego pola na planszy
      (1..9).each do |i|
        (1..9).each do |j|
          l += filterByCol(i,j) # filtruj po kolumnie
          l += filterByRow(i,j) # filtruj po wierszu
          l += filterByMiddle(i,j) # filtruj po kwadracie
        end
      end
      # dla każdego wiersza / każdej kolumny
      (1..9).each do |i|
        l += setByCol(i) # ustaw unikaty dla kolumny
        l += setByRow(i) # ustaw unikaty dla wiersza
      end
      # dla każdego kwadrata
      middleOptions.each do |m|
        l += setByMiddle({ :x => m[0], :y => m[1] }) # ustaw unikaty
      end
    end
  end
 
  private
 
  # znajdź współrzędne środka kwadratu do którego należy [@x,@y]
  def middle(x,y)
    m = middleOptions # tablica wszystkich możliwych środków kwadratów
    m.each do |t| # dla każdego środka kwadrata
      if x >= t[0] - 1 && x <= t[0] + 1 && y >= t[1] - 1 && y <= t[1] + 1 # jeżeli współrzędne zawierają się w kwardacie reprezentowanym przez bierzący środek
        return { :x => t[0], :y => t[1] } # zwróć współrzędne środka kwadratu
      end
    end
  end
 
  # usuń z listy możliwych liczbę spod [@x,@y] dla całej kolumny
  def filterByCol(x,y)
    l = 0 # licznik ile usunęliśmy cyfr z listy możliwych
    z = @b[x][y][:number] # pobierz liczbę która jest na polu @x,@y
    if z > 0 # jeżeli pole nie jest puste
      (1..9).each do |i| # od 1 do 9 po kolumnie
        if y != i # jeżeli nie stoimy na sprawdzamym polu
          l += 1 unless @b[x][i][:list].index(z).nil? # zwiększ licznik zmian jeśli liczba @z figuruje na liście możliwych liczb
          @b[x][i][:list] -= [z] # usuń @z z listy możliwych
        end
      end
    end
    l
  end
 
  # usuń z listy możliwych liczbę spod [@x,@y] dla całego wiersza
  def filterByRow(x,y)
    # analogicznie jak filterByCol z tym, że lecimy po wierszu nie kolumnie
    l = 0
    z = @b[x][y][:number]
    if z > 0
      (1..9).each do |i|
        if x != i
          l += 1 unless @b[i][y][:list].index(z).nil?
          @b[i][y][:list] -= [z]
        end
      end
    end
    l
  end
 
    # usuń z listy możliwych liczbę spod [@x,@y] dla całego kwadratu do którego należy [@x,@y]
  def filterByMiddle(x,y)
    # analogicznie jak filterByCol, opiszę tylko co jest inne
    l = 0
    z = @b[x][y][:number]
    if z > 0
      m = middle(x,y) # pobierz współrzędne środka
      # dla wszystkich pól w kwadracie do którego należą współrzędne środka
      ((m[:x] - 1)..(m[:x] + 1)).each do |i| # od m.x - 1 do m.x + 1 (czyli po wszystkich wierszach kwadratu)
        ((m[:y] - 1)..(m[:y] + 1)).each do |j| # od m.y - 1 do m.y + 1 (czyli po wszystkich kolumnach kwadratu)
          unless i == x and j == y # jeżeli nie jesteśmy na polu [@x,@y]
            l += 1 unless @b[i][j][:list].index(z).nil?
            @b[i][j][:list] -= [z]
          end
        end
      end
    end
    l
  end
 
  # ustaw jedyną liczbę pasującą w wierszu (dla podanej kolumny), sprawdza wszystkie liczby od 1 do 9
  def setByRow(y)
    r = 0 # licznik zmian (l użyłem dalej, więc tutaj będzie r na licznik)
    (1..9).each do |l| # dla każdej liczby
      a = b = s = 0 # suma ile razy liczba l została znaleziona w wierszu
      (1..9).each do |i| # dla każdego wiersza
        unless @b[i][y][:list].index(l).nil? # jeżeli znalazł liczbę l na liście możliwych liczb
          a = i # zapamiętaj współrzędną x
          b = y # zapamiętaj współrzędną y
          s += 1
        end
      end
      if s == 1 # jeżeli znalazł daną liczbę tylko w 1 miejscu
        r += 1 if set(a,b,l) # zwiększ licznik zmian jeśli wstawiono nową liczbę
      end
    end
    r
  end
 
  # ustaw jedyną liczbę pasującą w kolumnie (dla podanego wiersza), sprawdza wszystkie liczby od 1 do 9
  def setByCol(x)
    # analogicznie do setByRow
    r = 0
    (1..9).each do |l|
      a = b = s = 0
      (1..9).each do |i|
        unless @b[x][i][:list].index(l).nil?
          a = x
          b = i
          s += 1
        end
      end
      if s == 1
        r += 1 if set(a,b,l)
      end
    end
    r
  end
 
  # ustaw jedyną liczbę pasującą w kwadracie dla podanego kwadrata
  def setByMiddle(m)
    # analogicznie do setByRow, opiszę tylko to, co jest inne
    r = 0
    (1..9).each do |l| # dla każdej liczby od 1 do 9
      a = b = s = 0
      # dla wszystkich pól w kwadracie
      ((m[:x] - 1)..(m[:x] + 1)).each do |i| # od m.x - 1 do m.x + 1 (czyli po wszystkich wierszach kwadratu)
        ((m[:y] - 1)..(m[:y] + 1)).each do |j| # od m.y - 1 do m.y + 1 (czyli po wszystkich kolumnach kwadratu)
          unless @b[i][j][:list].index(l).nil?
            a = i
            b = j
            s += 1
          end
        end
      end
      if s == 1
        r += 1 if set(a,b,l)
      end
    end
    r
  end
 
  # pobierz tablicę środków wszystkich kwadratów
  def middleOptions
    [8,2,5].permutation(2).collect{ |p| p }+[[2,2],[5,5],[8,8]]
  end
end
 
s = Sudoku.new
begin
  s.from_file("sudoku.txt")
  s.algoritm
  puts s.to_s
rescue
  puts "nie umiem znaleźć rozwiązania"
end

Przykład był o tyle łatwy, że nie musieliśmy strzelać żadnej drogi. Dlatego też program rozwiązał nam całe sudoku:

564 281 739
981 735 462
327 469 518
 
439 158 276
275 694 183
816 372 954
 
193 847 625
652 913 847
748 526 391

Jednak nie możemy teraz stanąć na laurach i przygotujemy opcje na trudne sudoku, w których dochodzimy do momentu, że musimy strzelić jedną z kilku możliwych liczb.

Najpierw metoda sprawdzająca, czy odkryliśmy całą planszę (czy już koniec):

  # czy odkryliśmy wszystkie pola
  def finish?
    c = 0 # licznik zer
    (1..9).each do |i|
      (1..9).each do |j|
        c += 1 if @b[i][j][:number] == 0 
      end
    end
    c == 0
  end

Oraz metoda, która znajdzie nam pola w których wybór jest jak najmniejszy (np pomiędzy 2 liczbami a nie 9!)

  # znajdź pole z najmniejszą możliwą ilością liczb do wyboru (oprócz 1 czyli dla tych nieodkrytych pól)
  def minimal
    min = 10 # więcej niż najwięcej z możliwych
    x = y = 0 # nie znaleziono
    (1..9).each do |i|
      (1..9).each do |j|
        s = @b[i][j][:list].size
        if s < min and s > 1 # znaleźliśmy mniejsze niż dotychczas, podmień dane
          x = i
          y = j
          min = s
        end
      end
    end
    return [x,y] # zwracamy pole o najmniejszej ilości liczb do wyboru
  end

Ostatnia pomocnicza metoda kopiuje nam całą zawartość naszej planszy, czyli wartości pól, oraz aktualne listy możliwych liczb. Przyda się nam do rekurencji z powrotami

  # skopiuj dane
  def copyBoard
    n = Array.new(10)
    n.map! { Array.new(10) }
    (1..9).each do |i|
      (1..9).each do |j|
        n[i][j] = { :number => @b[i][j][:number], :list => @b[i][j][:list] }
      end
    end
    n
  end

Teraz zacznie się cała magia, czyli rekurencja z powrotami. Jeśli nie wiesz co to jest zapoznaj się z Problemem 8 hetmanów.

  # rozwiąż rekurencyjnie (rekurencja z powrotami)
  def solve_rec
    raise 'znalazłem' if finish? # jak znalazł rozwiązanie to wyrzuć wyjątek
    x,y = minimal
    cp = copyBoard # kopiuj stan planszy do powrotu
    unless x == 0 or y == 0 # jeżeli istnieje jakieś pole z liczbą możliwych liczb od 2 do 9
      @b[x][y][:list].each do |l| # dla każdej możliwości
        @b = cp # ustaw stan planszy na kopię
        set(x,y,l) # ustaw pole na kolejną opcję z możliwych liczb w polu
        algoritm # uruchom algorytm na nowej planszy
        solve_rec # wywołaj się ponownie
      end
    end
  end

I na koniec zamiast używać metody algoritm, przenieśmy ją do prywatnych i stwórzmy solve

  # rozwiąż sudoku
  def solve
    algoritm
    begin
      solve_rec unless finish?
    rescue
      # przechwyć wyjątek z rozwiązaniem
    end
    raise 'nie znalazłem' unless finish? # jak nie znalazł planszy wyrzuć wyjątek (błędne dane, albo za mało danych do rozwiązania planszy)
  end

Cały kod

# encoding: utf-8
 
class Sudoku
 
  # konstruktor
  def initialize
    # stwórz tablicę 10x10, będziemy korzystać dla wygody z indeksów 1..9 x 1..9
    @b = Array.new(10)
    @b.map! { Array.new(10) }
    (1..9).each do |i|
      (1..9).each do |j|
        # w każdym polu będzie numer 1..9, 0 to pusty, oraz lista możliwości 1..9
        @b[i][j] = { :number => 0, :list => (1..9).to_a }
      end
    end
  end
 
  # pobierz dane z pliku
  def from_file(file)
    initialize # odpal konstruktor jeszcze raz, żeby nadpisać ewentualne dane
    ln = 0
    open(file).read.split("\n").each do |l|
      if l != ''
        ln += 1
        cc = 0
        l.each_char.to_a.each_with_index do |c,i|
          if c != ' '
            cc += 1
            if (1..9).to_a.index(c.to_i)
              set(ln,cc,c.to_i)
            end
          end
        end
      end
    end
  end
 
  # nasza plansza jako łańcuch znaków
  def to_s
    s = ''
    (1..9).each do |i|
      (1..9).each do |j|
        s += ' ' if j%3 == 1 and j != 1
        n = @b[i][j][:number]
        s += n == 0 ? '.' : n.to_s
      end
      s += "\n" if i%3 == 0 and i != 9
      s += "\n";
    end
    return s
  end
 
  # sprawdź czy x jest od 1 do 9, na takich liczbach operujemy
  def check(x)
    return (x >= 1 and x <= 9)
  end
 
  # ustaw pole, tylko jeżeli nie zostało wcześniej ustawione
  def set(x,y,z)
    if check(x) and check(y) and check(z) and @b[x][y][:number] == 0 # czy poprawne wartości i pole nie ustawione wcześniej
      @b[x][y][:number] = z # ustaw pole
      @b[x][y][:list] = [z] # na liście możliwych jest tylko ustawione pole od teraz
      return true
    end
  end
 
  # rozwiąż sudoku
  def solve
    algoritm
    begin
      solve_rec unless finish?
    rescue
      # przechwyć wyjątek z rozwiązaniem
    end
    raise 'nie znalazłem' unless finish? # jak nie znalazł planszy wyrzuć wyjątek (błędne dane, albo za mało danych do rozwiązania planszy)
  end
 
  private
 
  # rozwiąż rekurencyjnie (rekurencja z powrotami)
  def solve_rec
    raise 'znalazłem' if finish? # jak znalazł rozwiązanie to wyrzuć wyjątek
    x,y = minimal
    cp = copyBoard # kopiuj stan planszy do powrotu
    unless x == 0 or y == 0 # jeżeli istnieje jakieś pole z liczbą możliwych liczb od 2 do 9
      @b[x][y][:list].each do |l| # dla każdej możliwości
        @b = cp # ustaw stan planszy na kopię
        set(x,y,l) # ustaw pole na kolejną opcję z możliwych liczb w polu
        algoritm # uruchom algorytm na nowej planszy
        solve_rec # wywołaj się ponownie
      end
    end
  end
 
  # rozwiąż ile potrafisz algorytmem
  def algoritm
    l = nil
    while l != 0 do # dopóki są jakieś zmiany (po to jest w każdej metodzie licznik zmian)
      l = 0
      # dla każdego pola na planszy
      (1..9).each do |i|
        (1..9).each do |j|
          l += filterByCol(i,j) # filtruj po kolumnie
          l += filterByRow(i,j) # filtruj po wierszu
          l += filterByMiddle(i,j) # filtruj po kwadracie
        end
      end
      # dla każdego wiersza / każdej kolumny
      (1..9).each do |i|
        l += setByCol(i) # ustaw unikaty dla kolumny
        l += setByRow(i) # ustaw unikaty dla wiersza
      end
      # dla każdego kwadrata
      middleOptions.each do |m|
        l += setByMiddle({ :x => m[0], :y => m[1] }) # ustaw unikaty
      end
    end
  end
 
  # znajdź współrzędne środka kwadratu do którego należy [@x,@y]
  def middle(x,y)
    m = middleOptions # tablica wszystkich możliwych środków kwadratów
    m.each do |t| # dla każdego środka kwadrata
      if x >= t[0] - 1 && x <= t[0] + 1 && y >= t[1] - 1 && y <= t[1] + 1 # jeżeli współrzędne zawierają się w kwardacie reprezentowanym przez bierzący środek
        return { :x => t[0], :y => t[1] } # zwróć współrzędne środka kwadratu
      end
    end
  end
 
  # usuń z listy możliwych liczbę spod [@x,@y] dla całej kolumny
  def filterByCol(x,y)
    l = 0 # licznik ile usunęliśmy cyfr z listy możliwych
    z = @b[x][y][:number] # pobierz liczbę która jest na polu @x,@y
    if z > 0 # jeżeli pole nie jest puste
      (1..9).each do |i| # od 1 do 9 po kolumnie
        if y != i # jeżeli nie stoimy na sprawdzamym polu
          l += 1 unless @b[x][i][:list].index(z).nil? # zwiększ licznik zmian jeśli liczba @z figuruje na liście możliwych liczb
          @b[x][i][:list] -= [z] # usuń @z z listy możliwych
        end
      end
    end
    l
  end
 
  # usuń z listy możliwych liczbę spod [@x,@y] dla całego wiersza
  def filterByRow(x,y)
    # analogicznie jak filterByCol z tym, że lecimy po wierszu nie kolumnie
    l = 0
    z = @b[x][y][:number]
    if z > 0
      (1..9).each do |i|
        if x != i
          l += 1 unless @b[i][y][:list].index(z).nil?
          @b[i][y][:list] -= [z]
        end
      end
    end
    l
  end
 
    # usuń z listy możliwych liczbę spod [@x,@y] dla całego kwadratu do którego należy [@x,@y]
  def filterByMiddle(x,y)
    # analogicznie jak filterByCol, opiszę tylko co jest inne
    l = 0
    z = @b[x][y][:number]
    if z > 0
      m = middle(x,y) # pobierz współrzędne środka
      # dla wszystkich pól w kwadracie do którego należą współrzędne środka
      ((m[:x] - 1)..(m[:x] + 1)).each do |i| # od m.x - 1 do m.x + 1 (czyli po wszystkich wierszach kwadratu)
        ((m[:y] - 1)..(m[:y] + 1)).each do |j| # od m.y - 1 do m.y + 1 (czyli po wszystkich kolumnach kwadratu)
          unless i == x and j == y # jeżeli nie jesteśmy na polu [@x,@y]
            l += 1 unless @b[i][j][:list].index(z).nil?
            @b[i][j][:list] -= [z]
          end
        end
      end
    end
    l
  end
 
  # ustaw jedyną liczbę pasującą w wierszu (dla podanej kolumny), sprawdza wszystkie liczby od 1 do 9
  def setByRow(y)
    r = 0 # licznik zmian (l użyłem dalej, więc tutaj będzie r na licznik)
    (1..9).each do |l| # dla każdej liczby
      a = b = s = 0 # suma ile razy liczba l została znaleziona w wierszu
      (1..9).each do |i| # dla każdego wiersza
        unless @b[i][y][:list].index(l).nil? # jeżeli znalazł liczbę l na liście możliwych liczb
          a = i # zapamiętaj współrzędną x
          b = y # zapamiętaj współrzędną y
          s += 1
        end
      end
      if s == 1 # jeżeli znalazł daną liczbę tylko w 1 miejscu
        r += 1 if set(a,b,l) # zwiększ licznik zmian jeśli wstawiono nową liczbę
      end
    end
    r
  end
 
  # ustaw jedyną liczbę pasującą w kolumnie (dla podanego wiersza), sprawdza wszystkie liczby od 1 do 9
  def setByCol(x)
    # analogicznie do setByRow
    r = 0
    (1..9).each do |l|
      a = b = s = 0
      (1..9).each do |i|
        unless @b[x][i][:list].index(l).nil?
          a = x
          b = i
          s += 1
        end
      end
      if s == 1
        r += 1 if set(a,b,l)
      end
    end
    r
  end
 
  # ustaw jedyną liczbę pasującą w kwadracie dla podanego kwadrata
  def setByMiddle(m)
    # analogicznie do setByRow, opiszę tylko to, co jest inne
    r = 0
    (1..9).each do |l| # dla każdej liczby od 1 do 9
      a = b = s = 0
      # dla wszystkich pól w kwadracie
      ((m[:x] - 1)..(m[:x] + 1)).each do |i| # od m.x - 1 do m.x + 1 (czyli po wszystkich wierszach kwadratu)
        ((m[:y] - 1)..(m[:y] + 1)).each do |j| # od m.y - 1 do m.y + 1 (czyli po wszystkich kolumnach kwadratu)
          unless @b[i][j][:list].index(l).nil?
            a = i
            b = j
            s += 1
          end
        end
      end
      if s == 1
        r += 1 if set(a,b,l)
      end
    end
    r
  end
 
  # skopiuj dane
  def copyBoard
    n = Array.new(10)
    n.map! { Array.new(10) }
    (1..9).each do |i|
      (1..9).each do |j|
        n[i][j] = { :number => @b[i][j][:number], :list => @b[i][j][:list] }
      end
    end
    n
  end
 
  # pobierz tablicę środków wszystkich kwadratów
  def middleOptions
    [8,2,5].permutation(2).collect{ |p| p }+[[2,2],[5,5],[8,8]]
  end
 
  # znajdź pole z najmniejszą możliwą ilością liczb do wyboru (oprócz 1 czyli dla tych nieodkrytych pól)
  def minimal
    min = 10 # więcej niż najwięcej z możliwych
    x = y = 0 # nie znaleziono
    (1..9).each do |i|
      (1..9).each do |j|
        s = @b[i][j][:list].size
        if s < min and s > 1 # znaleźliśmy mniejsze niż dotychczas, podmień dane
          x = i
          y = j
          min = s
        end
      end
    end
    return [x,y] # zwracamy pole o najmniejszej ilości liczb do wyboru
  end
 
  # czy odkryliśmy wszystkie pola
  def finish?
    c = 0 # licznik zer
    (1..9).each do |i|
      (1..9).each do |j|
        c += 1 if @b[i][j][:number] == 0 
      end
    end
    c == 0
  end
end
 
s = Sudoku.new
begin
  s.from_file("sudoku.txt")
  s.solve
  puts s.to_s
rescue
  puts "nie umiem znaleźć rozwiązania"
end

Przykład

.8. ... ...
3.4 ... ...
... .2. 1.9
 
... 2.. .7.
.3. ..8 .9.
65. ... 3..
 
8.9 ... ...
... .3. 6..
... 16. ...

sam algorytm rozwiązuje do momentu:

.82 ... ...
3.4 .8. ...
576 324 189
 
..1 253 876
237 6.8 .9.
658 ... 3..
 
869 ... ...
..5 839 6..
..3 16. 9.8

razem z rekurencją z powrotami

182 596 734
394 781 265
576 324 189
 
941 253 876
237 618 495
658 947 312
 
869 472 551
415 839 627
723 165 948

Większość sudoku pęka bez problemu, ale wiadomo, jeśli podamy odpowiednio trudne, np takie, że jest mało liczb i wstępny algorytm nie uzupełni ani jednego pola, to rekurencja będzie wyliczała się strasznie długo. Tak samo, program może nie znaleźć rozwiązania, pomimo, że takie istnieje. Dzieje się tak, gdyż algorytm zawsze wybiera to samo pole gdy dokonuje podziału na rekurencję. Gdyby dorzucić do tego trochę losowości, po kilku próbach może by się udało znaleźć rozwiązania w takich przypadkach. Ale to już może kiedy indziej :)

Jeżeli choć 1 osoba się zainteresowała tematem albo wyciągnęła cokolwiek z tego artykułu (a raczej namiastki artykułu) to znaczy, że warto było go pisać.

Trzymajcie się!



Alternatywne implementacje

Hack Lang » Rekurencyjnie

<?hh // strict

namespace ProgramistaIt\Sudoku;

final class RecursiveSolver {
    
    private $board = Vector{};
    private $temp = Vector{};

    private $time = 0;
    private $depth = 0;

    public function __construct(string $filename) {
        $this->readBoardFromFile($filename);
    }

    public function solve(): bool {
        $this->time = -microtime(true);
        $result = $this->solveRecursive(0, 0);
        $this->time += microtime(true);
        return $result;
    }

    public function info() {
        return [
            'time' => $this->time,
            'depth' => $this->depth 
        ];
    }

    public function drawBoard(): string {
        $text = "-------------------------\n";
        for ($i = 0; $i < 9; $i++) {
            $text .= "| ";
            for ($j = 0; $j < 9; $j++) {
                $text .= $this->temp[$i][$j] . ' ';
                if ($j % 3 === 2) {
                    $text .= "| ";
                }
            }
            $text .= "\n";
            if ($i % 3 === 2) {
                $text .= "-------------------------\n";
            }
        }
        return $text;
    }

    private function readBoardFromFile(string $filename) {
        $board = explode("\n", trim(file_get_contents('board.txt')));

        for ($i = 0; $i < 9; $i++) {
            $this->board[] = Vector{};
            $this->temp[] = Vector{};
            for ($j = 0; $j < 9; $j++) {
                $val = $board[$i][$j];
                if (!preg_match('/[0-9]/', $val)) {
                    $val = 0;
                }
                $this->board[$i][] = $val;
                $this->temp[$i][] = $val;
            }
        }
    }

    private function canInsert(int $x, int $y, int $value): bool {
        for ($i = 0; $i < 9; $i++) {
            if ($value == $this->temp[$x][$i]) {
                return false;
            }
            if($value == $this->temp[$i][$y]) {
                return false;
            }
            $cx = intval(floor($x / 3) * 3 + $i % 3);
            $cy = intval(floor($y / 3) * 3 + $i / 3);
            if($value == $this->temp[$cx][$cy]) {
                return false;
            }
        }
        return true;
    }

    private function nextItem(int $x, int $y): bool {
        if ($x == 8 && $y == 8)
            return true;
        if ($x == 8)
            return $this->solveRecursive(0, $y + 1);
        return $this->solveRecursive($x + 1, $y);
    }

    private function solveRecursive(int $x, int $y): bool {
        $this->depth++;
        if ($this->board[$x][$y] == 0) {
            for ($i = 1; $i <= 9; $i++) {
                if ($this->canInsert($x, $y, $i)) {
                    $this->temp[$x][$y] = $i;
                    if ($this->nextItem($x, $y)) {
                        return true;
                    }
                }
            }
            $this->temp[$x][$y] = 0;
            return false;
        }
        return $this->nextItem($x, $y);
    }

}

$recursiveSolver = new RecursiveSolver('board.txt');
if($recursiveSolver->solve()) {
    echo $recursiveSolver->drawBoard();
    print_r($recursiveSolver->info());
} else {
    echo 'impossible!';
}

Plansza:

.......1.
4........
.2.......
....5.4.7
..8...3..
..1.9....
3..4..2..
.5.1.....
...8.6...

Tagi: , , ,

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *