Sudoku

Programme des réjouissances

Vous connaissez sûrement ce jeu où le joueur doit compléter une grille 9x9 avec des chiffres de 1 à 9, de telle façon que le même chiffre ne soit pas répété dans une même ligne, une même colonne ou l'un des 9 carrés 3x3 qui divisent la grille.

Les programmes de résolution des grilles ne manquent pas, mais peu indiquent comment arriver à la solution qu'ils trouvent.

Le petit programme dont voici les sources en C vous permet de saisir une grille, d'en trouver la solution (ou les solutions), et surtout de connaître le moyen d'y arriver.

L'interface texte est volontairement très rudimentaire pour limiter les problèmes de portabilité.

Bien entendu, si vous entrez une grille vide dans le programme, il vous énumérera toutes les grilles possibles, ce qui devrait vous occuper quelques années.

Grosso modo, les méthodes de recherche utilisées sont les suivantes:

  • "Balayage": Si, dans une ligne, une seule case libre peut accueillir un 6, alors elle en contient nécéssairement un. Ce cas se voit facilement en balayant la grille du regard, à partir des 6 déjà placés.
  • "Coup unique": Si, dans une case, le seul chiffre autorisé est 5, alors il n'y a pas à hésiter! C'est malheureusement un peu moins facile à repérer que le balayage.
  • "Nettoyage": Si une ligne comporte cinq cases libres, et que sur trois d'entre elles les seules valeurs jouables sont 1,4 et 7, alors les deux autres cases libres ne contiennent ni 1, ni 4, ni 7. C'est sans doute la configuration la plus difficile à voir, à n'essayer qu'en désespoir de cause.
  • "Impasse": Si une case est libre alors qu'aucun chiffre ne peut être mis dedans, on n'a pas de solution et il faut revenir en arrière.

Les raisonnements du "balayage", du "coup unique" et du "nettoyage" viennent d'être expliqués pour une ligne. Ils s'appliquent naturellement de la même façon à une colonne ou à un carré 3x3.

Liens sur le suduku

  • Sudoku Explainer: ne passez plus de temps à résoudre vos grilles: ce programme explique si bien les solutions!
  • Le mathématicien Arto Inkala présente, sur AiSodoku.com, ses critères pour évaluer la difficulté d'une grille.
  • Sur Wikipedia les explications pour se ramener à un problème de couverture d'ensemble.

Retour sommaire

Dernière modification : 5 novembre 2016