Sudoku - przyśpieszamy, ale jeszcze nie za bardzo ;-)

Po tym jak zostałem wyzwany do pojedynku na rozwiązywarki Sudoku ;-) zajrzałem do kodu mojej rozwiązywarki i wprowadziłem w niej pewne zmiany.
Jest pewne przyśpieszenie choć jeszcze nie mogę się równać z rozwiązaniem WildWezyra.
Podejrzewam, że w tym celu będę musiał zmienić sposób szukania kandydatów :-)

Tutaj moje obecne rozwiązanie:



Do tej pory moje rozwiązanie działało tak, że dla każdego wolnego pola generowało listę możliwych w nim liczb (pod uwagę brane było to czy dana liczba znajduje się w kwadracie 3x3, czy znajduje się już w rzędzie i czy znajduje się w kolumnie, odpowiedź twierdząca na dowolne z tych pytań eliminowało liczbę z listy kandydatów dla danego pola).
Po tym wybierana była ta lista, która jako pierwsza z wszystkich możliwych (generowanych od lewego górnego rogu w prawo i w dół) miała najmniejszą ilość kandydatów.
To działa, ale nie do końca dobrze.

Dlatego wprowadziłem zmianę polegającą na tym, że teraz tworzona jest lista wszystkich rozwiązań, które mają minimalną ilość kandydatów.
Następnie z tej listy wybierany jest ten kandydat, dla którego suma zbudowana z użyć proponowanych przez niego liczb jest największa.... czyli jeśli proponuje użycie liczb 7 i 9, to sumowane są liczby użyć 7 i 9 na całej planszy.
Nie jest to najlepsze kryterium, ale działa i zmniejsza ilość kroków w celu znalezienia rozwiązania.

Teraz będę musiał zastanowić się nad lepszym kryterium ;-) lub co bardziej prawdopodobne nad nowym sposobem generowania czy też oceniania kandydatów :-)


Podobne posty^beta
Sudoku solver - dalsza walka ;-)
Sudoku - wstyd mi ;-)
Sudoku - atak pierwszy ;-)
Sudoku - rozwiązanie doskonałe ;p
Przyśpieszanie backtrackingu