Difficult-to-solve Sudoku wanted
-
Or no missing squares...
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay... AntiTwitter: @DalekDave is now a follower!
-
I wrote a small (85 lines of C# code) backtraking Sudoku solver - primarily to illustrate the idea of backtracking. (After all, the fun of Sudoku is not "Press this button to se the solution", but exercizing your brain :-).) Wikipedia claims that the general problem of solving a Sudoku "is known to be NP-complete". So I thought finding a Sudoku problem that could really stress a PC would be simple. Not true. The most difficult I have found until now solves in 3.4 milliseconds, evaluating about 110,000 tentative digit placements (about 30 ns per evaluation). A typical "trait" of backtracking is that on the average it usually performs well, but the worst case performance may be bad. So I am searching for examples of that worst-case performance :-). Where can I find Sudoku boards that are truly difficult to solve, even for a PC? NP complete problems are extremely dependent on problem size, and 9 by 9 is not exactly a large problem. My solver can handle any board size, but I made a very quick and dirty user interface that handles 9 by 9 only, so I would like to stay within that size.
Just to get things straightened out:* The minimum number of squares for a solvable sudoku is 17. It may take more. Worked out long ago by a mathematician. Note that this is not a Japanese invention - it just became popular there, first.
- Sudoku is solved logically - not by trial-and-error. The contents of the boxes are determine uniquely to solve it. As the puzzle gets more complex, the required abstractions are more complex - but the values entered are deduced - not guessed.
- A Sudoku with more than one solution (like many here suggested) is not solvable. Sudoku, as a proper puzzle, must have one and only one solution or an impasse will be caused whereby a unique entry in a particular square cannot be determined.
The computational solution, I was disappointed to learn, was basically trial and error, with unwinding at an impasse and retrial until the board is completed. This is very different for determining difficulty than the human-difficult. For the same reason, the computer would solve a Sudoku that has multiple solutions - it doesn't check for that (does it?). Thus, difficulty by PC standards will probably need to be determined by using many puzzle version and looking for a trend, or analysis on the part of the programmer to determine how to force his algorithm to be stressed. I first became interested in Sudoku when it was comparatively new in US Newspapers. I was interested in solving it analytically by computer. The simple algorithm worked, solving in 3-4 passes. Then more difficult puzzles began to appear. I came up with another layer. Fortunately . . . with a bool didChange flag so it wouldn't iterate forever. It rapidly became more complex than I had time for. I must say, however, converting the thought process into code was a great exercise.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
-
Just to get things straightened out:* The minimum number of squares for a solvable sudoku is 17. It may take more. Worked out long ago by a mathematician. Note that this is not a Japanese invention - it just became popular there, first.
- Sudoku is solved logically - not by trial-and-error. The contents of the boxes are determine uniquely to solve it. As the puzzle gets more complex, the required abstractions are more complex - but the values entered are deduced - not guessed.
- A Sudoku with more than one solution (like many here suggested) is not solvable. Sudoku, as a proper puzzle, must have one and only one solution or an impasse will be caused whereby a unique entry in a particular square cannot be determined.
The computational solution, I was disappointed to learn, was basically trial and error, with unwinding at an impasse and retrial until the board is completed. This is very different for determining difficulty than the human-difficult. For the same reason, the computer would solve a Sudoku that has multiple solutions - it doesn't check for that (does it?). Thus, difficulty by PC standards will probably need to be determined by using many puzzle version and looking for a trend, or analysis on the part of the programmer to determine how to force his algorithm to be stressed. I first became interested in Sudoku when it was comparatively new in US Newspapers. I was interested in solving it analytically by computer. The simple algorithm worked, solving in 3-4 passes. Then more difficult puzzles began to appear. I came up with another layer. Fortunately . . . with a bool didChange flag so it wouldn't iterate forever. It rapidly became more complex than I had time for. I must say, however, converting the thought process into code was a great exercise.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
W∴ Balboos wrote:
Sudoku is solved logically
In a strictly logical sense I trust that you are correct. But [EDIT: methinks] the OP has another approach. Above we are (at least I am) discussing how to stress-test that approach.
... such stuff as dreams are made on
-
W∴ Balboos wrote:
Sudoku is solved logically
In a strictly logical sense I trust that you are correct. But [EDIT: methinks] the OP has another approach. Above we are (at least I am) discussing how to stress-test that approach.
... such stuff as dreams are made on
Include in my post (my disappointment that computational solutions are by trial-and-error). It would still be an improper test if there are multiple answers. I assume that it would even speed up the solution as each pathway reduces the chances of a rollback. However - I do have an idea on how to stress-test it! Initialize it so that it cannot be solved. That's as difficult as it gets. If the algorithm doesn't check for an invalid initialization (i.e., pre-violation of rules) then it will always fail. What Fun ! ! ! !
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
-
My backtracker makes 970 checks to fill an empty Sudoku board correctly, in about 30 microseconds. Don't ask me how that CPU can do the check in 30 ns/check, but it does. The program has a single thread; before I started coding I was considering how to do multithreaded backtracking, but when a typical problem is solved in a handful milliseconds, then you don't do multithreading to improve response time. Actually, one reason why I would like a really difficult, time consuming one is to see if I can make it faster by multithreading.
-
I would think that less much clues with a multitude of solutions gives you a deeper search tree. I would not be surprised if that takes more time...
... such stuff as dreams are made on
And then again, zero clues (all empty board) is super-simple, for finding the fist solution. I have not yet given my solver any "search further" function; the first solution is accepted. I haven't often seen "real" uses of backtracking with a need to find all solutions, so until now I haven't seen the need for it. Maybe finding all solutions would take significantly more time.
-
Include in my post (my disappointment that computational solutions are by trial-and-error). It would still be an improper test if there are multiple answers. I assume that it would even speed up the solution as each pathway reduces the chances of a rollback. However - I do have an idea on how to stress-test it! Initialize it so that it cannot be solved. That's as difficult as it gets. If the algorithm doesn't check for an invalid initialization (i.e., pre-violation of rules) then it will always fail. What Fun ! ! ! !
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
There are computational solvers that doesn't do it by trial and error. Check out Sudoku Solver by Andrew Stuart[^] It allows you to step the solution, and it gives you an explanation for all the strategies used.
Wrong is evil and must be defeated. - Jeff Ello
-
Include in my post (my disappointment that computational solutions are by trial-and-error). It would still be an improper test if there are multiple answers. I assume that it would even speed up the solution as each pathway reduces the chances of a rollback. However - I do have an idea on how to stress-test it! Initialize it so that it cannot be solved. That's as difficult as it gets. If the algorithm doesn't check for an invalid initialization (i.e., pre-violation of rules) then it will always fail. What Fun ! ! ! !
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
You use "trial and error" as if it you want to label one method as extremely inferior, compared to your favorite method. No matter what method you use, you do not come up with all the missing 64 (or possibly fewer, if you have more than 17 clues) in parallel, as a single atomic result of deep thought. Even if you do not pronounce it, in your head you will "try out" suggestions for filling in the squares, and reject those that breaks the rules. An algorithm for evaluating possibilities in turn, and reject those that do not satisfy requirements, is not an inferior "trial and error" or a highly respected "logical" solution depending on the order in which you evaluate the possibilities. They are all logical, systematic methods - call them "algorithms" if you like. One algorithm may be faster than another, simpler than another, require less temporary space than another. But one algorithm doesn't have "higher moral standing" (as "logical") than another algorithm (branded as inferior "trial and error") because it evaluates options in a different way. The way I wrote my backtracking currently reports the first solution found (or failure, if there is no solution), ignoring other solutions. So it assumes that the clues are properly set up, no pre-violation of rules. Now I made a quick check: To the board that requires 110,000 checks to find the one solution, I added another clue that makes it non-solvable. It took 59,000 checks to detect that it wasn't solvable. For robustness, I could do a check for pre-violations, but that would be a oneshot setup issue that probably would take less than a microsecond. It wouldn't at all affect or be affected by the number of iterations/recursions.
-
There are computational solvers that doesn't do it by trial and error. Check out Sudoku Solver by Andrew Stuart[^] It allows you to step the solution, and it gives you an explanation for all the strategies used.
Wrong is evil and must be defeated. - Jeff Ello
-
You use "trial and error" as if it you want to label one method as extremely inferior, compared to your favorite method. No matter what method you use, you do not come up with all the missing 64 (or possibly fewer, if you have more than 17 clues) in parallel, as a single atomic result of deep thought. Even if you do not pronounce it, in your head you will "try out" suggestions for filling in the squares, and reject those that breaks the rules. An algorithm for evaluating possibilities in turn, and reject those that do not satisfy requirements, is not an inferior "trial and error" or a highly respected "logical" solution depending on the order in which you evaluate the possibilities. They are all logical, systematic methods - call them "algorithms" if you like. One algorithm may be faster than another, simpler than another, require less temporary space than another. But one algorithm doesn't have "higher moral standing" (as "logical") than another algorithm (branded as inferior "trial and error") because it evaluates options in a different way. The way I wrote my backtracking currently reports the first solution found (or failure, if there is no solution), ignoring other solutions. So it assumes that the clues are properly set up, no pre-violation of rules. Now I made a quick check: To the board that requires 110,000 checks to find the one solution, I added another clue that makes it non-solvable. It took 59,000 checks to detect that it wasn't solvable. For robustness, I could do a check for pre-violations, but that would be a oneshot setup issue that probably would take less than a microsecond. It wouldn't at all affect or be affected by the number of iterations/recursions.
As for solvers of the type you made (back tracking) - I already read about those a years ago. As an exercise for you, this is fine - as innovation - not so much, but:
Member 7989122 wrote:
Even if you do not pronounce it, in your head you will "try out" suggestions for filling in the squares, and reject those that breaks the rules.
Is a bit of a pathetic view of trial and error. The mental solutions are done ad-hoc, throughout the board, as spaces are uniquely defined. In fact, when I played Sudoku, I would (1) use ink - one shot only!, and (2) only put in a value if it was the ONE and ONLY value that could go into a location. If I was wrong - EOF. Actually - the quote from you, above, is just plain wrong. There is no try-out methodology. It IS A VALUE or it IS NOT YET DETERMINED. That's how it's played. That was, in fact, the whole point of doing it. Even if it wasn't solved - the mental exercise of abstracting values at, eventually, higher and higher abstractions was the point.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
-
There are computational solvers that doesn't do it by trial and error. Check out Sudoku Solver by Andrew Stuart[^] It allows you to step the solution, and it gives you an explanation for all the strategies used.
Wrong is evil and must be defeated. - Jeff Ello
I only briefly looked at the page - I couldn't tell how it would be solved computationally (or not) by analytical methods. The depth of algorithms is pretty impressive to solve "all" Sudoku boards. That's what I mean when I say Not Trial and Error. No backtracking. The algorithm must use India Ink, not a pencil. I just couldn't tell from the initial page from your link if that's what's being done. It would be very impressive.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
-
As for solvers of the type you made (back tracking) - I already read about those a years ago. As an exercise for you, this is fine - as innovation - not so much, but:
Member 7989122 wrote:
Even if you do not pronounce it, in your head you will "try out" suggestions for filling in the squares, and reject those that breaks the rules.
Is a bit of a pathetic view of trial and error. The mental solutions are done ad-hoc, throughout the board, as spaces are uniquely defined. In fact, when I played Sudoku, I would (1) use ink - one shot only!, and (2) only put in a value if it was the ONE and ONLY value that could go into a location. If I was wrong - EOF. Actually - the quote from you, above, is just plain wrong. There is no try-out methodology. It IS A VALUE or it IS NOT YET DETERMINED. That's how it's played. That was, in fact, the whole point of doing it. Even if it wasn't solved - the mental exercise of abstracting values at, eventually, higher and higher abstractions was the point.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
Before you write down, in ink, that digit: Don't make me believe that you have not considered different digits that you could fill in. You DO trial and error, mentally, in your head! Your only essential argument is that "But I don't write anything down until I have ascertained that it is a viable value ... at least so far". You say that you give yourself one trial, and accept the error if it was wrong, giving up that entire Sudoku board forever, never trying again. That is trial and error good as any, even though you refuse (/deny yourself) to make another try.
-
I only briefly looked at the page - I couldn't tell how it would be solved computationally (or not) by analytical methods. The depth of algorithms is pretty impressive to solve "all" Sudoku boards. That's what I mean when I say Not Trial and Error. No backtracking. The algorithm must use India Ink, not a pencil. I just couldn't tell from the initial page from your link if that's what's being done. It would be very impressive.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
It doesn't "use pencils", there are several examples where it fails. You can pick examples, scroll to the bottom. There is a brute force solver as well, click the "solution count" button.
Wrong is evil and must be defeated. - Jeff Ello
-
Before you write down, in ink, that digit: Don't make me believe that you have not considered different digits that you could fill in. You DO trial and error, mentally, in your head! Your only essential argument is that "But I don't write anything down until I have ascertained that it is a viable value ... at least so far". You say that you give yourself one trial, and accept the error if it was wrong, giving up that entire Sudoku board forever, never trying again. That is trial and error good as any, even though you refuse (/deny yourself) to make another try.
You really don't seem to get it - I do an analytical-only solution. All numbers for a given square are eliminated, except one. No "what if" at all. Should more more than one value exists they are NOT tried - one moves on to another part of the problem. Eventually, each square is uniquely defined and helps define other squares. Play the board once - win-or-lose - yup. That's right. There are and endless supply of new boards to try. Who cares about any particular one? In fact, if I stop because I am stuck, I have no way to know if the puzzle is even solvable (analytically) as it is only solvable (analytically) if the initial numbers allow for one and only one solution. A test I couldn't perform. Your algorithm will always come up with a solution, even on invalid boards (boards with more than one unique solution).
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
-
I wrote a small (85 lines of C# code) backtraking Sudoku solver - primarily to illustrate the idea of backtracking. (After all, the fun of Sudoku is not "Press this button to se the solution", but exercizing your brain :-).) Wikipedia claims that the general problem of solving a Sudoku "is known to be NP-complete". So I thought finding a Sudoku problem that could really stress a PC would be simple. Not true. The most difficult I have found until now solves in 3.4 milliseconds, evaluating about 110,000 tentative digit placements (about 30 ns per evaluation). A typical "trait" of backtracking is that on the average it usually performs well, but the worst case performance may be bad. So I am searching for examples of that worst-case performance :-). Where can I find Sudoku boards that are truly difficult to solve, even for a PC? NP complete problems are extremely dependent on problem size, and 9 by 9 is not exactly a large problem. My solver can handle any board size, but I made a very quick and dirty user interface that handles 9 by 9 only, so I would like to stay within that size.
For maximum difficulty on a puzzle continue backtracking even when the correct solution is found. You can then be sure you have found all of the possible solutions (hopefully only one for a Soduku) and will have traversed every possible path. I would not be surprised if on a 9x9 grid even this is quite quick, as a lot of the false paths will quickly cause a conflict.
-
For maximum difficulty on a puzzle continue backtracking even when the correct solution is found. You can then be sure you have found all of the possible solutions (hopefully only one for a Soduku) and will have traversed every possible path. I would not be surprised if on a 9x9 grid even this is quite quick, as a lot of the false paths will quickly cause a conflict.
Fueled By Caffeine wrote:
will have traversed every possible path.
Certainly not in the sense "every digit in every position". Backtracking shortcuts any recursion tree as soon as it can be shown to be invalid. Out of pure curiosity, I will add "search further" to my solver, just to see how much it costs to confirm that there is no other solution. My guess is that it is more work than finding the first/only solution, but not that much more. But that's just my guess...
-
You really don't seem to get it - I do an analytical-only solution. All numbers for a given square are eliminated, except one. No "what if" at all. Should more more than one value exists they are NOT tried - one moves on to another part of the problem. Eventually, each square is uniquely defined and helps define other squares. Play the board once - win-or-lose - yup. That's right. There are and endless supply of new boards to try. Who cares about any particular one? In fact, if I stop because I am stuck, I have no way to know if the puzzle is even solvable (analytically) as it is only solvable (analytically) if the initial numbers allow for one and only one solution. A test I couldn't perform. Your algorithm will always come up with a solution, even on invalid boards (boards with more than one unique solution).
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
While you don't seem to get that your "All numbers for a given square are eliminated, except one" is an algorithmic approach good as any. If I could watch you, filling in 4 in a square, and ask you "Why not a 3?", I am quite certain that you would say "Well, because [...]". You know that 3 wouldn't work, probably because there is already a 3 in either the row or the column. You just refuse to label it as a trial and error when you look at the row and column and find a 3 there. When you discover the presence of a 3, prohibiting another 3, it is "logic", but when the program code does exactly the same, it is "trial and error". But it is the same thing. It occurs to me that you might consider Fermat's theorem unproven, as the proof involved lower-value algorithmic evaluation, not "logic" of a much higher esteem.
-
While you don't seem to get that your "All numbers for a given square are eliminated, except one" is an algorithmic approach good as any. If I could watch you, filling in 4 in a square, and ask you "Why not a 3?", I am quite certain that you would say "Well, because [...]". You know that 3 wouldn't work, probably because there is already a 3 in either the row or the column. You just refuse to label it as a trial and error when you look at the row and column and find a 3 there. When you discover the presence of a 3, prohibiting another 3, it is "logic", but when the program code does exactly the same, it is "trial and error". But it is the same thing. It occurs to me that you might consider Fermat's theorem unproven, as the proof involved lower-value algorithmic evaluation, not "logic" of a much higher esteem.
I might have mixed up two proofs - maybe Fermat's Last Theorem did not require a computer algoritm. But the four-color theorem (that you cannot make a flat map where more than four areas all have common borders) was by "logic" reduced to a huge set of possibilities that had to be considered one by one, and this work was done by a computer. There are people who reject the proof for that reason.
-
While you don't seem to get that your "All numbers for a given square are eliminated, except one" is an algorithmic approach good as any. If I could watch you, filling in 4 in a square, and ask you "Why not a 3?", I am quite certain that you would say "Well, because [...]". You know that 3 wouldn't work, probably because there is already a 3 in either the row or the column. You just refuse to label it as a trial and error when you look at the row and column and find a 3 there. When you discover the presence of a 3, prohibiting another 3, it is "logic", but when the program code does exactly the same, it is "trial and error". But it is the same thing. It occurs to me that you might consider Fermat's theorem unproven, as the proof involved lower-value algorithmic evaluation, not "logic" of a much higher esteem.
Member 7989122 wrote:
If I could watch you, filling in 4 in a square, and ask you "Why not a 3?", I am quite certain that you would say "Well, because [...]". You know that 3 wouldn't work, probably because there is already a 3 in either the row or the column. You just refuse to label it as a trial and error when you look at the row and column and find a 3 there.
Which is analytical. I wouldn't even consider trying 3 as it was logically excluded. When all numbers but one are logically excluded then that is the value. Not, like your algorithm, try 2. Uh oh, didn't work. Remove it. Try 3. Still doesn't work. Remove it. Try 4 - ah - no problems . . . yet. Down the line you may end up rolling back past the 4, as well. Your algorithm is just organized guesswork at a very high rate of speed.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
-
Member 7989122 wrote:
If I could watch you, filling in 4 in a square, and ask you "Why not a 3?", I am quite certain that you would say "Well, because [...]". You know that 3 wouldn't work, probably because there is already a 3 in either the row or the column. You just refuse to label it as a trial and error when you look at the row and column and find a 3 there.
Which is analytical. I wouldn't even consider trying 3 as it was logically excluded. When all numbers but one are logically excluded then that is the value. Not, like your algorithm, try 2. Uh oh, didn't work. Remove it. Try 3. Still doesn't work. Remove it. Try 4 - ah - no problems . . . yet. Down the line you may end up rolling back past the 4, as well. Your algorithm is just organized guesswork at a very high rate of speed.
"The difference between genius and stupidity is that genius has its limits." - Albert Einstein
"If you are searching for perfection in others, then you seek disappointment. If you are seek perfection in yourself, then you will find failure." - Balboos HaGadol Mar 2010
You wouldn't know that it was "logically excluded" without considering the digits already in the row and column. You inspection of the row and column doesn't differ from the computer's inspection of the row and column. The computer decides that 3 is "logically excluded", exactly like you do.
