| Main Page - Back |
|
From SudokuWiki.org, the puzzle solver's site |
Crook's Algorithm
This week has seen some articles in many newspapers about a general algorithm that solves all Sudoku puzzles. For example, The Daily Mail (on-line). In a formal paper by American scientist J.F.Crook the article does indeed have a 'general' method for solving Sudoku puzzles - but at it's heart is the old game of 'Trial and Error' - and I feel I must pour some cold water on the hyperbole generated by this attempt. I'm afraid we've seen this all before.
In case you missed the paper, it is available here:
www.ams.org/notices/200904/rtx090400460p.pdf.,
and also on my server here in case the main link is down (was at time of writing).
Now, Mr. Crook does start well with some good definitions and theorems, his "Preemptive Sets" and the "Occupancy Theorem". But in careful reading I find that the Preemptive Sets is another name for a Locked Set, something many solvers will be intimately familiar with, especially if they delve into the strategies on this web site. A Locked Set/Preemptive Set is any set of N cells occupied by exactly N candidates. Mr. Crook's first theorem states that any X that can see any cell in the Locked Set that also has X, this X can be removed. He uses the words "in range", whereas I use the verb "to see" or "can be seen by". As examples of useful preemptive sets Mr. Crook cites Naked Pairs and Triples - which is true, but barely scratches the surface of their use.
His second theorem states that, and I quote, "There is always a preemptive set that can be invoked to unhide a hidden set, which the changes the hidden set into a preemptive set except in the case of a singleton". Quite true, and this covers everything upwards from Hidden Pairs and Hidden Triples - but his generalization is not new.
Now I blanched when I first read the word "random" in Mr. Crook's paper - I thought - Oh no, I don't believe it. Once the ideas above are exhausted - which will be pretty quick on the hardest puzzles, the algorithm asks us to pick - randomly, or intuitively, candidates somewhere on the board. Then he describes a classic bifurcation method. Pretend candidate X in the 'markup' of that cell is true and follow the consequences. If it leads to a violation then X can be removed. Do this for all candidates - one of those numbers will not lead to any contradiction.
Amazingly Mr Crook references Michael Mephams original document on how to solve Sudoku – which was produced before the Sudoku community had gotten further than Naked and Hidden Triples. Mr. Mepham has a very similar bifurcation method. All Mr. Crook brings to the table are some rigorous definitions of constraints and locked sets.
The whole idea of logical strategies is that we want to find a pattern or reason for making an elimination and/or solution at every point in the puzzle. I, and many others, are against the idea of guessing, trialing a candidate and seeing if it produces an error. Mr. Crook has made an good attempt at showing how paper and pencil methods are perfectly viable and his paper does bring formality to the simpler aspects of the puzzle, but this is not the Holy Grail.
In a nutshell, Mr. Crook confuses a priori knowledge with a posteriori knowledge. His solution is gained through experience of the puzzle – the exploring of the paths and finding out which numbers don’t violate the rules. This is an a posteriori method. Logical strategists such as myself are looking for rules which give us surety before confirmation – an a priori method where we deduce the correct answer because we have identified a pattern that equates to a rule. Crook's theorems are such rules and are good solid a priori stuff - but he fails to show how to identify preemptive sets in ALL situations and resorts to guessing.
To make my point, we could dispense with all Mr. Crook’s theorems save his final method and guess 1 in cell (1,1) – and try all remaining numbers on all cells up to 9 in cell (9,9). This is what my brute force “Solution Count” button does, and it does it very quickly. But it doesn’t tell us why a puzzle unfolds. This is the lure of logical strategies, and I’m afraid, we are still waiting for the big one which will slay all puzzles.
In case you missed the paper, it is available here:
www.ams.org/notices/200904/rtx090400460p.pdf.,
and also on my server here in case the main link is down (was at time of writing).
Now, Mr. Crook does start well with some good definitions and theorems, his "Preemptive Sets" and the "Occupancy Theorem". But in careful reading I find that the Preemptive Sets is another name for a Locked Set, something many solvers will be intimately familiar with, especially if they delve into the strategies on this web site. A Locked Set/Preemptive Set is any set of N cells occupied by exactly N candidates. Mr. Crook's first theorem states that any X that can see any cell in the Locked Set that also has X, this X can be removed. He uses the words "in range", whereas I use the verb "to see" or "can be seen by". As examples of useful preemptive sets Mr. Crook cites Naked Pairs and Triples - which is true, but barely scratches the surface of their use.
His second theorem states that, and I quote, "There is always a preemptive set that can be invoked to unhide a hidden set, which the changes the hidden set into a preemptive set except in the case of a singleton". Quite true, and this covers everything upwards from Hidden Pairs and Hidden Triples - but his generalization is not new.
Now I blanched when I first read the word "random" in Mr. Crook's paper - I thought - Oh no, I don't believe it. Once the ideas above are exhausted - which will be pretty quick on the hardest puzzles, the algorithm asks us to pick - randomly, or intuitively, candidates somewhere on the board. Then he describes a classic bifurcation method. Pretend candidate X in the 'markup' of that cell is true and follow the consequences. If it leads to a violation then X can be removed. Do this for all candidates - one of those numbers will not lead to any contradiction.
Amazingly Mr Crook references Michael Mephams original document on how to solve Sudoku – which was produced before the Sudoku community had gotten further than Naked and Hidden Triples. Mr. Mepham has a very similar bifurcation method. All Mr. Crook brings to the table are some rigorous definitions of constraints and locked sets.
The whole idea of logical strategies is that we want to find a pattern or reason for making an elimination and/or solution at every point in the puzzle. I, and many others, are against the idea of guessing, trialing a candidate and seeing if it produces an error. Mr. Crook has made an good attempt at showing how paper and pencil methods are perfectly viable and his paper does bring formality to the simpler aspects of the puzzle, but this is not the Holy Grail.
In a nutshell, Mr. Crook confuses a priori knowledge with a posteriori knowledge. His solution is gained through experience of the puzzle – the exploring of the paths and finding out which numbers don’t violate the rules. This is an a posteriori method. Logical strategists such as myself are looking for rules which give us surety before confirmation – an a priori method where we deduce the correct answer because we have identified a pattern that equates to a rule. Crook's theorems are such rules and are good solid a priori stuff - but he fails to show how to identify preemptive sets in ALL situations and resorts to guessing.
To make my point, we could dispense with all Mr. Crook’s theorems save his final method and guess 1 in cell (1,1) – and try all remaining numbers on all cells up to 9 in cell (9,9). This is what my brute force “Solution Count” button does, and it does it very quickly. But it doesn’t tell us why a puzzle unfolds. This is the lure of logical strategies, and I’m afraid, we are still waiting for the big one which will slay all puzzles.
Andrew Stuart
Later this week I will put links up to the puzzle examples he used so they can be loaded into the solver and break down the argument more concisely.