SOLO-019 · Futoshiki
EXTRÊMELes huit passages
Compléter le carré 8 × 8 avec les chiffres de 1 à 8.
Corrigé — cette page contient la réponse.
La réponse exacte
Grille, ligne par ligne :
1 5 6 8 2 7 4 3
8 6 2 3 4 5 1 7
6 8 3 2 7 1 5 4
4 7 5 1 6 3 2 8
3 2 4 7 1 6 8 5
2 3 7 4 5 8 6 1
7 4 1 5 8 2 3 6
5 1 8 6 3 4 7 2
| L / C | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 5 | 6 | 8 | 2 | 7 | 4 | 3 |
| 2 | 8 | 6 | 2 | 3 | 4 | 5 | 1 | 7 |
| 3 | 6 | 8 | 3 | 2 | 7 | 1 | 5 | 4 |
| 4 | 4 | 7 | 5 | 1 | 6 | 3 | 2 | 8 |
| 5 | 3 | 2 | 4 | 7 | 1 | 6 | 8 | 5 |
| 6 | 2 | 3 | 7 | 4 | 5 | 8 | 6 | 1 |
| 7 | 7 | 4 | 1 | 5 | 8 | 2 | 3 | 6 |
| 8 | 5 | 1 | 8 | 6 | 3 | 4 | 7 | 2 |
Le raisonnement
- Inscris d’abord les candidats de 1 à 8 dans chaque case vide. Retire tout chiffre déjà fixé dans sa ligne ou sa colonne. Les lignes et colonnes imposent chacune une permutation complète.
- Propage les inégalités dans les deux sens. Si A < B, A ne peut plus prendre une valeur supérieure ou égale au plus grand candidat de B, et B ne peut plus prendre une valeur inférieure ou égale au plus petit candidat de A.
- Après chaque réduction, vérifie les emplacements uniques de chaque chiffre dans chaque ligne et colonne. Une chaîne croissante de k cases consomme au moins k valeurs distinctes ; ses extrémités donnent aussi des bornes.
- La méthode de référence combine ces réductions puis des hypothèses contrôlées. Sur ce problème, la recherche exacte visite 43 nœuds, rencontre 21 contradictions et atteint une profondeur de 9 choix imbriqués. Ces nombres décrivent ce solveur et non une durée humaine garantie.
- Une hypothèse se traite comme une branche temporaire : note sa case et son chiffre, propage toutes les contraintes, puis reviens au dernier choix si une case perd tous ses candidats ou si une ligne ne peut plus contenir un chiffre. Ne gomme pas une hypothèse sans noter la contradiction.
- Voici les premières affectations du chemin qui aboutit à la solution. « Hypothèse » signifie un choix à confirmer dans l’exploration, et non une déduction locale déjà prouvée :
- L5C4 = 7 — inégalité.
- L5C1 = 3 — inégalité.
- L6C1 = 2 — inégalité.
- L6C4 = 4 — ligne/colonne.
- L1C4 = 8 — ligne/colonne.
- L1C3 = 6 — ligne/colonne.
- L4C8 = 8 — seul emplacement.
- L1C1 = 1 — hypothèse.
- L1C7 = 4 — hypothèse.
- L1C8 = 3 — ligne/colonne.
- L3C2 = 8 — hypothèse.
- L8C3 = 8 — seul emplacement.
- L2C1 = 8 — seul emplacement.
- L2C2 = 6 — hypothèse.
- L4C2 = 7 — ligne/colonne.
- L6C2 = 3 — ligne/colonne.
- L7C2 = 4 — ligne/colonne.
- L7C1 = 7 — ligne/colonne.
- L7C8 = 6 — ligne/colonne.
- L8C7 = 7 — seul emplacement.
- L2C7 = 1 — hypothèse.
- L7C7 = 3 — ligne/colonne.
- L7C3 = 1 — ligne/colonne.
- L2C6 = 5 — hypothèse.
- L2C5 = 4 — hypothèse.
- L2C8 = 7 — ligne/colonne.
- L3C4 = 2 — hypothèse.
- L3C7 = 5 — ligne/colonne.
- L3C6 = 1 — seul emplacement.
- L3C3 = 3 — seul emplacement.
- Exemple de branche réfutée : suppose L1C1 = 1, puis L1C7 = 3, puis L3C2 = 7. La propagation aboutit à : La case L3C4 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne. Le certificat d’exploration donne toutes les branches, avec indices de cases comptés à partir de zéro.
- Exemple de branche réfutée : suppose L1C1 = 1, puis L1C7 = 3, puis L3C2 = 8, puis L2C2 = 6, puis L2C8 = 5. La propagation aboutit à : La case L3C5 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne. Le certificat d’exploration donne toutes les branches, avec indices de cases comptés à partir de zéro.
- Exemple de branche réfutée : suppose L1C1 = 1, puis L1C7 = 3, puis L3C2 = 8, puis L2C2 = 6, puis L2C8 = 7, puis L3C4 = 1. La propagation aboutit à : Le chiffre 2 ne peut plus se placer dans le groupe L1C7, L2C7, L3C7, L4C7, L5C7, L6C7, L7C7, L8C7 Le certificat d’exploration donne toutes les branches, avec indices de cases comptés à partir de zéro.
- La grille finale permet le contrôle ligne par ligne et colonne par colonne : chacune contient une fois tous les chiffres. Vérifie ensuite les inégalités une par une :
- L4C1 < L4C2 : 4 < 7.
- L5C6 < L5C7 : 6 < 8.
- L8C2 < L7C2 : 1 < 4.
- L1C5 < L1C4 : 2 < 8.
- L6C2 < L6C3 : 3 < 7.
- L1C2 < L2C2 : 5 < 6.
- L5C1 < L4C1 : 3 < 4.
- L4C5 < L3C5 : 6 < 7.
- L2C3 < L2C2 : 2 < 6.
- L4C3 < L4C2 : 5 < 7.
- L6C1 < L6C2 : 2 < 3.
- L3C6 < L3C7 : 1 < 5.
- L7C3 < L6C3 : 1 < 7.
- L6C4 < L5C4 : 4 < 7.
- L8C8 < L8C7 : 2 < 7.
- L5C2 < L4C2 : 2 < 7.
- L4C2 < L3C2 : 7 < 8.
- L1C2 < L1C3 : 5 < 6.
- L6C1 < L5C1 : 2 < 3.
- Le comptage exact a continué après avoir trouvé cette grille pour chercher une seconde solution. Toutes les autres branches échouent : la solution est unique.
Fausses pistes et erreurs
- Ajouter les régions du Sudoku : elles ne font pas partie du Futoshiki.
- Oublier qu’une inégalité contraint ses deux extrémités.
- Prendre une hypothèse de recherche pour un chiffre déduit sans condition.
Déplier le certificat détaillé de recherche
Chaque branche est indépendante. L’arbre montre les déductions et contradictions du protocole utilisé ; ce n’est pas l’unique méthode possible.
{
"indexing": "Case i = ligne i//n+1, colonne i%n+1. Les indices bruts commencent à zéro.",
"events": [
{
"event": "branch",
"assumptions": [],
"cell": 0,
"values": [
1,
4
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
}
],
"cell": 6,
"values": [
3,
4
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
}
],
"cell": 17,
"values": [
7,
8
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 7
}
],
"reason": "La case L3C4 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
}
],
"cell": 9,
"values": [
6,
7
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
}
],
"cell": 15,
"values": [
5,
7
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 5
}
],
"reason": "La case L3C5 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 7
}
],
"cell": 19,
"values": [
1,
2
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 7
},
{
"cell": 19,
"value": 1
}
],
"reason": "Le chiffre 2 ne peut plus se placer dans le groupe L1C7, L2C7, L3C7, L4C7, L5C7, L6C7, L7C7, L8C7"
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 7
},
{
"cell": 19,
"value": 2
}
],
"cell": 20,
"values": [
5,
7
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 7
},
{
"cell": 19,
"value": 2
},
{
"cell": 20,
"value": 5
}
],
"reason": "La case L7C7 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 7
},
{
"cell": 19,
"value": 2
},
{
"cell": 20,
"value": 7
}
],
"cell": 22,
"values": [
4,
5
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 7
},
{
"cell": 19,
"value": 2
},
{
"cell": 20,
"value": 7
},
{
"cell": 22,
"value": 4
}
],
"cell": 14,
"values": [
1,
5
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 7
},
{
"cell": 19,
"value": 2
},
{
"cell": 20,
"value": 7
},
{
"cell": 22,
"value": 4
},
{
"cell": 14,
"value": 1
}
],
"reason": "Le chiffre 3 ne peut plus se placer dans le groupe L1C6, L2C6, L3C6, L4C6, L5C6, L6C6, L7C6, L8C6"
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 7
},
{
"cell": 19,
"value": 2
},
{
"cell": 20,
"value": 7
},
{
"cell": 22,
"value": 4
},
{
"cell": 14,
"value": 5
}
],
"reason": "La case L3C6 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 15,
"value": 7
},
{
"cell": 19,
"value": 2
},
{
"cell": 20,
"value": 7
},
{
"cell": 22,
"value": 5
}
],
"reason": "Deux chiffres fixés identiques dans les cases L1C1, L2C1, L3C1, L4C1, L5C1, L6C1, L7C1, L8C1"
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 3
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 7
}
],
"reason": "La case L3C4 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
}
],
"cell": 17,
"values": [
7,
8
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 7
}
],
"reason": "La case L3C4 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
}
],
"cell": 9,
"values": [
6,
7
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
}
],
"cell": 14,
"values": [
1,
5
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
}
],
"cell": 13,
"values": [
4,
5
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 4
}
],
"cell": 12,
"values": [
5,
7
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 4
},
{
"cell": 12,
"value": 5
}
],
"cell": 19,
"values": [
1,
2
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 4
},
{
"cell": 12,
"value": 5
},
{
"cell": 19,
"value": 1
}
],
"reason": "Le chiffre 2 ne peut plus se placer dans le groupe L1C7, L2C7, L3C7, L4C7, L5C7, L6C7, L7C7, L8C7"
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 4
},
{
"cell": 12,
"value": 5
},
{
"cell": 19,
"value": 2
}
],
"reason": "La case L4C1 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 4
},
{
"cell": 12,
"value": 7
}
],
"reason": "La case L3C3 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 5
}
],
"cell": 12,
"values": [
4,
7
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 5
},
{
"cell": 12,
"value": 4
}
],
"cell": 19,
"values": [
1,
2
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 5
},
{
"cell": 12,
"value": 4
},
{
"cell": 19,
"value": 1
}
],
"reason": "Le chiffre 2 ne peut plus se placer dans le groupe L1C7, L2C7, L3C7, L4C7, L5C7, L6C7, L7C7, L8C7"
},
{
"event": "solution",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 5
},
{
"cell": 12,
"value": 4
},
{
"cell": 19,
"value": 2
}
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 5
},
{
"cell": 12,
"value": 7
}
],
"cell": 18,
"values": [
3,
5
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 5
},
{
"cell": 12,
"value": 7
},
{
"cell": 18,
"value": 3
}
],
"reason": "La case L3C4 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 1
},
{
"cell": 13,
"value": 5
},
{
"cell": 12,
"value": 7
},
{
"cell": 18,
"value": 5
}
],
"reason": "L’inégalité L3C6 < L3C7 ne possède plus de couple de valeurs compatible."
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 14,
"value": 5
}
],
"reason": "L’inégalité L4C5 < L3C5 ne possède plus de couple de valeurs compatible."
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 1
},
{
"cell": 6,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 7
}
],
"reason": "La case L3C4 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 4
}
],
"cell": 17,
"values": [
7,
8
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 4
},
{
"cell": 17,
"value": 7
}
],
"reason": "La case L3C4 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 4
},
{
"cell": 17,
"value": 8
}
],
"cell": 9,
"values": [
6,
7
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 0,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
}
],
"cell": 19,
"values": [
1,
2
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 19,
"value": 1
}
],
"reason": "Le chiffre 2 ne peut plus se placer dans le groupe L1C7, L2C7, L3C7, L4C7, L5C7, L6C7, L7C7, L8C7"
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 6
},
{
"cell": 19,
"value": 2
}
],
"reason": "Le chiffre 1 ne peut plus se placer dans le groupe L3C1, L3C2, L3C3, L3C4, L3C5, L3C6, L3C7, L3C8"
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 0,
"value": 4
},
{
"cell": 17,
"value": 8
},
{
"cell": 9,
"value": 7
}
],
"reason": "La case L3C4 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
}
]
}Comment cette réponse a été vérifiée
Recherche exhaustive avec domaines, contraintes tout-différent, emplacements uniques et inégalités ; contrôle indépendant de la grille finale.
{
"nodes": 43,
"branches": 21,
"contradictions": 21,
"max_depth": 9,
"forced": 285,
"solutions": 1,
"size": 8,
"givens": 15,
"inequalities": 19
}Le croisement d’unicité des lignes, d’unicité des colonnes et d’inégalités ne se ferme pas par propagation des seuls chiffres forcés dans le solveur de référence. Des hypothèses imbriquées et des contradictions non locales sont nécessaires dans sa méthode ; cela motive le niveau Extrême, sans prétendre exclure une astuce humaine plus courte.