Erstellen Sie einen Sudoku-Solver in Java

1. Übersicht

In diesem Artikel werden wir uns das Sudoku-Puzzle und die Algorithmen ansehen, mit denen es gelöst wird.

Als nächstes implementieren wir Lösungen in Java. Die erste Lösung wird ein einfacher Brute-Force-Angriff sein. Der zweite wird die Dancing Links-Technik verwenden.

Denken wir daran, dass wir uns auf die Algorithmen und nicht auf das OOP-Design konzentrieren werden.

2. Das Sudoku-Puzzle

Einfach ausgedrückt ist Sudoku ein kombinatorisches Puzzle zur Platzierung von Zahlen mit einem 9 x 9-Zellenraster, das teilweise mit Zahlen von 1 bis 9 ausgefüllt ist. Ziel ist es, verbleibende leere Felder mit den restlichen Zahlen zu füllen, sodass jede Zeile und Spalte nur eine enthält Anzahl jeder Art.

Darüber hinaus kann in jedem 3 x 3-Unterabschnitt des Rasters keine Nummer dupliziert werden. Der Schwierigkeitsgrad steigt natürlich mit der Anzahl der leeren Felder in jeder Tafel.

2.1. Test Board

Um unsere Lösung interessanter zu gestalten und den Algorithmus zu validieren, verwenden wir das "härteste Sudoku" -Board der Welt:

8 . . . . . . . . . . 3 6 . . . . . . 7 . . 9 . 2 . . . 5 . . . 7 . . . . . . . 4 5 7 . . . . . 1 . . . 3 . . . 1 . . . . 6 8 . . 8 5 . . . 1 . . 9 . . . . 4 . .

2.2. Gelöstes Board

Und um die Lösung schnell zu verderben, liefert das richtig gelöste Rätsel das folgende Ergebnis:

8 1 2 7 5 3 6 4 9 9 4 3 6 8 2 1 7 5 6 7 5 4 9 1 2 8 3 1 5 4 2 3 7 8 9 6 3 6 9 8 4 5 7 2 1 2 8 7 1 6 9 5 3 4 5 2 1 9 7 4 3 6 8 4 3 8 5 2 6 9 1 7 7 9 6 3 1 8 4 5 2

3. Backtracking-Algorithmus

3.1. Einführung

Der Backtracking-Algorithmus versucht, das Rätsel zu lösen, indem jede Zelle auf eine gültige Lösung getestet wird.

Wenn keine Verletzung von Einschränkungen vorliegt, wechselt der Algorithmus zur nächsten Zelle, füllt alle möglichen Lösungen aus und wiederholt alle Überprüfungen.

Wenn eine Verletzung vorliegt, wird der Zellenwert erhöht. Sobald der Wert der Zelle 9 erreicht und immer noch eine Verletzung vorliegt, kehrt der Algorithmus zur vorherigen Zelle zurück und erhöht den Wert dieser Zelle.

Es werden alle möglichen Lösungen ausprobiert.

3.2. Lösung

Zunächst definieren wir unser Board als zweidimensionales Array von ganzen Zahlen. Wir werden 0 als unsere leere Zelle verwenden.

int[][] board = { { 8, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 3, 6, 0, 0, 0, 0, 0 }, { 0, 7, 0, 0, 9, 0, 2, 0, 0 }, { 0, 5, 0, 0, 0, 7, 0, 0, 0 }, { 0, 0, 0, 0, 4, 5, 7, 0, 0 }, { 0, 0, 0, 1, 0, 0, 0, 3, 0 }, { 0, 0, 1, 0, 0, 0, 0, 6, 8 }, { 0, 0, 8, 5, 0, 0, 0, 1, 0 }, { 0, 9, 0, 0, 0, 0, 4, 0, 0 } };

Erstellen wir eine Solve () -Methode, die die Karte als Eingabeparameter verwendet und durch Zeilen, Spalten und Werte iteriert, wobei jede Zelle auf eine gültige Lösung getestet wird:

private boolean solve(int[][] board) { for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) { for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) { if (board[row][column] == NO_VALUE) { for (int k = MIN_VALUE; k <= MAX_VALUE; k++) { board[row][column] = k; if (isValid(board, row, column) && solve(board)) { return true; } board[row][column] = NO_VALUE; } return false; } } } return true; }

Eine andere Methode, die wir brauchten, ist die Methode Valid () , mit der Sudoku-Einschränkungen überprüft werden, dh ob Zeile, Spalte und 3 x 3-Raster gültig sind:

private boolean isValid(int[][] board, int row, int column) { return (rowConstraint(board, row) && columnConstraint(board, column) && subsectionConstraint(board, row, column)); }

Diese drei Prüfungen sind relativ ähnlich. Beginnen wir zunächst mit Zeilenprüfungen:

private boolean rowConstraint(int[][] board, int row) { boolean[] constraint = new boolean[BOARD_SIZE]; return IntStream.range(BOARD_START_INDEX, BOARD_SIZE) .allMatch(column -> checkConstraint(board, row, constraint, column)); }

Als nächstes verwenden wir fast identischen Code, um die Spalte zu validieren:

private boolean columnConstraint(int[][] board, int column) { boolean[] constraint = new boolean[BOARD_SIZE]; return IntStream.range(BOARD_START_INDEX, BOARD_SIZE) .allMatch(row -> checkConstraint(board, row, constraint, column)); }

Darüber hinaus müssen wir den Unterabschnitt 3 x 3 validieren:

private boolean subsectionConstraint(int[][] board, int row, int column) { boolean[] constraint = new boolean[BOARD_SIZE]; int subsectionRowStart = (row / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionRowEnd = subsectionRowStart + SUBSECTION_SIZE; int subsectionColumnStart = (column / SUBSECTION_SIZE) * SUBSECTION_SIZE; int subsectionColumnEnd = subsectionColumnStart + SUBSECTION_SIZE; for (int r = subsectionRowStart; r < subsectionRowEnd; r++) { for (int c = subsectionColumnStart; c < subsectionColumnEnd; c++) { if (!checkConstraint(board, r, constraint, c)) return false; } } return true; }

Schließlich benötigen wir eine checkConstraint () -Methode:

boolean checkConstraint( int[][] board, int row, boolean[] constraint, int column) { if (board[row][column] != NO_VALUE) { if (!constraint[board[row][column] - 1]) { constraint[board[row][column] - 1] = true; } else { return false; } } return true; }

Sobald alles erledigt ist, kann die Methode Valid () einfach true zurückgeben .

Wir sind fast bereit, die Lösung jetzt zu testen. Der Algorithmus ist fertig. Es wird jedoch nur true oder false zurückgegeben .

Um die Karte visuell zu überprüfen, müssen wir nur das Ergebnis ausdrucken. Anscheinend ist dies nicht Teil des Algorithmus.

private void printBoard() { for (int row = BOARD_START_INDEX; row < BOARD_SIZE; row++) { for (int column = BOARD_START_INDEX; column < BOARD_SIZE; column++) { System.out.print(board[row][column] + " "); } System.out.println(); } }

Wir haben erfolgreich einen Backtracking-Algorithmus implementiert, der das Sudoku-Rätsel löst!

Offensichtlich gibt es Raum für Verbesserungen, da der Algorithmus jede mögliche Kombination immer wieder naiv überprüft (obwohl wir wissen, dass die jeweilige Lösung ungültig ist).

4. Tanzende Links

4.1. Genaue Abdeckung

Schauen wir uns eine andere Lösung an. Sudoku kann als Exact Cover-Problem beschrieben werden, das durch eine Inzidenzmatrix dargestellt werden kann, die die Beziehung zwischen zwei Objekten zeigt.

Wenn wir zum Beispiel Zahlen von 1 bis 7 und die Sammlung von Mengen S = {A, B, C, D, E, F} nehmen , wobei:

  • A = {1, 4, 7}
  • B = {1, 4}
  • C = {4, 5, 7}
  • D = {3, 5, 6}
  • E = {2, 3, 6, 7}
  • F = {2, 7}

Unser Ziel ist es, solche Teilmengen so auszuwählen, dass jede Nummer nur einmal vorhanden ist und keine wiederholt wird, daher der Name.

We can represent the problem using a matrix, where columns are numbers and rows are sets:

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | A | 1 | 0 | 0 | 1 | 0 | 0 | 1 | B | 1 | 0 | 0 | 1 | 0 | 0 | 0 | C | 0 | 0 | 0 | 1 | 1 | 0 | 1 | D | 0 | 0 | 1 | 0 | 1 | 1 | 0 | E | 0 | 1 | 1 | 0 | 0 | 1 | 1 | F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

Subcollection S* = {B, D, F} is exact cover:

 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | B | 1 | 0 | 0 | 1 | 0 | 0 | 0 | D | 0 | 0 | 1 | 0 | 1 | 1 | 0 | F | 0 | 1 | 0 | 0 | 0 | 0 | 1 |

Each column has exactly one 1 in all selected rows.

4.2. Algorithm X

Algorithm X is a “trial-and-error approach” to find all solutions to the exact cover problem, i.e. starting with our example collection S = {A, B, C, D, E, F}, find subcollection S* = {B, D, F}.

Algorithm X works as follows:

  1. If the matrix A has no columns, the current partial solution is a valid solution;

    terminate successfully, otherwise, choose a column c (deterministically)

  2. Choose a row r such that Ar, c = 1 (nondeterministically, i.e., try all possibilities)
  3. Include row r in the partial solution
  4. For each column j such that Ar, j = 1, for each row i such that Ai, j = 1,

    delete row i from matrix A anddelete column j from matrix A

  5. Repeat this algorithm recursively on the reduced matrix A

An efficient implementation of the Algorithm X is Dancing Links algorithm (DLX for short) suggested by Dr. Donald Knuth.

The following solution has been heavily inspired by this Java implementation.

4.3. Exact Cover Problem

First, we need to create a matrix that will represent Sudoku puzzle as an Exact Cover problem. The matrix will have 9^3 rows, i.e., one row for every single possible position (9 rows x 9 columns) of every possible number (9 numbers).

Columns will represent the board (again 9 x 9) multiplied by the number of constraints.

We've already defined three constraints:

  • each row will have only one number of each kind
  • each column will have only one number of each kind
  • each subsection will have only one number of each kind

Additionally, there is implicit fourth constraint:

  • only one number can be in a cell

This gives four constraints in total and therefore 9 x 9 x 4 columns in the Exact Cover matrix:

private static int BOARD_SIZE = 9; private static int SUBSECTION_SIZE = 3; private static int NO_VALUE = 0; private static int CONSTRAINTS = 4; private static int MIN_VALUE = 1; private static int MAX_VALUE = 9; private static int COVER_START_INDEX = 1;
private int getIndex(int row, int column, int num) { return (row - 1) * BOARD_SIZE * BOARD_SIZE + (column - 1) * BOARD_SIZE + (num - 1); }
private boolean[][] createExactCoverBoard() { boolean[][] coverBoard = new boolean [BOARD_SIZE * BOARD_SIZE * MAX_VALUE] [BOARD_SIZE * BOARD_SIZE * CONSTRAINTS]; int hBase = 0; hBase = checkCellConstraint(coverBoard, hBase); hBase = checkRowConstraint(coverBoard, hBase); hBase = checkColumnConstraint(coverBoard, hBase); checkSubsectionConstraint(coverBoard, hBase); return coverBoard; } private int checkSubsectionConstraint(boolean[][] coverBoard, int hBase) { for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row += SUBSECTION_SIZE) { for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column += SUBSECTION_SIZE) { for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) { for (int rowDelta = 0; rowDelta < SUBSECTION_SIZE; rowDelta++) { for (int columnDelta = 0; columnDelta < SUBSECTION_SIZE; columnDelta++) { int index = getIndex(row + rowDelta, column + columnDelta, n); coverBoard[index][hBase] = true; } } } } } return hBase; } private int checkColumnConstraint(boolean[][] coverBoard, int hBase) { for (int column = COVER_START_INDEX; column <= BOARD_SIZE; c++) { for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) { for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) { int index = getIndex(row, column, n); coverBoard[index][hBase] = true; } } } return hBase; } private int checkRowConstraint(boolean[][] coverBoard, int hBase) { for (int row = COVER_START_INDEX; row <= BOARD_SIZE; r++) { for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++, hBase++) { for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) { int index = getIndex(row, column, n); coverBoard[index][hBase] = true; } } } return hBase; } private int checkCellConstraint(boolean[][] coverBoard, int hBase) { for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) { for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++, hBase++) { for (int n = COVER_START_INDEX; n <= BOARD_SIZE; n++) { int index = getIndex(row, column, n); coverBoard[index][hBase] = true; } } } return hBase; }

Next, we need to update the newly created board with our initial puzzle layout:

private boolean[][] initializeExactCoverBoard(int[][] board) { boolean[][] coverBoard = createExactCoverBoard(); for (int row = COVER_START_INDEX; row <= BOARD_SIZE; row++) { for (int column = COVER_START_INDEX; column <= BOARD_SIZE; column++) { int n = board[row - 1][column - 1]; if (n != NO_VALUE) { for (int num = MIN_VALUE; num <= MAX_VALUE; num++) { if (num != n) { Arrays.fill(coverBoard[getIndex(row, column, num)], false); } } } } } return coverBoard; }

We are ready to move to the next stage now. Let's create two classes that will link our cells together.

4.4. Dancing Node

Dancing Links algorithm operates on a basic observation that following operation on doubly linked lists of nodes:

node.prev.next = node.next node.next.prev = node.prev

removes the node, while:

node.prev = node node.next = node

restores the node.

Each node in DLX is linked to the node on the left, right, up and down.

DancingNode class will have all operations needed to add or remove nodes:

class DancingNode { DancingNode L, R, U, D; ColumnNode C; DancingNode hookDown(DancingNode node) { assert (this.C == node.C); node.D = this.D; node.D.U = node; node.U = this; this.D = node; return node; } DancingNode hookRight(DancingNode node) { node.R = this.R; node.R.L = node; node.L = this; this.R = node; return node; } void unlinkLR() { this.L.R = this.R; this.R.L = this.L; } void relinkLR() { this.L.R = this.R.L = this; } void unlinkUD() { this.U.D = this.D; this.D.U = this.U; } void relinkUD() { this.U.D = this.D.U = this; } DancingNode() { L = R = U = D = this; } DancingNode(ColumnNode c) { this(); C = c; } }

4.5. Column Node

ColumnNode class will link columns together:

class ColumnNode extends DancingNode { int size; String name; ColumnNode(String n) { super(); size = 0; name = n; C = this; } void cover() { unlinkLR(); for (DancingNode i = this.D; i != this; i = i.D) { for (DancingNode j = i.R; j != i; j = j.R) { j.unlinkUD(); j.C.size--; } } } void uncover() { for (DancingNode i = this.U; i != this; i = i.U) { for (DancingNode j = i.L; j != i; j = j.L) { j.C.size++; j.relinkUD(); } } relinkLR(); } }

4.6. Solver

Next, we need to create a grid consisting of our DancingNode and ColumnNode objects:

private ColumnNode makeDLXBoard(boolean[][] grid) { int COLS = grid[0].length; ColumnNode headerNode = new ColumnNode("header"); List columnNodes = new ArrayList(); for (int i = 0; i < COLS; i++) { ColumnNode n = new ColumnNode(Integer.toString(i)); columnNodes.add(n); headerNode = (ColumnNode) headerNode.hookRight(n); } headerNode = headerNode.R.C; for (boolean[] aGrid : grid) { DancingNode prev = null; for (int j = 0; j < COLS; j++) { if (aGrid[j]) { ColumnNode col = columnNodes.get(j); DancingNode newNode = new DancingNode(col); if (prev == null) prev = newNode; col.U.hookDown(newNode); prev = prev.hookRight(newNode); col.size++; } } } headerNode.size = COLS; return headerNode; }

We'll use heuristic search to find columns and return a subset of the matrix:

private ColumnNode selectColumnNodeHeuristic() { int min = Integer.MAX_VALUE; ColumnNode ret = null; for ( ColumnNode c = (ColumnNode) header.R; c != header; c = (ColumnNode) c.R) { if (c.size < min) { min = c.size; ret = c; } } return ret; }

Finally, we can recursively search for the answer:

private void search(int k) { if (header.R == header) { handleSolution(answer); } else { ColumnNode c = selectColumnNodeHeuristic(); c.cover(); for (DancingNode r = c.D; r != c; r = r.D) { answer.add(r); for (DancingNode j = r.R; j != r; j = j.R) { j.C.cover(); } search(k + 1); r = answer.remove(answer.size() - 1); c = r.C; for (DancingNode j = r.L; j != r; j = j.L) { j.C.uncover(); } } c.uncover(); } }

If there are no more columns, then we can print out the solved Sudoku board.

5. Benchmarks

We can compare those two different algorithms by running them on the same computer (this way we can avoid differences in components, the speed of CPU or RAM, etc.). The actual times will differ from computer to computer.

However, we should be able to see relative results, and this will tell us which algorithm runs faster.

The Backtracking Algorithm takes around 250ms to solve the board.

If we compare this with the Dancing Links, which takes around 50ms, we can see a clear winner. Dancing Links is around five times faster when solving this particular example.

6. Conclusion

In diesem Tutorial haben wir zwei Lösungen für ein Sudoku-Puzzle mit Kern-Java besprochen. Der Backtracking-Algorithmus, ein Brute-Force-Algorithmus, kann das Standard-9 × 9-Rätsel leicht lösen.

Der etwas kompliziertere Dancing Links-Algorithmus wurde ebenfalls diskutiert. Beide lösen die schwierigsten Rätsel innerhalb von Sekunden.

Schließlich ist der während der Diskussion verwendete Code wie immer auf GitHub zu finden.