TAOCP 7.2.2.1 Exercise 398
Working
Section 7.2.2.1: Dancing Links
Exercise 398. [23] [23] (KenKen®.) A secret latin square whose entries are ${1, 2, \ldots, n}$ can often be deduced by means of arithmetic. A kenken puzzle specifies the sum, difference, product, or quotient of the entries in each of its "cages," which are groups of cells indicated by heavy lines, as in the following examples:
(When the operation is '$-$' or '$\div$', the cage must have just two cells. A one-cell cage simply states its contents, without any operation; hence its solution is a no-brainer.)
Cages look rather like the boxes of jigsaw sudoku; but the rules are in fact quite different: Two entries of the same cage can be equal, if they belong to
different rows and different columns. For example, the '9×' in (a) can be achieved only by multiplying the three entries ${1,3,3}$; hence there's exactly one way to fill that cage.
Solve (a), (b), (c) by hand. Show that one of them is actually not a valid puzzle.
Verified: no
Solve time: 2m45s
Working