niedziela, marca 06, 2011

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 postybeta
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 ;-)

4 komentarze:

  1. nie chce byc niemily albo sie przemadrzac, ale widziales to?
    https://market.android.com/details?id=de.georgwiese.sudokusolver&feature=search_result
    a tak wogole to google googles skanuje i rozwiazuje KAZDE sudoku...

    OdpowiedzUsuń
  2. Tego nie widziałem, ale wiem, że Google Googles rozwiązuje Sudoku.
    Ale co z tego?
    Przecież cały dowcip polega na tym by samemu wymyślić sposób na rozwiązanie :-)

    OdpowiedzUsuń
  3. gdzies czytalem, ze jest juz gotowy algorytm rozwiazujacy wszystkie...

    OdpowiedzUsuń
  4. @maciunio2 - a pewnie, że istnieje i nie jest nawet trudny, dokładniej to istnieje ich wiele. Niektóre radzą sobie dobrze też z większymi sudoku np. 25x25, a niektóre tylko z 9x9.
    Mój też zresztą rozwiązuje wszystkie 9x9, ale nie robi tego w rozsądnym czasie ;-)

    OdpowiedzUsuń