Sudoku (∼1h30 – ninja – entraînement)
Le but de cet exercice est de concevoir un algorithme permettant de résoudre un sudoku. Un sudoku est défini par une grille de 9 colonnes sur 9 lignes. Chaque case doit contenir un nombre compris entre 1 et 9 inclus. Le but du jeu est de remplir la grille de façon à ce que chacun des chiffres compris entre 1 et 9 apparaisse au plus une fois dans (i) chaque ligne, (ii) chaque colonne et (iii) chacun des sous-carrés représentés sur la figure ci-dessous. Au début du jeu, une vingtaine de chiffres sont déjà placés dans la grille et le joueur doit trouver les chiffres se trouvant dans les autres cases.
La grille résolvant le sudoku représenté ci-dessus se trouve ci-dessous :
Pour commencer, créez un projet nommé sudoku avec une classe Sudoku contenant une méthode main.
Une grille de sudoku est représentée par un tableau de 81 cases (9 lignes sur 9 colonnes). Si une case vaut 0, c'est qu'elle n'est pas encore initialisée, sinon, c'est qu'elle contient une valeur. Pour commencer, copiez-collez le code ci-dessous permettant de créer une grille. Ensuite, ajoutez une boucle permettant d'afficher la grille. Vous veillerez à afficher un point si la case contient 0. Vous devriez obtenir un affichage proche de celui utilisé pour la grille d'exemple, mais sans la représentation des carrés internes.
Nous vous proposons de résoudre votre grille avec une méthode de retour arrière (backtracking en anglais). Cette méthode consiste à tenter des valeurs et, si elles ne permettent pas de résoudre la grille, de revenir en arrière pour essayer une nouvelle valeur. Comme nous aurons besoin de modifier la grille pour tenter des valeurs, il faut savoir quelles valeurs sont données initialement et quelles valeurs sont tentées. Vous devez donc définir un tableau de booléens nommé fixed et assigner à vrai la valeur d'une case si et seulement si la case contient initialement une valeur (c'est-à-dire si la case correspondante dans grid a une valeur différente de 0 initialement).
Modifiez votre programme de façon à ce qu'il résolve le sudoku. Comme expliqué auparavant, le principe de l'algorithme est de parcourir la grille du début à la fin en tentant des valeurs. Dès qu'il est impossible de résoudre la grille avec une valeur précédemment rentrée, il faut revenir en arrière.
À haut niveau, il faut parcourir la grille avec une variable cur. Cette variable est initialisée à 0 et l'algorithme boucle tant que cur n'a pas atteint 81 (ce qui signifie que la grille a été résolue) et que cur n'est pas passé en dessous de 0 (ce qui signifie que la grille ne peut pas être résolue).
Pour un cur donné, l'algorithme doit tenter une nouvelle valeur sur la case grid[cur] (si cette dernière n'est pas donnée initialement) en incrémentant sa valeur. Si cette valeur atteint 10, c'est qu'une valeur tentée dans une case précédente ne permet pas de résoudre la grille. Il faut donc revenir en arrière. Sinon, si cette nouvelle valeur entre en conflit avec une valeur se trouvant dans la grille, il faut essayer la valeur suivante. Enfin, si la nouvelle valeur ne rentre pas en conflit, l'algorithme peut essayer de résoudre le reste de la grille en passant à la case suivante.
Techniquement, à chaque pas de boucle :
- Si la case cur est initialement donnée, il faut avancer cur de 1,
- Sinon, il faut incrémenter la case grid[cur].
Ensuite :
- Si cette case vaut 10, c'est qu'une des valeurs tentées dans une case précédente
ne permet pas de résoudre la grille. Il faut donc :
- Remettre le contenu de la case 0,
- Remonter cur jusqu'à la première précédente case qui n'est pas donnée initialement (pensez à utiliser fixed pour savoir si une case est donnée ou non initialement).
- Sinon, l'algorithme doit vérifier que la nouvelle valeur de grid[cur] est valide, c'est-à-dire qu'elle ne duplique pas une valeur dans une colonne, une ligne ou un des 9 carrés. Si la valeur est valide, l'algorithme peut avancer cur de 1 pour tenter une valeur sur la case suivante. Si la valeur est invalide, il ne faut rien faire : lors du tour de boucle suivante, la valeur suivante de grid[cur] sera tentée.
- Si cette case vaut 10, c'est qu'une des valeurs tentées dans une case précédente
ne permet pas de résoudre la grille. Il faut donc :
Vérifier qu'une valeur est valide n'est pas évident. Nous vous conseillons d'effectuer une unique boucle avec une variable i allant de 0 à 9. Dans cette boucle, il faut vérifier que :
- la valeur se trouvant sur la colonne de cur en iième ligne est différente de grid[cur],
- la valeur se trouvant sur la ligne de cur en iième colonne est différente de grid[cur],
- la iième case du carré interne est différente de grid[cur],
Nous vous conseillons d'utiliser 7 variables pour vérifier que la grille la dernière valeur tentée est valide :
- line : indique sur quelle ligne se trouve cur : cur / 9,
- col : indique sur quelle colonne se trouve cur : cur % 9,
- sline : indique la première ligne du carré interne dans lequel se trouve cur : (line / 3) * 3,
- scol : indique la première colonne du carré interne dans lequel se trouve cur : (col / 3) % 3,
- icol : indice de la case à la iième ligne de la colonne de cur : line * 9 + i,
- iline : indice de la case à la iième colonne de la ligne de cur : i * 9 + col,
- isquare : indice de la iième case du carré interne de cur : 9 * (sline + (i / 3)) + scol + (i % 3).
