SOLO-018 · Futoshiki
EXPERTLes sept escaliers
Compléter le carré 7 × 7 avec les chiffres de 1 à 7.
Corrigé — cette page contient la réponse.
La réponse exacte
Grille, ligne par ligne :
3 6 4 2 7 5 1
6 2 1 7 4 3 5
7 4 3 1 5 2 6
5 3 7 6 2 1 4
4 1 6 5 3 7 2
1 5 2 3 6 4 7
2 7 5 4 1 6 3
| L / C | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 1 | 3 | 6 | 4 | 2 | 7 | 5 | 1 |
| 2 | 6 | 2 | 1 | 7 | 4 | 3 | 5 |
| 3 | 7 | 4 | 3 | 1 | 5 | 2 | 6 |
| 4 | 5 | 3 | 7 | 6 | 2 | 1 | 4 |
| 5 | 4 | 1 | 6 | 5 | 3 | 7 | 2 |
| 6 | 1 | 5 | 2 | 3 | 6 | 4 | 7 |
| 7 | 2 | 7 | 5 | 4 | 1 | 6 | 3 |
Le raisonnement
- Inscris d’abord les candidats de 1 à 7 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 13 nœuds, rencontre 6 contradictions et atteint une profondeur de 3 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 :
- L3C6 = 2 — seul emplacement.
- L7C5 = 1 — seul emplacement.
- L3C4 = 1 — seul emplacement.
- L2C6 = 3 — hypothèse.
- L2C7 = 5 — inégalité.
- L3C7 = 6 — inégalité.
- L2C4 = 7 — ligne/colonne.
- L7C4 = 4 — ligne/colonne.
- L6C4 = 3 — inégalité.
- L5C4 = 5 — seul emplacement.
- L1C7 = 1 — hypothèse.
- L2C2 = 2 — hypothèse.
- L2C3 = 1 — ligne/colonne.
- L7C2 = 7 — ligne/colonne.
- L4C6 = 1 — seul emplacement.
- L4C3 = 7 — seul emplacement.
- L7C1 = 2 — ligne/colonne.
- L3C2 = 4 — ligne/colonne.
- L6C6 = 4 — ligne/colonne.
- L5C6 = 7 — seul emplacement.
- L6C1 = 1 — inégalité.
- L6C5 = 6 — inégalité.
- L4C2 = 3 — inégalité.
- L3C1 = 7 — ligne/colonne.
- L4C5 = 2 — ligne/colonne.
- L4C1 = 5 — seul emplacement.
- L6C2 = 5 — ligne/colonne.
- L6C3 = 2 — ligne/colonne.
- L1C2 = 6 — ligne/colonne.
- L5C2 = 1 — ligne/colonne.
- Exemple de branche réfutée : suppose L2C6 = 1, puis L1C5 = 3. La propagation aboutit à : Le chiffre 5 ne peut plus se placer dans le groupe L6C1, L6C2, L6C3, L6C4, L6C5, L6C6, L6C7 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 L2C6 = 1, puis L1C5 = 7, puis L2C3 = 2. La propagation aboutit à : Deux chiffres fixés identiques dans les cases L6C1, L6C2, L6C3, L6C4, L6C5, L6C6, L6C7 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 L2C6 = 1, puis L1C5 = 7, puis L2C3 = 7. La propagation aboutit à : L’inégalité L6C4 < L7C4 ne possède plus de couple de valeurs compatible. 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 :
- L5C1 < L4C1 : 4 < 5.
- L6C6 < L5C6 : 4 < 7.
- L3C6 < L3C7 : 2 < 6.
- L2C6 < L2C7 : 3 < 5.
- L6C2 < L7C2 : 5 < 7.
- L4C1 < L3C1 : 5 < 7.
- L7C7 < L7C6 : 3 < 6.
- L5C7 < L6C7 : 2 < 7.
- L5C2 < L4C2 : 1 < 3.
- L1C4 < L1C5 : 2 < 7.
- L1C4 < L2C4 : 2 < 7.
- L6C1 < L7C1 : 1 < 2.
- L6C4 < L7C4 : 3 < 4.
- L6C6 < L6C5 : 4 < 6.
- L4C2 < L3C2 : 3 < 4.
- L4C5 < L3C5 : 2 < 5.
- L2C7 < L3C7 : 5 < 6.
- 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": 12,
"values": [
1,
3
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 12,
"value": 1
}
],
"cell": 4,
"values": [
3,
7
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 12,
"value": 1
},
{
"cell": 4,
"value": 3
}
],
"reason": "Le chiffre 5 ne peut plus se placer dans le groupe L6C1, L6C2, L6C3, L6C4, L6C5, L6C6, L6C7"
},
{
"event": "branch",
"assumptions": [
{
"cell": 12,
"value": 1
},
{
"cell": 4,
"value": 7
}
],
"cell": 9,
"values": [
2,
7
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 12,
"value": 1
},
{
"cell": 4,
"value": 7
},
{
"cell": 9,
"value": 2
}
],
"reason": "Deux chiffres fixés identiques dans les cases L6C1, L6C2, L6C3, L6C4, L6C5, L6C6, L6C7"
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 12,
"value": 1
},
{
"cell": 4,
"value": 7
},
{
"cell": 9,
"value": 7
}
],
"reason": "L’inégalité L6C4 < L7C4 ne possède plus de couple de valeurs compatible."
},
{
"event": "branch",
"assumptions": [
{
"cell": 12,
"value": 3
}
],
"cell": 6,
"values": [
1,
4
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 12,
"value": 3
},
{
"cell": 6,
"value": 1
}
],
"cell": 8,
"values": [
1,
2
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 12,
"value": 3
},
{
"cell": 6,
"value": 1
},
{
"cell": 8,
"value": 1
}
],
"reason": "La case L6C3 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "solution",
"assumptions": [
{
"cell": 12,
"value": 3
},
{
"cell": 6,
"value": 1
},
{
"cell": 8,
"value": 2
}
]
},
{
"event": "branch",
"assumptions": [
{
"cell": 12,
"value": 3
},
{
"cell": 6,
"value": 4
}
],
"cell": 8,
"values": [
1,
2
]
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 12,
"value": 3
},
{
"cell": 6,
"value": 4
},
{
"cell": 8,
"value": 1
}
],
"reason": "La case L4C7 ne possède plus aucun candidat après exclusion des chiffres fixés dans sa ligne/colonne."
},
{
"event": "contradiction",
"assumptions": [
{
"cell": 12,
"value": 3
},
{
"cell": 6,
"value": 4
},
{
"cell": 8,
"value": 2
}
],
"reason": "Le chiffre 1 ne peut plus se placer dans le groupe L1C1, L1C2, L1C3, L1C4, L1C5, L1C6, L1C7"
}
]
}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": 13,
"branches": 6,
"contradictions": 6,
"max_depth": 3,
"forced": 136,
"solutions": 1,
"size": 7,
"givens": 11,
"inequalities": 17
}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. Le niveau Expert repose sur la combinaison des bornes et des emplacements uniques, suivie d’une exploration contrôlée ; il ne découle pas seulement de la taille du carré.