czwartek, sierpnia 18, 2011

Sudoku solver - dalsza walka ;-)

Wydaje mi się, że dotarłem już do ściany z algorytmem ;-) A jedyne miejsce na przyspieszenie to optymalizacje.

Sudoku potwór które potrzebowało w tym co nazwałem rozwiązaniem doskonałym 38 tysięcy prób, teraz działa w 1500-1600 ;-)
Ówczesne blisko 8 sekund, zmieniło się w zwykle mniej niż 180 ms.

Potwór wygląda tak:



.........
.....3.85
..1.2....
...5.7...
..4...1..
.9.......
5......73
..2.1....
....4...9


Sama rozwiązywarka podobnie do tego jak wyglądała wcześniej ;-)



Algorytm działa prawie tak samo jak działał wcześniej z tą drobną różnicą, że poprawiłem 2 błędy z poprzedniej wersji, teraz jeżeli istnieje kilka równolicznych zestawów kandydatów to wybierany jest ten, który ma najmniejszą sumę liczby jeszcze niewykorzystanych liczb....... inaczej mówiąc ;-) Jeśli dla pola A są kandydaci 3 i 5, a dla pola B kandydaci 2 i 7 to wybierane przy uwzględnieniu, że np. 3 i 5 są wykorzystane już 8 razy na planszy, a 2 i 7 dopiero 3 razy to po zsumowaniu dla A będziemy mieli (9-8)*2, a dla B (9-3)*2, czyli A jest lepsze.
Następnie sortuję jeszcze liczby "kandydackie" dla pola tak by najpierw próbować te które których użyto już najwięcej razy.
Wcześniej jakby się zastanowić robiłem to jakby na odwrót ;-)
Dodatkowego przyśpieszenia wszystko dostało przez zmianę formatu przechowywania danych. Wcześniej miałem tablicę łańcuchów w postaci pole:wartość, teraz mam tablicę w której parzyste elementy to numer pola, a nieparzyste wartość. Dzięki temu unikam masy wołań split(":").
Dałoby się jeszcze to trochę przyśpieszyć, ale już jakoś nie czuję bluesa do tego ;-)

Cała zabawa jest zaś odpowiedzią na rozwiązywarkę WildWezyra :-)
Moja wykonuje mniej kroków, ale wykonuje się ciut wolniej, choć wydaje mi się, że wystarczyłoby kilka zmian w obróbce danych [może ich spróbuję ;-)]


Podobne postybeta
Sudoku - przyśpieszamy, ale jeszcze nie za bardzo ;-)
10 milionów pięter...
Sudoku - rozwiązanie doskonałe ;p
Sudoku - wstyd mi ;-)
HeapSort, a MergeSort i QuickSort :-) - od strony "chytrości" ;-)