Sudoku Solver w jednej (rekurencyjnej) kwerendzie SQL

Posted: 2010/03/13 by wildwezyr in Programistycznie i technicznie
Tagi: , , , , , , , , , , ,

W skrócie – w tym wpisie:

  1. Siła wyrazu rekurencyjnych kwerend w SQL pozwala napisać Sudoku Solver w jednej instrukcji select (więcej)
  2. Efektywność jednak nie jest mocną stroną tego rozwiązania – mój stary Solver w JavaScript robi to 30x razy szybciej (więcej)
  3. Dlaczego nie lubię Sudoku, ale lubię Kakuro (więcej)
  4. Pierwsze wrażenia po 3 dniach życia bloga – kakiej funkcjonalności mi najbardziej brakuje w blogach robionych na WordPress.com? (więcej)



Przeglądając Wykop natrafiłem na coś takiego: Oracle RDBMS 11gR2 – Solving a Sudoku using Recursive Subquery Factoring. Ciekawa sprawa, choć Oracle na swoim sprzęcie aktualnie nie mam, więc przetestować nie było jak. Na szczęście w komentarzach ktoś dał link do wersji postgresowej: Sudoku puzzle. Tak się składa, że Postgresa mam i lubię bardziej niż Oracle, więc się ucieszyłem.

Pomimo iż trudno zrozumieć ten kod, to on po prostu działa. Aby ułatwić sobie testowanie, wykonałem drobną modyfikację:

WITH RECURSIVE x( s, ind ) AS
( SELECT sud, position( ' ' IN sud )
  FROM  (SELECT regexp_replace(regexp_replace(-- zadanie do rozwiązania wstaw poniżej
'
001002000030040050600700800006000007010000030900000600007001008040030020000500900
', '[\n\r]', '', 'g'), '[^1-9]', ' ', 'g')::text
             AS sud) xx
  UNION ALL
  SELECT substr( s, 1, ind - 1 ) || z || substr( s, ind + 1 )
       , position(' ' IN repeat('x',ind) || substr( s, ind + 1 ) )
  FROM x
     ,  (SELECT gs::text AS z FROM generate_series(1,9) gs) z
  WHERE ind > 0
  AND NOT EXISTS ( SELECT NULL
                   FROM generate_series(1,9) lp
                   WHERE z.z = substr( s, ( (ind - 1 ) / 9 ) * 9 + lp, 1 )
                   OR    z.z = substr( s, mod( ind - 1, 9 ) - 8 + lp * 9, 1 )
                   OR    z.z = substr( s, mod( ( ( ind - 1 ) / 3 ), 3 ) * 3
                                      + ( ( ind - 1 ) / 27 ) * 27 + lp
                                      + ( ( lp - 1 ) / 3 ) * 6
                                   , 1 )
                 )
)
SELECT s
FROM x
WHERE ind = 0;

To co widać powyżej zawiera od razu zadaną do rozwiązania jedną z trudniejszych plansz Sudoku. Na obrazku wygląda ona tak:


Rozwiązanie tego zajmuje około 60 sekund. Inne nietrywialne układy do rozwiązania są np. tu: dyskusja na angielskiej wikipedii. Przykładowo układ zwany Easter Monster wygląda tak

1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1

i wymaga ponad 120 sekund na rozwiązanie powyższym sposobem.

Z ciekawości odgrzebałem swój stary WildWezyr’s Sudoku Solver. Napisałem go w 2005 roku i właściwie zapomniałem o nim. Była to dla mnie pierwsza lekcja JavaScripta, mój solver mimo stosowania metody brutal-force (lekko zoptymalizowanej) radzi sobie bardzo dobrze, np. rozwiązanie powyższego Easter Monster zajmuje mu ok. 10 sekund w Firefox 3.6, a jak wiadomo to Chrome posiada aktualnie najszybszy engine JavaScriptu. I to się zgadza – w Chrome 4.0.249 zajmuje to około 4 sekundy u mnie. Czyli… działa to 30x szybciej niż jednokwerendowe rozwiązanie w SQL.

Moje rozwiązanie jest oczywiście znacznie bardziej rozwlekłe niż jedna instrukcja SQL, co ciekawe znalazłem też rozwiązanie w plpgSQL: Solving sudoku using PostgreSQL PL/pgSQL czyli nie w samym SQLu a w jego proceduralnym rozszerzeniu. Niestety to rozwiązanie jest tak wolne, że nie wiem czy będę miał cierpliwość czekać na zakończenie działania – uruchomiłem dla Easter Monster, czekam już ponad 1 500 sekund i nic.

Wydaje mi się, że po pierwsze można to napisać lepiej w SQL, ale to nie jest właściwy język do np. rekurencyjnych algorytmów z nawrotami. Wątpię aby przy zastosowaniu wielu optymalizacji udało się uzyskać wynik zbliżony do – nie oszukujmy się – lamerskiego kodu w JavaScript jaki zaprezentowałem w 2005 w ramach uczenia się JavaScripta. JavaScript jest znacznie sensowniejszym językiem do implementowania takich algorytmów. Być może kiedyś pokuszę się o napisanie (jak mi się będzie bardzo nudziło) rozwiązania w mojej ulubionej Javie. Zakładam, że rozwiązanie w Javie śmigałoby szybciej od JavaScriptu, choć silnik JavaScriptu „V8” używany w Chromie to podobno prawdziwe cacko (demon szybkości), więc nie wiadomo czy i o ile lepszy wynik mógłbym osiągnąć.


Generalnie jestem zniechęcony do Sudoku – strasznie to nudne i żmudne – rozwiązywanie na kartce jest wręcz upierdliwe. To zabawa dobra dla komputerów!

Co innego Kakuro – tę grę, choć pozornie wydaje się podobna do Sudoku lubię bardzo i rozwiązuję często. Wydaje mi się, że jest w niej znacznie więcej myślenia i mniej żmudnego wpisywania, ścierania itp. A po drugie – zrobienie dobrego algorytmu nie jest tak proste jak dla Sudoku – zwykły brutal-force nie wystarczy…

Trudne układy Sudoku są tak trudne, że praktycznie niemożliwe do rozwiązania dla człowieka (np. Al Escargot), a trudne układy w Kakuro – wymagają sporo myślenia jednak wydaje mi się, że częściej da się je rozwiązać za pomocą dedukcji i bez uciekania się do metody prób i błędów.


PS. Coraz bardziej brakuje mi możliwości uruchamiania JavaScriptu na tym blogu. To dziwne bo na google’owskim Bloggerze – jak widać z choćby powyższego przykładu – można było uruchamiać JavaScript. Przez ten brak nie mogę przenieść tutaj swojego starego Sudoku Solvera, a szkoda. A może jednak da się jakoś zaczarować i uruchamiać JavaScript – choćby w takiej ograniczonej formie jak na Bloggerze?

Advertisements

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s