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

	class Cell {
	Integer value
	List<Integer> candidates
	}

view raw Cell.groovy hosted with ❤ by GitHub

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

	class Board {
	Integer[][] sample = [
	[0, 0, 0, 0, 0, 2, 0, 0, 3],
	[6, 0, 0, 0, 3, 0, 0, 0, 9],
	[9, 0, 0, 0, 0, 0, 0, 0, 0],
	[0, 4, 5, 0, 0, 0, 6, 0, 0],
	[8, 0, 0, 6, 0, 0, 3, 0, 7],
	[0, 0, 0, 0, 0, 0, 8, 5, 2],
	[4, 9, 0, 0, 6, 3, 0, 0, 5],
	[0, 3, 0, 5, 0, 8, 0, 0, 0],
	[0, 0, 0, 4, 9, 0, 0, 0, 0]
	]
	Cell[][] board = new Cell[9][9]
	Board() {
	for (int i = 0; i < sample.length; i++) {
	for (int j = 0; j < sample[i].length; j++) {
	board[i][j] = new Cell(value: sample[i][j])
	}
	}
	}
	}

view raw Board.groovy hosted with ❤ by GitHub

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.

	Cell[] getRecord(int rowNum) { return board[rowNum] }
	Cell[] getColumn(int colNum) { return (0..<board.length).collect { board[it][colNum] } }
	Cell[] getSquare(int rowNum, int colNum) {
	int beginRow = rowNum – rowNum % 3
	int beginColumn = colNum – colNum % 3
	return (beginRow..<beginRow + 3).collect { row ->
	(beginColumn..<beginColumn + 3).collect { column ->
	board[row][column]
	}
	}.flatten()
	}

view raw Board.groovy hosted with ❤ by GitHub

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:

	void fillCandidates() {
	for (int i = 0; i < board.length; i++) {
	for (int j = 0; j < board[i].length; j++) {
	Cell cell = board[i][j]
	if (cell.value == 0) {
	cell.candidates = (1..9)
	removeKnown(i, j)
	assert cell.candidates.size() > 0
	} else {
	cell.candidates = []
	}
	}
	}
	}
	void removeKnown(int rowNum, int colNum) {
	Cell cell = board[rowNum][colNum]
	cell.candidates -= getValuesForColumn(colNum)
	cell.candidates -= getValuesForRecord(rowNum)
	cell.candidates -= getValuesForSquare(rowNum, colNum)
	}

view raw Board.groovy hosted with ❤ by GitHub

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. 

	boolean removePairsCandidates(Cell cell, Cell[] cells) {
	boolean theSameRecord = false
	boolean change = false
	Cell twinCell
	cells.each {
	if (it != cell && it.candidates == cell.candidates) {
	theSameRecord = true
	twinCell = it
	}
	}
	if (theSameRecord) {
	cells.findAll {
	it != cell && it != twinCell && it.candidates
	}.each { otherCell ->
	cell.candidates.each { value ->
	if (otherCell.candidates.contains(value)) {
	otherCell.candidates -= value
	change = true
	}
	}
	}
	}
	return change
	}

view raw Board.groovy hosted with ❤ by GitHub

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Ć

https://giphy.com/gifs/captain-facepalm-picard-XsUtdIeJ0MWMo

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

	while (board.emptyCells.size() > 0 || results.any { it }) {
	List bees = []
	(0..10).each {
	Cell cell = board.getCell()
	bees << task { board.resolve(cell) }
	}
	results = waitAll(bees)
	}

view raw Main.groovy hosted with ❤ by GitHub

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 😉