Sudoku - atak pierwszy ;-)

[Updata: mam już lepsze rozwiązanie, które radzi sobie jak mi się wydaje ze wszystkimi Sudoku i to w bardzo krótkim czasie :-)]

Zaatakowałem sobie Sudoku ;-)
Czyli napisałem coś co powinno być zdolne do rozwiązywania Sudoku... i jest, ale w rozsądnym czasie rozwiązuje tylko te prostsze ;-)

Przykładowe Sudoku wrzuciłem do środka, dzięki czemu można zobaczyć działanie mojej "rozwiązywarki" ;-)



Jak to działa?

Prosto i naiwnie. Atak odbywa się przy pomocy backtrackingu (czyli tak samo jak atakowałem problem 8 królowych :-)).
Pozycje do rozważenia dobierane są w taki sposób, że najpierw skanujemy jakie liczby zostały użyte w poszczególnych liniach (poziomych i pionowych), oraz "sekcjach" (czyli kwadratach 3x3). Następnie iterujemy po liczbach od 1 do 9 i dla każdej z tych liczb iterujemy po możliwych pozycjach sprawdzając czy w danym momencie takowa pozycja może zostać zajęta przez daną liczbę, jeśli może to zapamiętujemy sobie daną liczbę na danej pozycji jako kandydata. Następnie sortujemy kandydatów tak by najpierw rozpatrywać tych, którzy są "najbardziej unikatowi" ;-) Idealnie takim kandydatem będzie 1 liczba, która może być na danej pozycji.

Przy bardziej skomplikowanych Sudoku dobrze to odpalać pod Chrome lub Firefoksem (4.0), i nie chodzi o wydajność JavaScriptu, a bardziej o to, że ta wersja co przeszukanie 1000 rozwiązań wyświetla alert ;-) a w Chrome i Firefoksie można po prostu zaznaczyć przy drugim alercie, że nie chcemy go już widzieć.... (przy okazji wydaje się, że obie przeglądarki dodają tą opcję tylko gdy alerty pojawiają się w odstępie góra 1 sekundy ;-)).

Teraz trzeba by się za to zabrać od poważniejszej strony i spróbować wymyślić lepszy algorytm :-)


Podobne posty^beta
Sudoku - przyśpieszamy, ale jeszcze nie za bardzo ;-)
Sudoku - rozwiązanie doskonałe ;p
Sudoku - wstyd mi ;-)
Przyśpieszanie backtrackingu
Sudoku - atak pierwszy wersja 2 ;-)