SAE21_2023/SudokuSolver.java

/**
 * La classe SudokuSolver fournit des méthodes pour résoudre une grille de Sudoku.
 * Elle utilise une approche de récursion avec backtracking pour trouver la solution.
 */
public class SudokuSolver {

    /**
     * Résout la grille de Sudoku donnée.
     * @param grid La grille de Sudoku à résoudre.
     * @return True si la grille a été résolue avec succès, False si elle est insoluble.
     */
    public boolean solve(Grid grid) {
        long startTime = System.nanoTime(); // Temps de début de la résolution

        boolean isSolved = solveRecursive(grid);

        long endTime = System.nanoTime(); // Temps de fin de la résolution
        long duration = (endTime - startTime) / 1_000_000; // Conversion de nanosecondes en millisecondes

        if (isSolved) {
            System.out.println("La grille a été résolue en " + duration + " millisecondes.");
        } else {
            System.out.println("La grille est insoluble.");
        }

        return isSolved;
    }

    /**
     * Méthode récursive pour résoudre la grille de Sudoku.
     * Utilise une approche de backtracking pour explorer toutes les possibilités.
     * @param grid La grille de Sudoku à résoudre.
     * @return True si la grille a été résolue avec succès, False si elle est insoluble.
     */
    private boolean solveRecursive(Grid grid) {
        for (int row = 0; row < 9; row++) {
            for (int col = 0; col < 9; col++) {
                if (grid.getCell(row, col).getValue() == 0) {
                    for (int num = 1; num <= 9; num++) {
                        if (isSafe(grid, row, col, num)) {
                            grid.getCell(row, col).setValue(num);
                            if (solveRecursive(grid)) {
                                return true;
                            }
                            // Backtrack si la solution actuelle n'est pas valide
                            grid.getCell(row, col).setValue(0);
                        }
                    }
                    // Aucun nombre n'est valide, donc la grille est insoluble
                    return false;
                }
            }
        }
        // Toutes les cellules ont été remplies, la grille est résolue
        return true;
    }

    /**
     * Vérifie si le placement d'un nombre dans une cellule est sûr.
     * @param grid La grille de Sudoku.
     * @param row L'indice de ligne de la cellule.
     * @param col L'indice de colonne de la cellule.
     * @param num Le nombre à vérifier.
     * @return True si le placement est sûr, False sinon.
     */
    public boolean isSafe(Grid grid, int row, int col, int num) {
        // Vérifier la ligne
        for (int i = 0; i < 9; i++) {
            if (grid.getCell(row, i).getValue() == num) {
                return false;
            }
        }

        // Vérifier la colonne
        for (int i = 0; i < 9; i++) {
            if (grid.getCell(i, col).getValue() == num) {
                return false;
            }
        }

        // Vérifier la région 3x3
        int startRow = row - row % 3;
        int startCol = col - col % 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid.getCell(i + startRow, j + startCol).getValue() == num) {
                    return false;
                }
            }
        }

        return true;
    }
}