SAE21_2023/GenerateGrid.java

import java.util.Random;

/**
 * Cette classe génère une grille de Sudoku aléatoire.
 */
public class GenerateGrid {
    private static final int GRID_SIZE = 9;
    private static final int EMPTY_CELL = 0;
    private static int minimumClues = 25; // Nombre de "clues" par défaut

    /**
     * Méthode principale pour tester la génération d'une grille ( Seulement pour le debug ).
     * @param args Arguments de la ligne de commande (non utilisés).
     */
    public static void main(String[] args) {
        Grid grid = generateSudokuGrid(minimumClues); // Utilisation de la variable pour générer la grille
        printGrid(grid);
    }

    /**
     * Génère une grille de Sudoku.
     * @param numberOfClues Le nombre de "clues" (indices déjà remplis) à générer.
     * @return La grille de Sudoku générée.
     */
    public static Grid generateSudokuGrid(int numberOfClues) {
        minimumClues = numberOfClues; // Met à jour le nombre de "clues"

        Grid grid = new Grid();
        solveSudoku(grid);
        ensureUniqueSolution(grid); // Vérifie et assure une solution unique
        removeNumbers(grid);
        return grid;
    }

    /**
     * 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, sinon False.
     */
    private static boolean solveSudoku(Grid grid) {
        return solveSudokuHelper(grid, 0, 0);
    }

    /**
     * Méthode auxiliaire récursive pour résoudre la grille de Sudoku.
     * @param grid La grille de Sudoku à résoudre.
     * @param row L'indice de ligne actuel.
     * @param col L'indice de colonne actuel.
     * @return True si la grille a été résolue avec succès, sinon False.
     */
    private static boolean solveSudokuHelper(Grid grid, int row, int col) {
        if (row == GRID_SIZE) {
            row = 0;
            if (++col == GRID_SIZE) {
                return true;
            }
        }

        if (grid.getCell(row, col).getValue() != EMPTY_CELL) {
            return solveSudokuHelper(grid, row + 1, col);
        }

        Random random = new Random();
        int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        shuffleArray(numbers, random);

        for (int num : numbers) {
            if (isValidMove(grid, row, col, num)) {
                grid.getCell(row, col).setValue(num);
                if (solveSudokuHelper(grid, row + 1, col)) {
                    return true;
                }
                grid.getCell(row, col).setValue(EMPTY_CELL);
            }
        }

        return false;
    }

    /**
     * Vérifie si un mouvement donné est valide.
     * @param grid La grille de Sudoku.
     * @param row L'indice de ligne.
     * @param col L'indice de colonne.
     * @param num Le nombre à placer.
     * @return True si le mouvement est valide, sinon False.
     */
    private static boolean isValidMove(Grid grid, int row, int col, int num) {
        for (int i = 0; i < GRID_SIZE; i++) {
            if (grid.getCell(row, i).getValue() == num || grid.getCell(i, col).getValue() == num) {
                return false;
            }
        }

        int boxRow = row - row % 3;
        int boxCol = col - col % 3;

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (grid.getCell(boxRow + i, boxCol + j).getValue() == num) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * Mélange les éléments d'un tableau.
     * @param array Le tableau à mélanger.
     * @param random L'instance de Random à utiliser.
     */
    private static void shuffleArray(int[] array, Random random) {
        for (int i = array.length - 1; i > 0; i--) {
            int index = random.nextInt(i + 1);
            int temp = array[index];
            array[index] = array[i];
            array[i] = temp;
        }
    }

    /**
     * Vérifie et assure qu'il y a une solution unique pour la grille de Sudoku.
     * @param grid La grille de Sudoku.
     * @return True si la grille a une solution unique, sinon False.
     */
    private static boolean ensureUniqueSolution(Grid grid) {
        return hasUniqueSolution(grid, 0);
    }

    /**
     * Vérifie si la grille de Sudoku a une solution unique.
     * @param grid La grille de Sudoku à vérifier.
     * @param count Le nombre de solutions trouvées jusqu'à présent.
     * @return True si la grille a une solution unique, sinon False.
     */
    private static boolean hasUniqueSolution(Grid grid, int count) {
        // Recherche de solutions supplémentaires après la première
        if (count > 1) {
            return false;
        }

        // Recherche de solutions
        if (!solveSudoku(grid)) {
            return false; // Aucune solution trouvée
        }

        count++; // Une solution trouvée

        if (count == 1 && !hasMultipleSolutions(grid)) {
            return true; // Une solution unique trouvée
        }

        // Plusieurs solutions trouvées
        return false;
    }

    /**
     * Vérifie si la grille de Sudoku a plusieurs solutions.
     * @param grid La grille de Sudoku à vérifier.
     * @return True si la grille a plusieurs solutions, sinon False.
     */
    private static boolean hasMultipleSolutions(Grid grid) {
        return solveSudoku(grid); // Si une deuxième solution est trouvée, la grille a plusieurs solutions
    }

    /**
     * Supprime les nombres de la grille pour créer une énigme de Sudoku.
     * @param grid La grille de Sudoku.
     */
    public static void removeNumbers(Grid grid) {
        Random random = new Random();

        while (countClues(grid) > minimumClues) {
            int row = random.nextInt(GRID_SIZE);
            int col = random.nextInt(GRID_SIZE);
            int value = grid.getCell(row, col).getValue();
            grid.getCell(row, col).setValue(EMPTY_CELL);

            Grid tempGrid = new Grid();
            if (!solveSudoku(tempGrid)) {
                grid.getCell(row, col).setValue(value);
            }
        }
    }

    /**
     * Compte le nombre de "clues" dans la grille.
     * @param grid La grille de Sudoku.
     * @return Le nombre de "clues" dans la grille.
     */
    private static int countClues(Grid grid) {
        int count = 0;
        for (int row = 0; row < GRID_SIZE; row++) {
            for (int col = 0; col < GRID_SIZE; col++) {
                if (grid.getCell(row, col).getValue() != EMPTY_CELL) {
                    count++;
                }
            }
        }
        return count;
    }

    /**
     * Affiche la grille de Sudoku dans la console.
     * @param grid La grille de Sudoku à afficher.
     */
    public static void printGrid(Grid grid) {
        for (int row = 0; row < GRID_SIZE; row++) {
            for (int col = 0; col < GRID_SIZE; col++) {
                System.out.print(grid.getCell(row, col).getValue() + " ");
            }
            System.out.println();
        }
    }
}