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….