[groovy] Sudoku Backtracking – ostatnie starcie

Uznałam, że nie ma co udawać, że komputer rozwiązuje cokolwiek symulując człowieka i postanowiłam zaimplementować algorytm z nawrotami (backtracking). To, mam nadzieję, moja ostatnia próba rozwiązania sudoku z pomocą programowania.

Ogólna idea jest taka, żeby wybierać wartość i jeśli wartość jest ok posuwać się naprzód, aż do momentu kiedy stwierdzimy, że to nie była dobra wartość. Wtedy trzeba się wrócić i wybrać inną. I tak aż do momentu kiedy znajdziemy poprawne rozwiązanie.

Jak to mówią, zanim napisze się kod warto najpierw rozrysować sobie wszystko na kartce. Grunt żeby móc się rozczytać samemu 😀

• 

• 

Pierwsze próby rozpisania na sudoku 4×4. Można dostrzec próbę zidentyfikowania kroków potrzebnych o znalezienia rozwiązania: kiedy wstawiać wartość – kiedy resetować, kiedy wracać – kiedy przechodzić dalej

Na początek przyda się ustalenie kilku obiektów w klasie SudokuBacktracking. Przyda mi się tablica, będąca po prostu planszą. Wskaźniki na obecnie przetwarzaną kolumnę i rząd. Potrzebuję jeszcze czegoś gdzie mogę przechowywać liczby, które są już powstawiane na wejściu i nie powinny się zmienić. Będę je przechowywać w formie [„00”:true, „01”:false, …].

	SudokuBacktracking(List<List<Integer>> board) {
	this.board = board.collect { it.collect() }
	this.rowIndex = 0
	this.columnIndex = 0
	this.board.eachWithIndex { List<Integer> row, int i -> row.eachWithIndex { int col, int j -> this.isFixedNumber.put("$i$j".toString(), col != 0) } }
	}

view raw SudokuBacktracking.groovy hosted with ❤ by GitHub

Na początek ustalenie jak powinny się zachowywać wskaźniki na kolumnę i rząd przy przechodzeniu do następnej i poprzedniej komórki.

	private void nextCell() {
	if (columnIndex < this.board.size() – 1) {
	columnIndex++
	} else {
	columnIndex = 0
	rowIndex++
	}
	}
	private void previousCell() {
	if (columnIndex > 0) {
	columnIndex–
	} else {
	columnIndex = this.board.size() – 1
	rowIndex–
	}
	}

view raw SudokuBacktracking.groovy hosted with ❤ by GitHub

Zaczynajmy zawsze z wizją końca – czas na metodę, która powie, czy sudoku jest już rozwiązane – czy wszystkie komórki mają wartość inną niż zero?

	boolean isResolved() {
	return board.flatten().every { it != 0 } && isValid()
	}

view raw SudokuBacktracking.groovy hosted with ❤ by GitHub

I teraz jak już wiadomo jak się przemieszczać i kiedy można zakończyć zabawę można przejść do najważniejszego: jak wygląda krok rozwiązania. Kiedy i co wsadzać w komórkę.

	void step() {
	if (isFixedNumber["$rowIndex$columnIndex" as String]) {
	nextCell()
	} else {
	int cell = board[rowIndex][columnIndex]
	int value = ++cell
	if (value <= 9) {
	board[rowIndex][columnIndex] = value
	if (this.isValid()) {
	nextCell()
	}
	} else {
	board[rowIndex][columnIndex] = 0
	do {
	previousCell()
	} while (isFixedNumber["$rowIndex$columnIndex" as String])
	}
	}
	printTable()
	}

view raw SudokuBacktracking.groovy hosted with ❤ by GitHub

1. Jeśli w komórce jest liczba, którą dostałam za darmo – idę do następnej komórki
2. W przeciwnym wypadku pobieram wartość komórki do zmiennej. Zwiększam jej wartość o 1 i sprawdzam, czy nie jest większa od 9.
   1. Jeśli nie jest większa wrzucam ją do komórki i waliduję planszę – jeśli plansza jest prawidłowa – przesuwam wskaźnik na następną komórkę
   2. Jeśli jest większa od 9, resetuję to pole na planszy wpisując 0 i przesuwam się w tył do pierwszej komórki, która nie ma w sobie stałej wartości.

Tylko włożyć to w pętle while i można wyliczać:

	(…)
	while (!sudokuBacktracking.isResolved()) {
	sudokuBacktracking.step()
	println(sudokuBacktracking.textOutput)
	}
	println("Done")
	(…)

view raw ConsoleOutput.groovy hosted with ❤ by GitHub

Zwykłe wyjście na konsole nie jest jakoś bardzo imponujące:

• 

• 

• 

• 

• 

• 

• 

• 

Tak wygląda to w praktyce z użyciem biblioteki Processing:

Walidacja planszy to sprawdzanie, czy w każdym rekordzie, wierszu i kwadracie wszystkie liczby pojawiają się tylko raz (oczywiście z pominięciem 0)

	private boolean isValid() {
	boolean right = true
	board.each { row ->
	if (row.findAll { it != 0 }.countBy { it }.any { k, v -> v != 1 }) {
	right = false
	}
	}
	(0..this.board.size() – 1).each { colNum ->
	List<Integer> column = board.collect { it[colNum] }
	if (column.findAll { it != 0 }.countBy { it }.any { k, v -> v != 1 }) {
	right = false
	}
	}
	Map<String, List<Integer>> squares = [:]
	board.eachWithIndex { List<Integer> row, int i ->
	row.eachWithIndex { int entry, int j ->
	String key = findSquare(i, j)
	if (!squares.containsKey(key)) {
	squares[key] = [entry]
	} else {
	squares[key] << entry
	}
	}
	}
	squares.values().each { square ->
	if (square.findAll { it != 0 }.countBy { it }.any { k, v -> v != 1 }) {
	right = false
	}
	}
	return right
	}
	private String findSquare(int i, int j) {
	int squareCount = Math.sqrt(board.size()) as Integer
	return "${Math.floor(i / squareCount)}${Math.floor(j / squareCount)}".toString()
	}

view raw SudokuBacktracking.groovy hosted with ❤ by GitHub

I to by było na tyle. Cały kod na githubie