TAOCP 7.2.2.1 Exercise 388
The statement of the problem depends on the concrete futoshiki grids given in Figure 388, including the initial filled entries and the inequality relations between adjacent cells.
Section 7.2.2.1: Dancing Links
Exercise 388. ▶ [21] The goal of a futoshiki puzzle is to deduce the entries of a secret latin square, given only two kinds of hints: A "strong clue" is an explicit entry; a "weak clue" is a greater-than relation between neighboring entries. The entries are the numbers 1 to $n$, where $n$ is usually 5 as in the following examples:
Solve these puzzles by hand, using sudoku-like principles.
Verified: no
Solve time: 1m01s
Solution
The statement of the problem depends on the concrete futoshiki grids given in Figure 388, including the initial filled entries and the inequality relations between adjacent cells.
A futoshiki instance is a constrained Latin square on ${1,\dots,n}$ where each solution is determined by the simultaneous satisfaction of row and column permutation constraints together with all given inequality constraints. The exact cover formulation depends explicitly on which cells contain fixed values and which pairs of cells are constrained by $<$ or $>$ relations.
Since the contents of Figure 388 are not present in the provided material, the sets of givens and inequalities defining instances (a), (b), and (c) are undefined. Without those constraints, the corresponding Latin square completions are not uniquely determined and cannot be derived.
The solution therefore requires the explicit grids from Figure 388 in order to construct the admissible permutations and propagate constraints.
This completes the analysis. ∎