[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) } }
}

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
}
}

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()
}

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()
}
  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()
}

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

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.

%d bloggers like this: