„Sudoku solver” – tym razem nie wyszło – post mortem

Próbowałam zrobić program rozwiązujący sudoku. Gdyby to nie było wystarczająco skomplikowane dorzuciłam do tego równoległość. Nie wyszło. Ale dlaczego?

Sudoku – 9 wierszy, 9 kolumn -> 81 kratek, podzielonych na 9 kwadratów po 9 kratek, w każdej cyfra z przedziału [1-9]. Cyfry nie mogą się powtarzać w obrębie wiersza, kolumny i kwadratu. Niezbyt skomplikowane, prawda?

Początek był prosty. Komórka. Komórka ma wartość lub listę kandydujących wartości. 

https://gist.github.com/jezinka/477939188cb4086133232a1862662831

Dalej plansza. Plansza ma komórki. 81. 9 wierszy, 9 kolumn. 

https://gist.github.com/jezinka/5e01e21486854f74e624019ed68e51f9

Kolejne rzeczy do stworzenia to metody pobierające komórki dla wiersza, kolumny i kwadratu. Jak na razie standard. Nie dzieje się tutaj nic zbyt skomplikowanego. Dla uspójnienia wszystkie zwracają tablicę z komórkami dlatego spłaszczam dwuwymiarowy kwadrat przed zwróceniem go z funkcji.

https://gist.github.com/jezinka/fcb24833ba4eedbf545cdb8a2efcba8b

I myślę, że tu zaczęły się pierwsze problemy z programem. Zamiast skupić się na rozwiązaniu problemu zaczęłam jednocześnie pisać i refaktoryzować. Powstaly w tym czasie inne metody jak getValueForColumn(), getValueForRecord(),  getEmptyCell(), a także dwie dość ważne:

https://gist.github.com/jezinka/a7fc3d53889b73d98bf45a33b84f4928

Ogólnie najlepiej i najszybciej kod powstawał wtedy kiedy cały dom już spał, bo niestety dwulatki potrafią być bardzo absorbujące. Z tym, że rano trzeba wstać do pracy i nie można siedzieć już pół nocy jak za studenckich czasów. Tyle kodu wystarczyło żeby rozwiązywać najprostsze warianty sudoku. Działało? Tak, ale nie dla wszystkich. Po długich poszukiwaniach doszłam do tego, że część z plansz branych ze strony internetowej z sudoku ma więcej niż jedno rozwiązanie. Czyli jest nieprawidłowych… cóż trochę czasu na to zeszło.

Kolejną techniką, którą zaimplementowałam była w sumie nieoczywista, bo opierała się na wyszukiwaniu par kandydatów. Coś co znalazłam później opisane na tej stronie KLIK

https://gist.github.com/jezinka/024aae1c3b17347b28b48224b4420f32

Czemu wybrałam akurat tą pomijając bardziej oczywistą technikę ustalenia ’pojedynczej pozycji’? Zawinił tu mój brak researchu i ustalonego planu działania. Trochę było działania z partyzanta. Na zasadzie – jak rozwiązuję sudoku, to korzystam trochę z takiej techniki, potem takiej i wychodzi. Ale tu przydałoby się spojrzenie na to, jakie techniki istnieją w ogóle, zastanowienie się, które mogą dać najwięcej korzyści przy najmniejszym wkładzie i pójście tak wytyczoną drogą.

Ok. Mam już zaimplementowane 2 techniki dochodzenia do jedynego kandydata w komórce. Więc co jest oczywistym następnym krokiem w momencie, w którym część sudoku daje się rozwiązać? 

ZRÓWNOLEGLIĆ

Star Trek Reaction GIF - Find & Share on GIPHY

Widzę w oddali tą równię pochyłą. No, ale pociągnijmy to dalej. Importuję grails.async.Promises.* i zaczynamy zabawę:

https://gist.github.com/jezinka/e0ae4235c3e74f7660940f756ab53069

Jak widać metody rozwiązywania – czyli wstawianie wartości do komórki i usuwanie kandydatów zostało przeniesione do metody resolve(), która w zależności od tego czy na planszy pojawiły się jakieś zmiany zwraca true lub false. Zapobiegło to wpadnięciu w nieskończoną pętlę poszukiwania rozwiązania bez efektu. A skąd tu nagle pszczółki? Robiąc research (a jednak!) natknęłam się na opis algorytmu Artificial Bee Colony (ABC) i jego wykorzystanie w wielowątkowym rozwiązywaniu sudoku. Idea wydała mi się ciekawa. W oryginalnym algorytmie są 3 wyspecjalizowane grupy pszczółek, z których każda zajmuje się trochę innymi zadaniami. Ostatecznie zrezygnowałam z tego podejścia, ale ślady pozostały.

Po zrównolegleniu rozwiązania niestety sudoku, które wcześniej się rozwiązywało, teraz przestało. Dziwne? Wcale nie 😉 Po prostu cała sprawa sekcji krytycznych i semaforów została przeze mnie olana, więc nic dziwnego, że przestało działać.

Jaki jest następny krok? Przede wszystkim muszę usiąść i na sucho, z ołówkiem w ręku, przeanalizować bardziej zaawansowane metody rozwiązywania sudoku. W tym celu mam już kupione 500 sudoku do rozwiązywania w autobusie 😉 Dalej, jak już ogarnę to co najważniejsze, trzeba będzie zabrać się do implementacji poszczególnych rozwiązań. Na początku na jednym wątku, najlepiej na tych sudoku, które samej udało mi się rozwiązać. Jak się skończą to w dalszym ciągu lepiej sprawdzać na bieżąco czy dane sudoku da się rozwiązać zamiast szukać bugów. Dopiero taki działający prawidłowo system można próbować zrównoleglać. Do tego dorzucić kilkanaście asercji i można jechać 🙂

I chyba najważniejsze – wygnać dziecko razem z tatusiem z domu na długi spacer i wtedy usiąść na spokojnie do pracy nad kodem 😉

Dodaj komentarz

Twój adres e-mail nie zostanie opublikowany. Wymagane pola są oznaczone *

Witryna wykorzystuje Akismet, aby ograniczyć spam. Dowiedz się więcej jak przetwarzane są dane komentarzy.