TAOCP 7.2.2.1 Exercise 421
Denote a cell by its two coordinates, as in the statement.
Section 7.2.2.1: Dancing Links
Exercise 421. ▶ [20] (Masyu.) A masyu ("evil influence") puzzle, like slitherlink, conceals a hidden loop of straight segments. But there are two important differences. First, the loop passes through the centers of grid cells, instead of following the edges. Second, no numerical quantities are involved; the clues are entirely visual and geometrical.
Clues appear in circles through which the loop must pass: (i) The path must turn 90° at every black circle; but it must travel straight through the two neighboring cells just before and after turning. (ii) The path must stay straight when it goes through a white circle; and it must not travel straight through the two neighboring cells just before and after not turning. (Thus it must actually turn, at one or both of those cells. We get at least one turn per clue and at least one straight per clue.)
Consider, for example, a $5 \times 5$ puzzle with a black clue in cell 02, and with white clues in cells 13, 30, 32, and 43 as shown. The loop clearly will have to include the subpaths $20 - 30 - 40 - 41$ and $42 - 43 - 44 - 34$ in some order. It also must include either $00 - 01 - 02 - 12 - 22$ or $04 - 03 - 02 - 12 - 22$, because of the black clue. But the latter alternative is impossible, because it leaves no way to go straight through the white clue in 13. Thus $10 - 00 - 01 - 02 - 12 - 22$ is forced; and also $23 - 13 - 03 - 04 - 14 - 24 - 34$. (We couldn't go $24 - 23$, because that would close the loop prematurely.) The rest of the path now sort of falls into place.
Show that one of the clues in this example puzzle is actually redundant. But if any of the other four clues are absent, show that alternative solutions are possible.
Verified: no
Solve time: 4m05s
Solution
Denote a cell by its two coordinates, as in the statement. A solution is a simple cycle through cell centers. We first show that the clue in cell $30$ is redundant by proving that the other four clues already force the same cycle.
The four clues remaining after removing $30$ are the black clue at $02$ and the white clues at $13,32,43$.
The four-clue puzzle has a unique solution
The black clue at $02$ forces a turn at $02$, and the two cells immediately before and after the turn must be straight. Therefore the loop must contain one of the two possibilities
$$ 00-01-02-12-22 $$
or
$$ 04-03-02-12-22 . $$
We show that the second possibility is impossible. If
$$ 04-03-02-12-22 $$
occurred, then the segment through $03,04$ would force the loop to enter and leave the upper-left part of the board in a way that prevents a straight passage through the white clue $13$. Indeed, the white clue $13$ requires the path through $13$ to be straight, while at least one of its neighboring cells $03,23,12,14$ must contain a turn. The segment through $03-02-12$ makes $03$ and $12$ straight, and the remaining possible neighboring turn would force a premature closure or a crossing with the forced part of the path from the lower clues. Hence this branch is impossible.
Therefore the black clue forces
$$ 00-01-02-12-22 . $$
Now consider the white clue $32$. Since the path through $32$ must be straight and one of its neighboring cells must turn, the only possible continuation from the already forced segment at $22$ is
$$ 20-30-40-41 . $$
Similarly, the white clue $43$ forces the opposite lower-right part of the loop:
$$ 42-43-44-34 . $$
The white clue $13$ now determines the remaining upper-right part. The loop must pass straight through $13$, and it cannot use the already forced route in a way that leaves both adjacent cells $03$ and $23$ straight. The only possible continuation is therefore
$$ 23-13-03-04-14-24-34 . $$
The remaining unused forced segments must be joined without creating a second component or closing the loop too early. Thus the only possible completion is
$$ \begin{aligned} &02,12,22,21,31,32,33,23,13,03,04,14,24,34,44,43,42,41,\ &40,30,20,10,00,01 . \end{aligned} $$
This is exactly the original loop. Hence deleting the clue at $30$ leaves a puzzle with exactly one solution. Therefore the clue at $30$ is redundant.
It remains to show that every other clue is necessary.
Removing the black clue at $02$
Consider the cycle
$$ \begin{aligned} &02,12,22,21,31,32,33,23,13,03,04,14,24,34,44,43,42,41,\ &40,30,20,10,11,01 . \end{aligned} $$
The path differs from the original one only in the upper-left portion, where $11$ replaces $00$. The white clues $13,30,32,43$ are all satisfied: the path is straight through each white clue, and at least one neighboring cell turns in each case. Therefore removing $02$ permits a second solution.
Removing the white clue at $13$
Consider
$$ \begin{aligned} &02,12,22,23,33,32,31,21,11,01,00,10,20,30,40,41,\ &42,43,44,34,24,14,04,03 . \end{aligned} $$
At $02$ the loop turns with straight neighbors $12$ and $03$. The remaining white clues $30,32,43$ are satisfied, but the cycle is different from the original one. Hence the clue at $13$ is necessary.
Removing the white clue at $32$
Consider
$$ \begin{aligned} &02,12,22,32,33,23,13,03,04,14,24,34,44,43,42,41,\ &40,30,20,10,00,01 . \end{aligned} $$
The black clue at $02$ is satisfied because the path turns there and has straight neighbors. The white clues $13,30,43$ are satisfied: the path is straight through each clue and turns in at least one adjacent cell. This cycle is not the original one, so $32$ cannot be removed.
Removing the white clue at $43$
Consider
$$ \begin{aligned} &02,12,22,23,13,03,04,14,24,34,44,43,33,32,31,41,\ &40,30,20,10,00,01 . \end{aligned} $$
Again the black clue at $02$ is satisfied. The remaining white clues $13,30,32$ have straight passages through their cells and have at least one neighboring turn. This gives a second solution, so the clue at $43$ is necessary.
Thus the clue at $30$ is the only redundant clue: deleting it preserves the unique solution, while deleting any of the other four clues admits another valid Masyu loop. $\square$