Résolution d’un Sudoku
Il y a sans doute
plusieurs manière pour résoudre un sudoku, mais elles reposent, à moins que
votre cerveau ne soit « cablé pour » sur trois algorithmes de base.
Ce sont ces trois algorithmes qui ont été utilisés dans le programme proposé.
Le premier
consiste à considérer que dans chaque « sous-carré », doivent figurer les 9 chiffres. Si, de par
la position des chiffres déjà présents dans le sous-carré, et dans les autres
colonnes et lignes il existe un chiffre pour lequel une seule position est
possible, alors c’est la position de la solution (si une solution existe bien
sur). On illustre ceci sur l’exemple ci-dessous :
On a représenté sur
ce carré qui contenait déjà des « 2 », les lignes et les colonnes
interdites pour un autre chiffre « 2 ». On constate que pour le
sous-carré du milieu de la bande basse, une seule case est laissée possible
pour un 2, celle du milieu. Comme il faut un « 2 » dans ce
sous-carré, il faut effectivement mettre « 2 » dans cette case.
Le deuxième
consiste à considérer que dans chaque colonne, il faut que l’on trouve tous les
chiffres de 1 à 9 ; comme dans le cas du sous-carré, si il y a un chiffre
pour lequel une seule case est possible, alors il doit y être placé. Voir
l’exemple ci-dessous. On cherche à mettre le chiffre 2 dans la première
colonne, seule une case est possible comme l’indique la construction de
droite :
La troisième
méthode est analogue, sauf que l’on considère les lignes au lieu des
colonnes :
Amusez-vous
bien maintenant….