Close

“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. 

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

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.

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:

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

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 Facepalm 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ę:

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 😉

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: