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
Email addresses are never displayed, but they are required to confirm your comments. When you enter your name and email address, you'll be sent a link to confirm your comment. Line breaks and paragraphs are automatically converted - no need to use <p> or <br> tags.
... by: Peter Steinhaus
Thank you very much for this page and your dedication towards Sudoku.
I have a lot of respect for you.
Concerning this Article and the use of "Trial and Error" or "a priori vs. a posteriori knowledge": First I was completely on the same page with you and especially liked the use of "a prioir vs. a poteriori knowledge". However, after thinking a bit more about this topic, I came to the following conclusion for myself: (Most of) The strategies presented on this site are at their core also based on "a posteriori knowledge", especially onces beyond basic level strategies. The explanation of the strategies on this site often go as "If you put X into A6 then this and that happens ... and if you put in Y than this and that happens. Therefore, Z can be excluded in cell A8". In my opinion, for everything that goes beyond basic level strategies "trial and error" is essentially needed at its core. The difference and that is your point, as I understand it, is that you can learn these strategies and their underlying pattern. Once a player has internalized a particular strategy/pattern (which is essentially based on "trial and error") it evolves from "a posterior" into "a prior knowledge" for this player.
My personal view on this topic: I am no genius and, especially, not a mathematician. I am also not the best at pattern recognition and, especially, dislike learning stuff by rote. For me the latter would be the case with many of the strategies presented here. I can solve almost any hard puzzle with the basic strategies and just "easy" logical thinking. Extreme or diabolical puzzle, what ever they are called, I mostly solve by basic strategies and then "trial and error", except for basic rectangle strategies (I think they are one of the few advanced strategies that may be considered closer related to "a priori" than to "a posteriori knowledge"). For me personally, learning all these strategies here is just to much. Especially, because there are so many and sometimes it says that this strategy is a generalization of that and so on. I am very much a fan of "simple logic" and "generalization". Maybe for some people like me it would be easier, if only the general strategies are explained. Moreover, e.g. if "coloring" is left out, since many people would not color their sudokus, in my opinion, and also when playing on a computer one does not have the possibility to color. So all in all, for some people I think this page and the strategies would be more accessible if the content would be trimmed and only a few strategies (the general ones and ones which are statistically applicable the most) would be explained. I don't mean that you shouldn't have all the strategies explained here, I mean it is your page and there are many people who like this page; all I am trying to say is that maybe an extra section for "general and most effective strategies" would be helpful to some people and make the (content of the) page more accessible to a wider range of people. Effective means here: Statistically need to be known to solve sodokus more than other strategies, e.g. a threshold might be used like 10%, so that if 10% of sudokus can only be solved by knowing this advanced strategy. This leads to the elimination of strategies that need to be known for only "a handful" of sudokus. It gives users a good overview of which of the advanced strategies are "truly important" and which are only "nice to know" for this 1 sudoku out of 100 extreme ones.
Pattern recognition is a very crucial skill for a human and (at least partly) distinguishes us from machines. Pattern recognition is e.g.also very important in the game of chess. However, what I like more about chess is that, if played between humans, it still leaves room for intuition. So it is not all "learning by heart", different from what, in my opinion, is proposed here for solving sudokus.
In any case, I hope I didn't offend you or your project, because that is not the intention of this comment!! ( I am also not a native speaker) I am very grateful this page exists and you are investing so much time in maintaining it. Thanks a lot!
Best,
Peter
Looking for the pattern is as frustrating as "trial and error" because it involves a long search which can often be fruitless. I've sure I note elsewhere that a lot of the extreme strategies are only useful for computers to look use - although I have had puzzle solvers who swear they pen/paper them as well. But that is not your usual puzzle solver. Also - I don't publish the extremes in a newspaper. They are the end tail of the bell-curve. But I am interested in ANY strategy that help avoid guessing. Sometimes we can get rid of an over-complicated strategy (like Empty Rectangles) and replace it with a much simpler one (eg Rectangle Elimination). This is the goal of the website. To find the optimal least-complex way to solve all puzzles. That after 20 years we (or at least I - other solvers claim differently) can't solve all puzzles makes the topic so interesting.
I definitely recognise the superior human attribute that is "insight". Can't encode that. I am not a regular pen-and-paper solver so I would be the wrong person to write a "general and most effective strategies" column. And if someone did I think it would be hard to convey to an audience as it invokes more mystical language rather than the cold determinism I am fond of here.
"Pattern recognition is a very crucial skill for a human and (at least partly) distinguishes us from machines"
- actually the opposite is true, computers are made for pattern matching
I do have some stats on the frequency of occurrence of strategies:
https://www.sudokuwiki.org/The_Relative_Incidence_of_Sudoku_Strategies
However this is one-dimensional in that it is skewed to the specific order. A real statistical anaylsis would consider all possible orderings (after the basics) but I don’t have the time or statistical knowledge to combine the results.
Good conversation though
... 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: 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
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: Jim Dennis