Crea un risolutore di Sudoku in Java

1. Panoramica

In questo articolo, esamineremo il puzzle di Sudoku e gli algoritmi utilizzati per risolverlo.

Successivamente, implementeremo soluzioni in Java. La prima soluzione sarà un semplice attacco di forza bruta. Il secondo utilizzerà la tecnica Dancing Links.

Teniamo presente che il focus ci concentreremo sugli algoritmi e non sul design OOP.

2. Il Sudoku Puzzle

In poche parole, il Sudoku è un puzzle di posizionamento di numeri combinatori con una griglia di celle 9 x 9 parzialmente riempita con numeri da 1 a 9. L'obiettivo è riempire i campi vuoti rimanenti con il resto dei numeri in modo che ogni riga e colonna ne abbia solo uno numero di ogni tipo.

Inoltre, ogni sottosezione 3 x 3 della griglia non può avere alcun numero duplicato. Il livello di difficoltà aumenta naturalmente con il numero di campi vuoti in ogni tabellone.

2.1. Scheda di prova

Per rendere la nostra soluzione più interessante e per convalidare l'algoritmo, utilizzeremo la tavola del "sudoku più difficile del mondo", che è:

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

2.2. Consiglio risolto

E, per rovinare rapidamente la soluzione, il puzzle risolto correttamente ci darà il seguente risultato:

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. Algoritmo di backtracking

3.1. introduzione

L'algoritmo di backtracking cerca di risolvere il puzzle testando ogni cella per una soluzione valida.

Se non c'è violazione dei vincoli, l'algoritmo passa alla cella successiva, inserisce tutte le potenziali soluzioni e ripete tutti i controlli.

Se c'è una violazione, incrementa il valore della cella. Una volta, il valore della cella raggiunge 9 e vi è ancora violazione, l'algoritmo torna alla cella precedente e aumenta il valore di quella cella.

Prova tutte le soluzioni possibili.

3.2. Soluzione

Prima di tutto, definiamo la nostra scheda come un array bidimensionale di numeri interi. Useremo 0 come cella vuota.

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

Creiamo un metodo resol () che prenda la scheda come parametro di input e itera attraverso righe, colonne e valori testando ogni cella per una soluzione valida:

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

Un altro metodo di cui avevamo bisogno è il metodo isValid () , che controllerà i vincoli di Sudoku, ovvero controlla se la riga, la colonna e la griglia 3 x 3 sono valide:

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

Questi tre controlli sono relativamente simili. Innanzitutto, iniziamo con i controlli di riga:

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

Successivamente, utilizziamo un codice quasi identico per convalidare la colonna:

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

Inoltre, dobbiamo convalidare la sottosezione 3 x 3:

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

Infine, abbiamo bisogno di un metodo checkConstraint () :

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

Una volta, tutto ciò che viene fatto è il metodo Valid () può semplicemente restituire true .

Siamo quasi pronti per testare la soluzione ora. L'algoritmo è fatto. Tuttavia, restituisce solo vero o falso .

Pertanto, per controllare visivamente il tabellone, è sufficiente stampare il risultato. Apparentemente, questo non fa parte dell'algoritmo.

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

Abbiamo implementato con successo l'algoritmo di backtracking che risolve il puzzle di Sudoku!

Ovviamente, c'è spazio per miglioramenti poiché l'algoritmo controlla ingenuamente ogni possibile combinazione più e più volte (anche se sappiamo che la soluzione particolare non è valida).

4. Collegamenti danzanti

4.1. Copertura esatta

Diamo un'occhiata a un'altra soluzione. Il Sudoku può essere descritto come un problema di copertura esatta, che può essere rappresentato da una matrice di incidenza che mostra la relazione tra due oggetti.

Ad esempio, se prendiamo numeri da 1 a 7 e la raccolta di insiemi S = {A, B, C, D, E, F} , dove:

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

Il nostro obiettivo è selezionare tali sottoinsiemi in modo che ogni numero sia presente solo una volta e nessuno venga ripetuto, da cui il nome.

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 questo tutorial, abbiamo discusso due soluzioni a un sudoku con Java core. L'algoritmo di backtracking, che è un algoritmo di forza bruta, può risolvere facilmente il puzzle standard 9 × 9.

È stato discusso anche l'algoritmo di Dancing Links leggermente più complicato. Entrambi risolvono i puzzle più difficili in pochi secondi.

Infine, come sempre, il codice utilizzato durante la discussione può essere trovato su GitHub.