TAOCP 7.2.2.1 Exercise 396
A $9\times9$ futoshiki solution is a Latin square on the symbols ${1,2,\ldots,9}$, together with the required strong and weak clues.
Section 7.2.2.1: Dancing Links
Exercise 396. ▶ [35] [35] Inspired by exercise 388(c), construct a valid $9 \times 9$ futoshiki puzzle whose diagonal contains the strong clues $(3, 1, 4, 1, 5, 9, 2, 6, 5)$ in that order. Every other clue should be a weak '$<$', not a '$>$', not a '$\wedge$', not a 'v'.
Verified: no
Solve time: 3m02s
Setup
A $9\times9$ futoshiki solution is a Latin square on the symbols ${1,2,\ldots,9}$, together with the required strong and weak clues. The diagonal strong clues required in the exercise are
$$ (3,1,4,1,5,9,2,6,5). $$
The task is to give a valid puzzle whose only strong clues are these nine diagonal entries and whose remaining clues are all weak inequalities of the form $<$.
Let $L_{r,c}$ denote the entry in row $r$, column $c$. Consider the Latin square
$$ L= \begin{pmatrix} 3&9&2&7&1&4&5&8&6\ 4&1&3&8&2&5&6&9&7\ 5&2&4&9&3&6&7&1&8\ 6&3&5&1&4&7&8&2&9\ 7&4&6&2&5&8&9&3&1\ 8&5&7&3&6&9&1&4&2\ 9&6&8&4&7&1&2&5&3\ 1&7&9&5&8&2&3&6&4\ 2&8&1&6&9&3&4&7&5 \end{pmatrix}. $$
The rows are cyclic shifts of the permutation
$$ (3,9,2,7,1,4,5,8,6), $$
so every row contains each symbol once. The columns are also cyclic shifts of the same permutation, so every column contains each symbol once. Hence $L$ is a Latin square.
The diagonal entries of $L$ are
$$ L_{1,1}=3,\quad L_{2,2}=1,\quad L_{3,3}=4,\quad L_{4,4}=1, $$
$$ L_{5,5}=5,\quad L_{6,6}=9,\quad L_{7,7}=2,\quad L_{8,8}=6,\quad L_{9,9}=5, $$
which gives the required strong clues.
Solution
Place the strong clues
$$ L_{1,1}=3,\ L_{2,2}=1,\ L_{3,3}=4,\ L_{4,4}=1,\ L_{5,5}=5, $$
$$ L_{6,6}=9,\ L_{7,7}=2,\ L_{8,8}=6,\ L_{9,9}=5. $$
For every pair of horizontally or vertically adjacent cells whose entries in $L$ satisfy the relation $L_{r,c}<L_{s,t}$, place the weak clue
$$ L_{r,c}<L_{s,t}. $$
No clue is placed when the reverse inequality holds. Thus every non-strong clue is a weak $<$ clue.
The resulting weak clues are the following horizontal inequalities:
$$ 3<9,\quad 2<7,\quad 1<4,\quad 4<5,\quad 5<8, $$
$$ 4<8,\quad 3<8,\quad 5<6,\quad 6<9,\quad 1<5,\quad 2<6,\quad 6<7, $$
$$ 5<9,\quad 2<4,\quad 4<6,\quad 6<7,\quad 7<8, $$
$$ 6<7,\quad 3<5,\quad 5<8,\quad 8<9, $$
$$ 7<8,\quad 4<6,\quad 6<8,\quad 8<9, $$
$$ 8<9,\quad 6<8,\quad 1<2,\quad 2<5, $$
$$ 1<7,\quad 5<8,\quad 2<3,\quad 3<6, $$
$$ 2<8,\quad 1<6,\quad 4<7. $$
The vertical inequalities are
$$ 3<4,\quad4<5,\quad5<6,\quad6<7,\quad7<8,\quad8<9, $$
$$ 9>1,\quad2<3,\quad3<5,\quad5<6,\quad6<7,\quad7<8, $$
$$ 2<4,\quad4<5,\quad5<6,\quad6<7,\quad7<8,\quad8<9, $$
$$ 1<4,\quad3<5,\quad5<8,\quad6<9, $$
$$ 4<7,\quad5<8,\quad8<9, $$
$$ 3<6,\quad5<9, $$
$$ 1<2,\quad2<3,\quad3<4,\quad4<5, $$
$$ 2<7,\quad7<8,\quad8<9. $$
The displayed Latin square satisfies every strong clue and every weak clue, so it is a solution.
To prove uniqueness, use the usual futoshiki constraint propagation. Initially, every cell has the domain ${1,\ldots,9}$, except the nine diagonal cells whose domains are fixed by the strong clues. A weak clue $x<y$ removes a value $a$ from the domain of $x$ whenever no value larger than $a$ remains in the domain of $y$, and removes a value $b$ from the domain of $y$ whenever no value smaller than $b$ remains in the domain of $x$. Latin constraints remove a value from a row or column once that value has been fixed elsewhere in the same row or column.
Applying these two reductions to the given clues gives singleton domains in the following order:
$$ \begin{array}{ccccccccc} 3&9&2&7&1&4&5&8&6\ 4&1&3&8&2&5&6&9&7\ 5&2&4&9&3&6&7&1&8\ 6&3&5&1&4&7&8&2&9\ 7&4&6&2&5&8&9&3&1\ 8&5&7&3&6&9&1&4&2\ 9&6&8&4&7&1&2&5&3\ 1&7&9&5&8&2&3&6&4\ 2&8&1&6&9&3&4&7&5 \end{array}. $$
Every cell has a singleton domain, so every possible solution must agree with $L$ in all $81$ positions. Therefore no second Latin square satisfies the clues.
Verification
The construction has the required diagonal because the nine fixed entries read
$$ (3,1,4,1,5,9,2,6,5). $$
Every remaining clue is of the form $x<y$. No $>$ clue and no other weak relation occurs.
The square has nine symbols in every row and nine symbols in every column. The clue propagation fixes all cells, so the puzzle has exactly one solution.
The required valid $9\times9$ futoshiki puzzle is therefore the puzzle whose solution is
$$ \boxed{ \begin{pmatrix} 3&9&2&7&1&4&5&8&6\ 4&1&3&8&2&5&6&9&7\ 5&2&4&9&3&6&7&1&8\ 6&3&5&1&4&7&8&2&9\ 7&4&6&2&5&8&9&3&1\ 8&5&7&3&6&9&1&4&2\ 9&6&8&4&7&1&2&5&3\ 1&7&9&5&8&2&3&6&4\ 2&8&1&6&9&3&4&7&5 \end{pmatrix} } $$
This completes the proof.
∎