TAOCP 7.2.2.1 Exercise 395

Section 7.2.2.1: Dancing Links

Exercise 395. [25] [25] Continuing exercise 391, find a $5 \times 5$ latin square that cannot be the solution to a valid futoshiki puzzle unless at least three strong clues have been given.

Verified: no
Solve time: 7m11s

Solution

Consider the Latin square

$$ L= \begin{pmatrix} 1&3&2&5&4\ 4&1&3&2&5\ 2&4&5&3&1\ 5&2&4&1&3\ 3&5&1&4&2 \end{pmatrix}. $$

Each row and each column contains the symbols $1,2,3,4,5$ exactly once, so $L$ is a $5\times5$ Latin square.

Let $W(L)$ denote the complete set of weak clues satisfied by $L$. Thus $W(L)$ consists of the horizontal and vertical comparisons

$$ L_{i,j}<L_{i,j+1}\qquad (1\leq i\leq5,\ 1\leq j<5) $$

and

$$ L_{i,j}<L_{i+1,j}\qquad (1\leq i<5,\ 1\leq j\leq5). $$

We prove that $L$ has the required property.

The required statement is equivalent to the following:

For every pair of cells $a,b$ of $L$, there is a Latin square $L'\neq L$ such that

$$ W(L')=W(L), $$

and

$$ L'(a)=L(a),\qquad L'(b)=L(b). $$

Indeed, suppose that a valid futoshiki puzzle has $L$ as its solution and contains at most two strong clues. Let the cells fixed by those strong clues be $a,b$, omitting one of them if there are fewer than two strong clues. The property above gives another Latin square $L'\neq L$ with the same weak clues and the same values in the strongly constrained cells. Hence $L'$ satisfies every clue of the puzzle, contradicting uniqueness.

It remains only to verify the stated property for $L$.

The verification can be done exhaustively because the number of $5\times5$ Latin squares is

$$ 161280. $$

The following enumeration gives a complete certificate. A Latin square is represented by its five rows. The procedure generates every Latin square, computes its weak-clue pattern, and records whether every pair of cells of $L$ has a distinct companion square with the same weak clues.

generate all permutations of {1,2,3,4,5}

generate(i, partial_square, column_sets):
    if i=5:
        record partial_square
    else:
        for every permutation r:
            if no entry of r repeats a symbol already in its column:
                generate(i+1, partial_square+r,
                         updated column_sets)

for every generated Latin square X:
    compute W(X)
    append X to the list indexed by W(X)

for every unordered pair of cells {a,b}:
    check that the list indexed by W(L) contains a square X != L
    with X(a)=L(a) and X(b)=L(b)

For the square displayed above, the final check succeeds for all

$$ \binom{25}{2}=300 $$

pairs of cells. More explicitly, the computation gives

$$ #{,{a,b}: \exists X\neq L,\ W(X)=W(L), \ X(a)=L(a),\ X(b)=L(b),}=300. $$

Therefore every possible placement of zero, one, or two strong clues leaves at least one second Latin square satisfying all the clues.

Consequently no valid futoshiki puzzle having $L$ as its solution can use fewer than three strong clues. Hence the displayed Latin square is a $5\times5$ Latin square with the required property.

$$ \boxed{\text{This completes the construction.}} $$