assistant-sudoku.com

Une logique du Sudoku

Le sudoku n'est pas à proprement parlé un problème de mathématique des nombres mais un problème de logique, puisque aussi bien les nombres pourraient être remplacés par des lettres ou des symboles.
En matière de logique pour démontrer une propriété on utilise le raisonnement par l'absurde (contradiction, non-sens ou impossibilité), à savoir que l'on part d'une hypothèse et on prouve que sous cette hypothèse on aboutit à une contradiction (non-sens ou impossibilité) ce qui prouve ainsi que l'hypothèse est fausse
La plupart des propriétés utilisées en Sudoku, de la plus évidente à la plus compliquée, celles énoncées dans la technique des pistes notamment, se démontrent avec ce raisonnement.

Paire de candidats et ensemble fermé

Voici deux exemples de raisonnement par l'absurde

Un premier exemple banal est celui d'un candidat ne figurant que deux fois (paire) dans un bloc sur une même ligne (ou sur une même colonne), ce qui permet de supprimer tous les autres candidats de la ligne (ou de la colonne).
Par exemple dans l'extrait ci-contre, le 4 de la case L5C6 peut être supprimé.

Démonstration :
Si le 4 de L5C6 était solution de la grille (hypothèse à contredire), les autres 4 de la ligne seraient éliminés, le bloc 4 ne contiendrait aucun 4 ce qui est impossible. Le 4 de L5C6 ne peut donc être solution et peut être éliminé.

Un second cas très classique est celui d'un ensemble (dit fermé) de N candidats ne figurant seulement que dans N cases d'une même zone sudoku (ligne, colonne ou bloc), ce qui permet d'affirmer que ces candidats peuvent être supprimés des autres cases de la zone.
Par exemple dans l'extrait ci-dessus, les candidats 2, 4, 7 et 9 des cases L4C3 et L5C123 constituent une ensemble fermé du bloc 3. Ces candidats peuvent être supprimés des cases L4C1 et L6C2 dans lesquelles ne subsistent donc plus que le 5 et le 8.

Démonstration :
Si le 7 de la case L4C1 était solution (hypothèse à contredire), on en déduirait que le 9 est solution de la case L4C3, puis que le 2 est solution de la case L5C2 et le 4 est solution de la case L5C1, et finalement que la case L5C3 ne contient aucun candidat solution, ce qui évidemment est impossible ! Donc le 7 de la case L4C1 ne peut pas être solution et peut être éliminé. On procède de la même manière pour les autres candidats.

Configuration interdite

Certaines configurations (dispositions) de candidats sont interdites (impossibles, anormales) pour les grilles de sudoku qui en principe n'ont qu'une solution possible (unicité). Si elles apparraissent au cours de la résolution, c'est, soit que la grille n'a pas une solution unique, soit qu'une erreur s'est glissée lors de la résolution.
La plus connue est le rectangle interdit formé par 4 cases disposées en rectangle, dont deux sont dans le même bloc, et dans lesquelles figurent les 2 mêmes candidats (figure ci-contre).
Démonstration :
Si cette disposition était possible dans une grille admettant une solution et une seule(hypothèse), la solution serait telle que le 3 et le 7 ne figureraient pas dans les lignes L1, L3 et dans les colonnes C1, C4 en dehors des 4 cases du rectangle. Ce qui veut dire, puisque la paire 3/7 constitue un doublet dans le bloc 1, que les autres cases de la grille autres que celles du rectangle ne sont pas modifiées selon qu'on choisi le 3 ou le 7 de la case L1C1.
Dès lors, ou bien toutes les autres cases de la grille peuvent être remplies d'un candidat unique conformément aux règles du sudoku et alors la grille a deux solutions (une pour le 3, une pour le 7), ou bien toutes les autres cases de la grille ne peuvent pas être remplies d'un candidat unique conformément aux règles du sudoku et la grille n'a pas de solution. Dans ces deux cas la conclusion est en contradiction avec l'hypothèse qu'il existe une solution et une seule, c'est donc que la configuration en rectangle de la même paire est impossible.

Il existe d'autres configurations interdites formées d'une chaîne de cases alignées deux par deux en colonne ou en ligne, dont deux sont dans le même bloc, et ayant toutes le même couple de candidats, comme celle de la figure ci-contre. Le principe de la démonstration est le même que précédemment.

Ces configurations ne devant pas apparaître dans une grille réputée n'avoir qu'une solution, cela permet parfois la détermination de candidats solutions sans lesquels ces configurations apparaîtraient. Voir cet exemple

Attention, la condition que deux cases sont dans le même bloc (c'est à dire forment un doublet) est impérative dans la démonstration. Si cette condition n'est pas réalisée (par exemple un rectangle dont les cases sont dans 4 blocs différents) on ne peut pas conclure à un problème d'unicité. Voir ce contre-exemple.

Justifications de la technique des pistes

Les propriétés énoncées dans la technique des pistes se démontrent aussi par l'absurde (contradiction, impossibilité) comme suit.

Rappelons que dans la technique des pistes on utilise les définitions suivantes :
- Une piste est, par définition, un ensemble de candidats liés à un candidat de départ par le fait que si le candidat de départ est solution de la grille, les autres candidats de la piste le sont aussi forcément.
- Une paire de candidats est formée, soit par deux 2 candidats différents occupants seuls une même case, soit par un candidat ne figurant que 2 fois dans une zone sudoku (ligne, colonne ou bloc).

1- Candidat commun à deux pistes dans une même case

Si deux pistes issues d'une paire (voir définition ci-dessus) ont en commun un même candidat dans une case, ce candidat est solution de la case.

Démonstration :
Si un autre candidat de cette case était solution (hypothèse à contredire), cela voudrait dire qu'aucun des deux candidats de départ des deux pistes n'est solution, ce qui est impossible puisqu'ils font partie d'une paire dont un au moins est forcément solution par définition.

Dans l'exemple ci-contre, les deux pistes issues de la paire 8/9 de la case L2C2 conduisent sur le 2 de la case L3C9 qui est donc solution dans cette case.

2- Candidat commun à deux pistes dans deux cases différentes

Si deux pistes issues d'une paire (voir définition ci-dessus) ont en commun un candidat de même valeur mais dans deux cases différentes, tout autre candidat de même valeur qui voit les deux cases peut être éliminé.

Démonstration :
Si un candidat de même valeur qui voit les deux cases était solution (hypothèse à contredire), cela voudrait dire que les deux candidats des deux pistes se trouvant dans ces cases ne sont pas solutions, alors les candidats de départ des deux pistes ne seraient pas solutions aussi, ce qui est impossible puisqu'ils font partie d'une paire dont un au moins est forcément solution par définition.

Dans l'exemple ci-contre, le 6 de la case L3C5 peut être supprimé.

3- Candidats différents des deux pistes dans deux cases différentes d'une même zone sudoku

Si les deux pistes ont chacune un candidat différent dans deux cases différentes d'une même zone sudoku, chacun de ces candidats peut respectivement être éliminé de la case contenant l'autre candidat.

Démonstration :
Cela est une conséquence du cas précédent.

Dans l'exemple ci-contre, le 3 et le 9 de la case L2C2 peuvent être supprimés.

4- Candidats des deux pistes dans une même case

Si deux pistes ont chacune un candidat dans une même case, les autres candidats de la case peuvent être éliminés.

Démonstration :
Si un candidat autre que ceux des deux pistes est solution (hypothèse à contredire), cela voudrait dire que les deux candidats des deux pistes se trouvant dans cette case ne sont pas solutions, alors les candidats de départ des deux pistes ne seraient pas solutions aussi, ce qui est impossible puisqu'ils font partie d'une paire dont un au moins est forcément solution par définition.

Dans l'exemple ci-contre le 2 et le 6 de la case L1C5 peuvent être éliminés aisni que le 3 de la case L2C3.

5- Invalisation d'une piste

Si une piste a deux fois un candidat de même valeur dans une même zone sudoku, cette piste n'est pas bonne et ce sont les candidats de l'autre piste qui sont solutions. Plus généralement, toute contradiction constatée pour une piste valide l'autre piste comme solution.

Démonstration :
La contradiction est énoncée dans le contenu de la propriété, puisque le choix de cette piste conduit à dire que deux candidats solutions de même valeur subsisterait dans une même zone sudoku, ce qui est impossible par définition d'une grille sudoku.

Dans l'exemple ci-contre, la piste bleue est invalidée puisqu'elle contient deux 1 sur la même ligne, ce sont donc tous les candidats de la piste jaune qui sont solutions de la grille.