TAOCP 7.2.2.1 Exercise 53
Working
Section 7.2.2.1: Dancing Links
Exercise 53. [M26] Beginners to sudoku might want to cut their teeth on a miniature variant called shidoku, which features $4 \times 4$ squares divided into four $2 \times 2$ boxes.
a) Prove that every uniquely solvable shidoku problem has at least four clues.
b) Two shidoku problems are equivalent if we can get from one to the other by permuting rows and columns in such a way that boxes are preserved, and/or by 90° rotation, and/or by permuting the numbers. Show that exactly 13 essentially different 4-clue shidoku problems have a unique solution.
Verified: no
Solve time: 4m29s
Working