Was "Crook's algorithm" for Sudoku really only developed in the 21st century?

Question

The following algorithm for simplifying (and very often completely solving) Sudoku puzzles:

1. Label each cell with the set of all possible values it could take.
2. Pick a row/column/block and for a value of $K\in[1, 9)$, look for "$K$-partnerships" -- $K$-tuples of cells that satisfy "the union of labels of each cell in the tuple has cardinality $K$". Call the "union of labels of each cell in a partnership" the "banned set" of the partnership.
3. For each such partnership, for all cells in that row/column/block not in the partnership remove any element in its label that are in the banned set of the partnership.
4. Repeat Steps 2-3 for all values of $K$ and all rows, columns and blocks.

(i.e. "if you have three cells labeled as (4, 5), (4, 7), (4, 5, 7), no other cell in that row can be 4, 5 or 7")

... has always seemed obvious to me, but I'm now informed from some sources that it has a name called "Crook's algorithm":

• http://pi.math.cornell.edu/~mec/Summer2009/meerkamp/Site/Solving_any_Sudoku_II.html
• https://www.ams.org/notices/200904/tx090400460p.pdf

The latter (by Crook) attributes the algorithm to texts written in 2005 and 2006. Are these really the earliest references? I'm pretty sure this must have been well-known for decades, but I'm not sure what to search for to find older references.

Answer 1

When designed for speed rather than adherence to human solving process, and with the notable exception of those based on exact cover, most of the Sudoku solving algorithms I've seen are functionally equivalent to DPLL from 1962.

Usually the correspondence is not explicit and the representation is not CNF. Instead the representation and the algorithm are tightly coupled to exploit the structure of Sudoku and the propagation step is unit propagation plus whatever additional inference rules are efficient given that representation (typically hidden singles or locked candidates).

That said, there is usually a non-minimal equisatisfiable CNF representation that, coupled with DPLL, produces exactly the same pattern of inference and search (given the same heuristics). This is certainly true for most casual Sudoku algorithms as well as some of the fastest ones (e.g., fsss2, jczsolve and its derivatives, or tdoku).

Viewed this way, Crook's algorithm is just the DPLL template adapted for human search, where "whatever inference rules are efficient" includes, for humans, direct consequences of the pigeonhole principle.

I can't speak to the history of Crook's formulation, but even if the ingredients (pseudo DPLL + pigeonhole principle) have been known forever, it's still a nice contribution to call attention to their use together as a uniform procedure for human puzzle solving that works for most puzzles and doesn't require memorizing a long list of patterns.

Answer 2

Modern Sudoku was only invented around 1979, and not widespread for another 10+ years.
Source: Sudoku on Wikipedia

Had the algorithms been developed immediately after Sudoku became widespread, it would have only been about 25 years before the dates you mention. Hardly time for them to be well-known for decades

Answer 3

Well, I have two points to make.

First, Crook's algorithm has more to it than the part you've described here. Specifically, if the part that you've described fails to solve the puzzle, then the next step of Crook's algorithm is to select an arbitrary unsolved cell, pick an arbitrary possible value for it, and attempt to solve the puzzle under the assumption that that cell has that value. (See the page that you linked, "Mathematics and Sudokus: Solving Algorithms (II)"; this is steps 5 and 7.) If you fail to solve the puzzle with this assumption, then you have succeeded in proving that the assumption is impossible.

Second, I don't see anyone claiming that Crook invented Crook's algorithm. It is, after all, just a combination of a few techniques:

• Pencil marks, used in the standard way.
• Pinned squares, hidden pairs, hidden triples, hidden quads, naked quads, naked triples, naked pairs. (These are all versions of the same technique; they're what you've called $K$-partnerships, after Tom Sheldon.)
• Trial and elimination.

Whoever discovered the last of these techniques essentially discovered Crook's algorithm.

What Crook did, though, was to select some techniques, form those techniques into one particular algorithm (as opposed to a mere collection of techniques for a person to use in whatever combination they wish), describe that algorithm using mathematical language, and publish that description in a mathematical journal. And so this particular algorithm is now known as "Crook's algorithm," perhaps more out of the desire to have a simple name for it than for any other reason.