SudokuWiki.org
Strategies for Popular Number Puzzles
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.
Comments
... by: Gaurav singh
I deeply appreciate your contribution to the world
of sudoku.
I have developed a sudoku algorithm that can solve
1) any sudoku with one solution
2) any sudoku with multiple solutions
Theoretically, it will produce all possible sudokus that can be constructed if you work the algorithm on a blank grid.
The algorithm is of course exhaustive, and implements big integers to find the solution(s) very quickly.
Each sudoku can be thought of as a collection of linear equations having integral solutions of a certain type. Solving every set of such equations can only be achieved using exhaustive searchig because of quantized nature of integral solutions.
There can not be any "logical" theory that provides
every solution unless it becomes exhaustive that we call "logical" .For example
x+y=6 where (x,y) belong to (1,5)
here the solutions seem logical but are exhaustive.
Lastly i request you to tell me how and where can
i publish this finding(algorithm) of mine, I ask this
because i am new to this world.
... by: jenny b
I wonder if you have collected links to other attempts on the HG, and if so, if you could publish them, with or without an analysis. It would make interesting reading.
I rarely have time to read what logical strategists have to say (I work a 60+-hour week) and I have completely avoided reading other people's methods, preferring to work out my own (for me, that's the point of Sudoku).
As a result, I have always used a substantially different approach, and have felt for years as if I'm hovering on the edge of the Holy Grail, but there's always that one Diabolical my approach doesn't solve, for the ten that it does. Solving that one-in-ten isn't a problem - the problem for me is finding that integrated all-inclusive Holy Grail.
So I've started comparing what I do with what other people do, and now waste a lot of time reading, only to find out in general that published methods don't add anything to mine, and (most frustratingly) are often entirely superfluous to me, because they're aimed at removing candidates which I would never have put there in the first place.
So if you could summarise Holy Grail attempts, I'd be immensely interested and grateful!
Thanks for the quality of your contributions to the debate.
... by: Andrew Stuart
I don't disagree with you that the article "adds value" - it is a clear approach to trial and error beyond basic strategies. However it purports - and the media picked it up as purporting - to be a general logical solving theory, and I was disappointed to find it not to be. I do class Sudokus into one of these general groups:
1) sudokus that can be solved using logical strategies that humans can use
2) sudokus that can be solved using logical strategies that humans find difficult to use
3) sudokus that can be solved using trial and error / birfiucation / back tracking / brute force
Sudokus in group 2 may genuinely require very hard strategies, or the easier strategies need improving, or a different solve route used. I don't know yet without more work.
I don't disagree that one one level the strategies in 3) are not logical - they are perfectly algorithmic What I look for in a logical strategy is a pattern that exists on the board which you can make a deduction from. Because strategies in group (3) are simply efficient, organised ways of guessing. That's my contention about Crookes.
As to how many Sudoku's are unsolvable, that depends on your list of strategies and how you implement them. I know I am not exhaustive and I am continuing to add to my list. But when I make stock - I produce random sudoku puzzles with the minimum number of clue which have a unique solution. Then I grade them. About 0.2% are unsolvable using the techniques I have. About 1/2 of those could be solved with Nishio/Bowmans, but I don't like to reply on those strategies.
I do have lists around. I published a few on certain forums and most could be cracked using either an extension or combination of the strategies I have programmed. So they are very useful for improving my list. However, I don't have time to absorb all these results yet. For the most part, you will never see such puzzles in the newspaper.
... by: Maciej
I recently wrote an article about sudoku and consequences of Prof. Crook's algoritm (not in English). I completely understand your point of view, but the question is: "does his algoritm gives some added value to what we know and what we can?".
From this point of view my answer is "yes". One could say that he wanted to allow trained yet ordinary people solve very hard sudokus which need guessing (or using "Ariadne threat" or however we'll call it). If that's impossible to avoid it, like here:
.......39
.....1..5
..3.5.8..
..8.9...6
.7...2...
1..4.....
..9.8..5.
.2....6..
4..7.....
then we don't have to use absolutely every possible method to solve it. You can only argue that it's better to use guessing as little as possible, eg. doing it 5 times is better then 50 times. That is still true but only for computers under my second point.
My second objection is that some pure logic strategies itself require computation beyond human capabilities. Hence they are useless for humans - or at least unpractical. So if we'll limit the application of his method to:
1) sudokus that cannot be solved by pure logic
2) humans
then I think Crook's algoritm is an added value in the mathematics of sudoku. In the other words, it's a method to solve extremely hard sudokus using pen and paper - something that he'd expained in the title.
sincerely,
Maciej Psyk
Maciej.Psyk@gmail.com
... by: Jim Dennis