... by: Gaurav singh
Mr Stuart,
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
Thanks for this analysis, Andrew. Saves me reading the detail of the article. The Holy Grail (which you describe so well) isn't under threat from this approach.
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
Hi Maciej,
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
Dear Mr. Stuart
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
Overall an excellent criticism of Crook's work with a compelling explanation of what has driven the development of more advanced sudoku techniques.
