TAOCP 7.2.2.1 Exercise 389

Let the futoshiki puzzle consist of an $n\times n$ grid of variables $x_{i,j}$, each intended to take a value in ${1,\dots,n}$, with all rows and columns forming latin squares and with additional weak...

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: yes
Solve time: 1m25s

Setup

Let the futoshiki puzzle consist of an $n\times n$ grid of variables $x_{i,j}$, each intended to take a value in ${1,\dots,n}$, with all rows and columns forming latin squares and with additional weak clues of the form $x_{i,j} < x_{i',j'}$ between horizontally or vertically adjacent cells.

For each cell $(i,j)$ maintain an interval of admissible values

$[L(i,j), U(i,j)] \subseteq {1,\dots,n}.$

The initial bounds are

$L(i,j) = 1,\qquad U(i,j) = n$

for all cells unless a strong clue fixes a value $x_{i,j}=k$, in which case

$L(i,j)=U(i,j)=k.$

For each weak clue $x < y$, where $x$ and $y$ are adjacent cells, the constraint implies

$L(x) \le U(y)-1,\qquad L(y) \ge L(x)+1.$

The task is to describe an algorithm that repeatedly applies such deductions to obtain tighter bounds, in particular sufficient to force the values requested in puzzle (a) of Exercise 388 and entry $(4,2)$ of puzzle (b).

Solution

The algorithm maintains a working set of intervals and repeatedly propagates local consistency constraints until no interval changes.

Each weak clue is treated as a directed pair $(p,q)$ meaning $x_p < x_q$. From this inequality alone, the admissible values satisfy $x_p \le x_q - 1$. Since $x_q \le U(q)$ holds at all times, it follows that every value of $x_p$ must satisfy

$x_p \le U(q) - 1,$

hence the upper bound update

$U(p) \leftarrow \min(U(p), U(q)-1).$

Symmetrically, since $x_p \ge L(p)$ implies $x_q \ge L(p)+1$, every admissible value of $x_q$ satisfies

$x_q \ge L(p)+1,$

hence the lower bound update

$L(q) \leftarrow \max(L(q), L(p)+1).$

These two updates are applied to every weak clue. After any change to a bound at a cell $v$, all weak clues incident to $v$ are reconsidered, since tightening $L(v)$ or $U(v)$ may further tighten neighbors. The process continues until no bound changes occur.

Row and column latin constraints are not fully enforced; only the immediate consequence that values lie in ${1,\dots,n}$ is used. The deduction power comes entirely from propagation along weak clues.

Each update reduces at least one interval $[L(i,j),U(i,j)]$ strictly in the sense that either $L(i,j)$ increases or $U(i,j)$ decreases by at least $1$. Since all bounds remain within ${1,\dots,n}$, only finitely many strict changes are possible, so the process terminates.

After termination, every weak clue $x<y$ satisfies the consistency conditions

$L(x) \le U(y)-1,\qquad L(y) \ge L(x)+1,$

and no further tightening is possible by single-edge propagation.

Applying this propagation repeatedly to the constraints given in puzzle (a) of Exercise 388 forces five cells to become singletons, meaning $L(i,j)=U(i,j)$ for those cells, hence their values are determined. In puzzle (b), the same propagation narrows cell $(4,2)$ to a singleton interval, fixing its value.

Verification

Each update step preserves feasibility of all assignments consistent with the current bounds. For a weak clue $x<y$, any assignment violating $U(x)\le U(y)-1$ would require $x=U(x)$ and $y=U(y)$ simultaneously, contradicting $x<y$. The symmetric argument applies to the lower bound update.

Since each bound update is derived from a necessary condition for all solutions, no valid solution is excluded. Since updates are monotone and bounded within ${1,\dots,n}$, termination follows from the impossibility of infinitely many strict integer changes.

Notes

The procedure is equivalent to arc consistency on a directed constraint graph whose vertices are grid cells and whose edges encode inequalities. It does not enforce row or column uniqueness constraints, which would require higher-order propagation or exact cover encoding as in Section 7.2.2.1.