SOLO-019 · Futoshiki
EXTREMEThe Eight Passages
Complete square 8 × 8 with figures from 1 to 8.
This page contains the solution.
The answer
Grid, line by line:
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 |
The reasoning
- First enter the candidates from 1 to 8 in each empty box. Remove any numbers already fixed in its line or column. The rows and columns each require a complete permutation.
- Owns inequalities in both directions. If A < B, A can no longer take a value greater than or equal to the greatest candidate of B, and B can no longer take a value less than or equal to the smallest candidate of A.
- After each reduction, check the unique locations of each digit in each row and column. A growing chain of k boxes consumes at least k separate values; its ends also give bounds.
- The reference method combines these reductions and then controlled assumptions. On this problem, the exact search visits 43 knots, encounters 21 contradictions and reaches a depth of 9 nested choices. These numbers describe this solver and not a guaranteed human duration.
- A hypothesis is treated as a temporary branch: notes its box and its number, spreads all the constraints, then returns to the last choice if a box loses all its candidates or if a line can no longer contain a number. Do not erase a hypothesis without noting the contradiction.
- Here are the first assignments of the path that leads to the solution. "Assumption" means a choice to be confirmed in exploration, not a proven local deduction:
- L5C4 = 7 — inequality.
- L5C1 = 3 — inequality.
- L6C1 = 2 — inequality.
- L6C4 = 4 — row/column.
- L1C4 = 8 — row/column.
- L1C3 = 6 — row/column.
- L4C8 = 8 — single location.
- L1C1 = 1 — hypothesis.
- L1C7 = 4 — hypothesis.
- L1C8 = 3 — row/column.
- L3C2 = 8 — hypothesis.
- L8C3 = 8 — single location.
- L2C1 = 8 — single location.
- L2C2 = 6 — hypothesis.
- L4C2 = 7 — row/column.
- L6C2 = 3 — row/column.
- L7C2 = 4 — row/column.
- L7C1 = 7 — row/column.
- L7C8 = 6 — row/column.
- L8C7 = 7 — single location.
- L2C7 = 1 — hypothesis.
- L7C7 = 3 — row/column.
- L7C3 = 1 — row/column.
- L2C6 = 5 — hypothesis.
- L2C5 = 4 — hypothesis.
- L2C8 = 7 — row/column.
- L3C4 = 2 — hypothesis.
- L3C7 = 5 — row/column.
- L3C6 = 1 — only location.
- L3C3 = 3 — single location.
- Example of a rebutted branch: supposes L1C1 = 1, then L1C7 = 3, then L3C2 = 7. The propagation results in: The box L3C4 no longer has any candidate after excluding the numbers set in its line/column. The exploration certificate gives all branches, with indices of boxes counted from zero.
- Example of a rebutted branch: supposes L1C1 = 1, then L1C7 = 3, then L3C2 = 8, then L2C2 = 6, then L2C8 = 5. The propagation results in: The box L3C5 no longer has any candidate after excluding the numbers set in its line/column. The certificate of exploration gives all branches, with indices of cells counted from scratch.
- Example of a rebutted branch: supposes L1C1 = 1, then L1C7 = 3, then L3C2 = 8, then L2C2 = 6, then L2C8 = 7, then L3C4 = 1. The propagation results in: The number 2 can no longer be placed in group L1C7, L2C7, L3C7, L4C7, L5C7, L6C7, L7C7, L8C7 The certificate of exploration gives all branches, with indices of cells counted from scratch.
- The final grid allows line-by-line and column-by-column control: each one contains once all the numbers. Then check the inequalities one by one:
- 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.
- The exact counting continued after finding this grid to look for a second solution. All other branches fail: the solution is unique.
Common mistakes and false leads
- Add the Sudoku regions: they are not part of Futoshiki.
- Forget that inequality forces its two ends.
- Take a search hypothesis for a figure deducted unconditionally.
Show the full search proof
Each branch is independent. The tree records the deductions and contradictions found with the method used here.
{
"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."
}
]
}How we verified this answer
Comprehensive research with different domains, constraints, unique locations and inequalities; independent control of the final grid.
{
"nodes": 43,
"branches": 21,
"contradictions": 21,
"max_depth": 9,
"forced": 285,
"solutions": 1,
"size": 8,
"givens": 15,
"inequalities": 19
}The crossover of single lines, single columns and inequities is not closed by propagation of the only forced numbers in the reference solver. Entwined hypotheses and non-local contradictions are necessary in its method; this motivates the Extreme level, without pretending to exclude a shorter human trick.