TAOCP 7.2.2.1 Exercise 211

We analyze bipairs in the standard exact cover formulations of the Langford pair problem, the $n$ queens problem, and Sudoku.

taocpmathematicsalgorithmsvolume-4hard

Section 7.2.2.1: Dancing Links

Exercise 211. [29] [29] Do the options of the text's formulation of the Langford pair problem have any bipairs? How about the $n$ queens problem? And sudoku?

Verified: no
Solve time: 3m02s

We analyze bipairs in the standard exact cover formulations of the Langford pair problem, the $n$ queens problem, and Sudoku. A bipair is a pair of distinct options whose item-sets intersect in exactly two items.

Langford pair problem

An option corresponds to placing the two occurrences of symbol $k$ at positions $i$ and $i+k+1$. The associated items are:

  • position items $i$ and $i+k+1$
  • symbol usage item $k$

Thus each option has exactly three items.

Let two distinct options be

$$ O = (k, i, i+k+1), \quad O' = (\ell, j, j+\ell+1). $$

Case 1: $k \neq \ell$

Then $O$ contains item $k$ while $O'$ contains item $\ell$, so they share no symbol item. Any shared items must come only from positions. If they shared two position items, then the two placements occupy exactly the same two positions. That forces

$$ {i, i+k+1} = {j, j+\ell+1}. $$

This implies the same unordered distance between the positions, hence the same value of $k$, contradiction. Therefore they cannot share two items.

So the intersection has size at most $1$.

Case 2: $k = \ell$

Then both options use the same symbol item $k$. Distinctness means the position pairs differ. If they shared one position item, say $i=j$, then equality of the second positions would force $i+k+1 = j+k+1$, hence identical options. So distinct options share at most one item.

Thus no pair of distinct options shares two items.

Conclusion: No bipairs occur in the Langford pair formulation.

$n$ queens problem

An option corresponds to placing a queen at square $(r,c)$. The items are:

  • row item $r$
  • column item $c$
  • main diagonal item $r-c$
  • anti-diagonal item $r+c$

So each option has four items:

$$ {r, c, r-c, r+c}. $$

Let two distinct options be at $(r,c)$ and $(r',c')$.

Step 1: possible shared item pairs

We examine whether two shared items can occur without forcing equality.

  • Row and column:

$$ r=r',\ c=c' \Rightarrow \text{same square}. $$

  • Row and main diagonal:

$$ r=r',\ r-c=r'-c' \Rightarrow c=c' \Rightarrow \text{same square}. $$

  • Row and anti-diagonal:

$$ r=r',\ r+c=r'+c' \Rightarrow c=c' \Rightarrow \text{same square}. $$

  • Column and main diagonal:

$$ c=c',\ r-c=r'-c' \Rightarrow r=r' \Rightarrow \text{same square}. $$

  • Column and anti-diagonal:

$$ c=c',\ r+c=r'+c' \Rightarrow r=r' \Rightarrow \text{same square}. $$

  • Main and anti-diagonal:

$$ r-c=a,\quad r+c=b $$

uniquely determine

$$ r=\frac{a+b}{2},\quad c=\frac{b-a}{2}. $$

Hence equality of both diagonal items forces equality of the square.

Step 2: conclusion

Any two shared items determine $(r,c)$ uniquely. Therefore two distinct options cannot share two items.

Conclusion: No bipairs occur in the $n$ queens formulation.

Sudoku

An option corresponds to placing digit $d$ in cell $(r,c)$. The items are:

  • cell item $(r,c)$
  • row-digit item $(r,d)$
  • column-digit item $(c,d)$
  • box-digit item $(b,d)$, where $b$ is the 3×3 box of $(r,c)$

Thus each option has four items:

$$ {(r,c), (r,d), (c,d), (b,d)}. $$

We show that bipairs do exist by constructing a pair of distinct options with exactly two shared items.

Construction of a bipair

Fix a row $r$, a digit $d$, and a 3×3 box $b$. In any box, there are exactly three columns in that row. Choose two distinct columns $c_1 \neq c_2$ in the same box $b$.

Consider the two options:

$$ O_1 = (r,c_1,d), \quad O_2 = (r,c_2,d). $$

Shared items

Both options share:

  • row-digit item $(r,d)$
  • box-digit item $(b,d)$

Distinct items

They differ in:

  • cell items: $(r,c_1) \neq (r,c_2)$
  • column-digit items: $(c_1,d) \neq (c_2,d)$

Thus:

$$ |O_1 \cap O_2| = 2. $$

Conclusion for Sudoku

Such pairs exist in every row and box, so bipairs occur in the standard Sudoku exact cover formulation.

Final conclusion

  • Langford pair problem: no bipairs
  • $n$ queens problem: no bipairs
  • Sudoku: bipairs do occur, given by two placements of the same digit in the same row and same 3×3 box but different columns

$$ \boxed{\text{Langford: no bipairs; $n$ queens: no bipairs; Sudoku: bipairs exist.}} $$