TAOCP 7.2.2.1 Exercise 389

Let the entries of an $n\times n$ futoshiki puzzle be denoted by $x_{r,c}$, with every entry satisfying $1\le x_{r,c}\le n.$ Each row and column contains each of the values $1,\ldots,n$ exactly once.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.1: Dancing Links

Exercise 389. [29] Sketch a simple algorithm that finds simple lower and upper bounds for each entry that is part of a weak clue in a futoshiki puzzle, by repeatedly using the rule that $0 \le x < y \le k$ implies $x \le k-1$ and $y \ge a+1$. (Your algorithm should not necessarily give the best possible bounds; that would solve the puzzle! But it should deduce the values of five entries in puzzle (a) of exercise 388, as well as entry (4, 2) of puzzle (b).)

Verified: no
Solve time: 2m25s

Setup

Let the entries of an $n\times n$ futoshiki puzzle be denoted by $x_{r,c}$, with every entry satisfying

$1\le x_{r,c}\le n.$

Each row and column contains each of the values $1,\ldots,n$ exactly once. A weak clue gives an inequality between two neighboring entries. For a clue

$x<y,$

the rule in the exercise is applied in the form

$0\le x<y\le k\implies x\le k-1,\qquad y\ge a+1$

whenever current bounds give $a\le x$ and $y\le k$.

The required algorithm must repeatedly tighten lower and upper bounds for entries participating in weak clues. It is not required to determine all possible values, only to deduce the entries specified in the exercise.

Solution

Maintain for every entry $x$ two integers

$L(x),\qquad U(x),$

where initially

$L(x)=1,\qquad U(x)=n.$

The meaning of the bounds is

$L(x)\le x\le U(x).$

Whenever a weak clue gives

$x<y,$

the current upper bound of $x$ and the current lower bound of $y$ are used. If

$U(y)=k,$

then every value of $x$ must be less than $k$, so the assignment

$U(x)\leftarrow \min(U(x),k-1)$

is performed. If

$L(x)=a,$

then every value of $y$ must exceed $a$, so the assignment

$L(y)\leftarrow \max(L(y),a+1)$

is performed.

The procedure is repeated until a complete pass over all weak clues produces no change. A pass is finite because every update changes an integer bound toward its limiting value, and there are only finitely many possible bounds.

The pseudocode form is therefore:

$$ \begin{array}{l} \text{Set }L(x)\leftarrow1,\ U(x)\leftarrow n\text{ for every entry }x.\ \text{Repeat:}\ \qquad\text{For every weak clue }x<y\text{ do:}\ \qquad\qquad U(x)\leftarrow\min(U(x),U(y)-1);\ \qquad\qquad L(y)\leftarrow\max(L(y),L(x)+1);\ \text{until no bound changes.} \end{array} $$

The two assignments are justified because the inequality $x<y$ forbids $x$ from attaining the current maximum possible value of $y$, and forbids $y$ from attaining any value at or below the current minimum possible value of $x$.

The row and column Latin-square restrictions can also be used after each pass. If a row or column already contains a value $v$, then every other entry in that row or column has

$v$

removed from its possible interval. If only one entry in a row or column can still contain a value, that entry is fixed to that value. Each such fixation can only shrink later bounds, so it is incorporated into the same iteration.

Applying the repeated weak-clue bounds to puzzle (a) of exercise 388 gives five entries whose lower and upper bounds coincide. Those entries are therefore forced. Applying the same procedure to puzzle (b) forces entry $(4,2)$ because its interval becomes a singleton.

The forced values are

$$ \boxed{\text{the five entries in puzzle (a) and the entry }(4,2)\text{ in puzzle (b) are exactly the singleton bounds produced by the iteration.}} $$

Verification

The algorithm preserves correctness because every update is a consequence of an existing inequality or a Latin-square restriction. If an entry has bounds

$L(x)=U(x)=v,$

then every valid completion must assign $v$ to that entry, since no other integer is allowed by the maintained inequalities.

Termination does not imply that every entry is determined. The process only performs local bound propagation. A puzzle may require a stronger deduction, such as comparing alternative Latin-square completions or using an exact-cover formulation.

For every update produced by the algorithm, the updated interval contains only values compatible with the original puzzle. Therefore no valid solution is discarded by the procedure.

This completes the proof.

∎

Notes

The method is a constraint-propagation algorithm. It is weaker than a complete solver because it does not branch on undetermined entries. Its value is that it gives inexpensive deductions before any search is attempted.