Créer un solveur de Sudoku en Java

1. Vue d'ensemble

Dans cet article, nous allons examiner le puzzle de Sudoku et les algorithmes utilisés pour le résoudre.

Ensuite, nous implémenterons des solutions en Java. La première solution sera une simple attaque par force brute. Le second utilisera la technique Dancing Links.

Gardons à l'esprit que nous allons nous concentrer sur les algorithmes et non sur la conception de la POO.

2. Le puzzle Sudoku

En termes simples, Sudoku est un casse-tête combinatoire de placement de nombres avec une grille de 9 x 9 cellules partiellement remplie avec des nombres de 1 à 9. Le but est de remplir les champs vides restants avec le reste des nombres de sorte que chaque ligne et colonne n'en ait qu'un nombre de chaque type.

De plus, chaque sous-section 3 x 3 de la grille ne peut pas non plus avoir de numéro dupliqué. Le niveau de difficulté augmente naturellement avec le nombre de champs vides dans chaque tableau.

2.1. Conseil d'essai

Pour rendre notre solution plus intéressante et valider l'algorithme, nous allons utiliser le tableau «sudoku le plus dur du monde», qui est:

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

2.2. Conseil résolu

Et, pour gâcher la solution rapidement - le puzzle correctement résolu nous donnera le résultat suivant:

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. Algorithme de retour en arrière

3.1. introduction

L'algorithme de retour en arrière tente de résoudre le casse-tête en testant chaque cellule pour une solution valide.

S'il n'y a pas de violation des contraintes, l'algorithme passe à la cellule suivante, remplit toutes les solutions potentielles et répète toutes les vérifications.

S'il y a une violation, cela incrémente la valeur de la cellule. Une fois, la valeur de la cellule atteint 9 et il y a toujours violation, puis l'algorithme revient à la cellule précédente et augmente la valeur de cette cellule.

Il essaie toutes les solutions possibles.

3.2. Solution

Tout d'abord, définissons notre tableau comme un tableau à deux dimensions d'entiers. Nous utiliserons 0 comme cellule vide.

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

Créons une méthode solve () qui prend la carte comme paramètre d'entrée et itère à travers les lignes, les colonnes et les valeurs en testant chaque cellule pour une solution valide:

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

Une autre méthode dont nous avions besoin est la méthode isValid () , qui va vérifier les contraintes de Sudoku, c'est-à-dire vérifier si la ligne, la colonne et la grille 3 x 3 sont valides:

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

Ces trois contrôles sont relativement similaires. Commençons par les vérifications de lignes:

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

Ensuite, nous utilisons un code presque identique pour valider la colonne:

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

De plus, nous devons valider la sous-section 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; }

Enfin, nous avons besoin d'une méthode 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; }

Une fois, tout ce qui est fait, la méthode isValid () peut simplement retourner true .

Nous sommes presque prêts à tester la solution maintenant. L'algorithme est terminé. Cependant, il renvoie uniquement vrai ou faux .

Par conséquent, pour vérifier visuellement le tableau, nous devons simplement imprimer le résultat. Apparemment, cela ne fait pas partie de l'algorithme.

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

Nous avons mis en œuvre avec succès un algorithme de retour en arrière qui résout le puzzle Sudoku!

De toute évidence, il y a place pour des améliorations car l'algorithme vérifie naïvement chaque combinaison possible encore et encore (même si nous savons que la solution particulière n'est pas valide).

4. Liens dansants

4.1. Couverture exacte

Regardons une autre solution. Sudoku peut être décrit comme un problème de couverture exacte, qui peut être représenté par une matrice d'incidence montrant la relation entre deux objets.

Par exemple, si nous prenons les nombres de 1 à 7 et la collection d'ensembles S = {A, B, C, D, E, F} , où:

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

Notre objectif est de sélectionner des sous-ensembles tels que chaque numéro n'est là qu'une seule fois et aucun n'est répété, d'où le nom.

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

Dans ce didacticiel, nous avons discuté de deux solutions à un puzzle de sudoku avec le noyau Java. L'algorithme de retour en arrière, qui est un algorithme de force brute, peut résoudre facilement le casse-tête standard 9 × 9.

L'algorithme Dancing Links un peu plus compliqué a également été discuté. Les deux résolvent les énigmes les plus difficiles en quelques secondes.

Enfin, comme toujours, le code utilisé lors de la discussion se trouve à l'adresse over sur GitHub.