Sur la résolution de Sudoku

Quelqu’un peut-il m’aider s’il vous plaît à comprendre cette solution :

Initialize 2D array with 81 empty grids (nx = 9, ny = 9) Fill in some empty grid with the known values Make an original copy of the array Start from top left grid (nx = 0, ny = 0), check if grid is empty if (grid is empty) { assign the empty grid with values (i) if (no numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in) fill in the number if (numbers exists in same rows & same columns same as (i) & 3x3 zone (i) is currently in) discard (i) and repick other values (i++) } else { while (nx < 9) { Proceed to next row grid(nx++, ny) if (nx equals 9) { reset nx = 1 proceed to next column grid(nx,ny++) if (ny equals 9) { print solution } } } } 

C’est un simple solveur de force brute. Cela commence en haut à gauche, en allant de gauche à droite, ligne par ligne, en essayant de placer chaque nombre possible dans chaque carré, puis en utilisant un appel récursif. En cas d’échec, il recule et essaie une alternative différente.

La fonction appelée safe détermine s’il est actuellement légal de placer la valeur n dans une cellule donnée en vérifiant quelles valeurs ont déjà été placées dans la ligne, la colonne et la zone.

C’est l’un des moyens les plus simples (et les plus lents) de résoudre un sudoku.

Il y a beaucoup de façons de résoudre le Sudoku (je ne sais pas si cela vous intéresse en général). Il s’agit fondamentalement d’un problème de satisfaction de contrainte, et vous pouvez appliquer vos techniques de vérification de la cohérence préférées (par exemple, AC3) pour propager des contraintes et supprimer des chemins évidemment infructueux beaucoup plus tôt. Vos variables sont chaque carré, le domaine que chaque variable peut prendre est les entiers 1 à 9. Les contraintes sont AllDiff sur divers sous-ensembles de cellules.

Vous pouvez également le formuler en tant que problème de programmation linéaire entier et laisser votre moteur ILP préféré (par exemple, lp_solve) le résoudre!

La chose la plus déroutante était que je m’attendais à ce que l’algorithme remplisse la masortingce de sudoku avec les valeurs correctes à la fin, mais au lieu de cela, il affiche simplement les valeurs puis revient au début car la valeur de la variable t est toujours écrite en retour parvient même à trouver une autre solution).

Pour que la grid soit remplie à la fin de l’algorithme, vous pouvez demander à la fonction de résolution de retourner vrai / faux, puis de décider si vous souhaitez effectuer un suivi en fonction du résultat des appels internes.