Sudoku FlowJak komputery rozwiązują Sudoku
Zaktualizowano 2026-10-05
Nawracanie
Program próbuje wpisać do pustej komórki cyfrę zgodną z regułami i kontynuuje. Jeśli żadna cyfra nie prowadzi do rozwiązania, cofa wcześniejszy wybór i próbuje innej. Wybranie najpierw komórki z najmniejszą liczbą możliwych cyfr często znacznie skraca przeszukiwanie.
Źródła: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Pokrycie dokładne i Dancing Links
Sudoku można przedstawić jako problem pokrycia dokładnego: należy wybrać rozmieszczenia cyfr tak, aby każda komórka oraz każda cyfra w każdym wierszu, kolumnie i kwadracie były pokryte dokładnie raz. W artykule z listopada 2000 roku Donald Knuth opisał Dancing Links, wydajny sposób wykonywania jego algorytmu X opartego na nawracaniu. Zastosowany do modelu Sudoku opartego na pokryciu dokładnym algorytm ten szybko znajduje wszystkie rozwiązania łamigłówki.
Źródła: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Przeszukiwanie losowe
Niektóre programy wypełniają planszę losowo, a następnie przestawiają liczby, aby zmniejszyć liczbę konfliktów, stosując metody takie jak symulowane wyżarzanie lub algorytmy genetyczne. Badano je jako alternatywne podejścia; ich skuteczność zależy od programu i łamigłówki.
Źródła: Wikipedia: Sudoku solving algorithms
Programy myślące jak ludzie
System podpowiedzi ma inne zadanie: nie tylko znaleźć rozwiązanie, lecz także pokazać kolejny krok, który człowiek może zrozumieć i wykonać. System w naszej aplikacji sprawdza techniki stosowane przez ludzi w ustalonej kolejności, od najłatwiejszych, takich jak Ukryty singiel, po najtrudniejsze, takie jak łańcuchy i zbiory prawie zamknięte, i stosuje pierwszą, która prowadzi do wpisania cyfry; trudniejsze techniki najpierw eliminują kandydatów. Najtrudniejsza technika zastosowana do danej łamigłówki wyznacza jej poziom w aplikacji.
Źródła: Czego wymaga każdy poziom trudności sudoku
