Difficult-to-solve Sudoku wanted
-
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.
-
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.
Let me at least try to simplify this for you: If you have any reason to undo a value (virtually or otherwise) than it's trial and error. If you never have to undo any value than it's analytical. If you program needs to unwind your work - even a single step - you took a guess and tested it. Beyond the above, I'll leave it to someone else to get it through to you.
"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
-
Let me at least try to simplify this for you: If you have any reason to undo a value (virtually or otherwise) than it's trial and error. If you never have to undo any value than it's analytical. If you program needs to unwind your work - even a single step - you took a guess and tested it. Beyond the above, I'll leave it to someone else to get it through to you.
"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
So if a program does exactly like you do: Fill in some digit. If if later in the process fails, it reports - just like you - "Sorry, I failed to solve this problem - give me another board", then it is "logical", of the same intellectual standing as your brain. Fair enough. I'll accept that. Trying different alternatives is not "logic" (but highly illogical :-)). Some mental effort should appear as magic. Analyzing that kind of thinking, identifying the paths of thought that leads to those "logic" solutions sort of cheapens the "logic" and the magic of the human brain. So let's stick to the magic, that unexplainable that elevates the human brain from trivialities such as letting a computer follow the same rules as the human "logic". Let's pretend that human "logic" is something supernatural that cannot be explained. Sort of in a religious sense. I hereby declare that I accept your right to believe that your brain's "logic" is superior to any computer realizing a similar logic, and your right to believe that your brain's "logic" in no way considers the effect of writing a digit into a square and rejecting it, the way a computer does it.
-
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.
I took a completely different approach when I addressed the issue a few years back -- because I believe that a trial-and-error back-tracking approach is not appropriate to the challenge. Mine works by keeping track of which values a cell _may_ hold and when a cell is down to only one possible value, then it _must_ have that value, and it can then announce to its peers "my value is x" and all those other cells can announce to their peers "my value is not x" etc. And so the dominoes fall. The idea I had, was for the UI to show the user which possible values each cell had and what the relative probability of each is -- such as "this cell may be x, y, or z, but it is most likely x". Unfortunately, it turned out that the puzzle would solve itself as soon as (or even before) the user finished entering the puzzle.
-
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.
try this one and report back:
.........
.......12
..3.45...
.........
..6...4..
.7.1.....
..82...7.
3.9.5....
4...6.... -
I took a completely different approach when I addressed the issue a few years back -- because I believe that a trial-and-error back-tracking approach is not appropriate to the challenge. Mine works by keeping track of which values a cell _may_ hold and when a cell is down to only one possible value, then it _must_ have that value, and it can then announce to its peers "my value is x" and all those other cells can announce to their peers "my value is not x" etc. And so the dominoes fall. The idea I had, was for the UI to show the user which possible values each cell had and what the relative probability of each is -- such as "this cell may be x, y, or z, but it is most likely x". Unfortunately, it turned out that the puzzle would solve itself as soon as (or even before) the user finished entering the puzzle.
"When in doubt, use brute force" (attributed to Ken Thompson). In the basic Algorithms course at the University (a long time ago :-)) we of course learned sorting algorithms - and learned that when sort a subsequence of say five or six numbers, managing a quicksort costs more administration than what you save. So, below 8 elements in a subsequence, you switch to a near-zero administration bubble sort. At least half of the students (myself as one) refused to take the professor's claim at face value, doing timing with quicksort (or other nlogn method) down to sorting even two elements. Surprise, surprise: The professor was right: With less than roughly 10 elements, no.brain bubble sort IS more efficient than the intellectually superior nlogn methods, if your goal is to get the job done. I use similar reasoning in my backtracking Sudoku: In a few places I make "unneccesary" cheks, but managing the required data structures to suppress the checks would cost more resources than simply doing them. You shouldn't spend too much time on supressing a few checks taking 30 nanoseconds to execute! My solver handles all the games I have tried in less than five milliseconds. I was hoping for someone to dig up games that is not handled well by backtracking methods - but that seems to be more difficult than solving a Sudoku game :-) Do you still believe that "a backtracking approach is not appropriate to the challenge"? Is that because its simplicity is intellectualy inferior, or do you believe that it is less efficient (i.e. slower) than other methods? I would be very curious to see an algorithmic encoding of these "logic" or "analythic" solution methods, strongly suspecting that the analysis required to analythically determine that "It is no use trying the value 3 in that square" would take far more resources than simply putting a 3 in there and see if all conditions are satisfied - even though some people condsider that intellectually inferior. The difficulty is to have those guys using "logic" or "analythic" solutions come out of magician mode and explain how they know that a 4 rather than a 3 would be suitable in a given square. If they manage to explain it, it will turn out just as algorithmic as backtracking.
-
try this one and report back:
.........
.......12
..3.45...
.........
..6...4..
.7.1.....
..82...7.
3.9.5....
4...6....Yeah, that's a tough one! There actually was a noticable delay from I hit the Solve button to the result was presented - 1.49 seconds. It checked 57,286,961 tentative digits at a rate of 26 ns/check. I have added this to my test cases. If you have more in this class (or worse), I'd be happy to hear.
-
Yeah, that's a tough one! There actually was a noticable delay from I hit the Solve button to the result was presented - 1.49 seconds. It checked 57,286,961 tentative digits at a rate of 26 ns/check. I have added this to my test cases. If you have more in this class (or worse), I'd be happy to hear.
I knew that was number I expected from your 80 lines :-\ My C/C++ program took about 0.0027s to crack it :)
-
Yeah, that's a tough one! There actually was a noticable delay from I hit the Solve button to the result was presented - 1.49 seconds. It checked 57,286,961 tentative digits at a rate of 26 ns/check. I have added this to my test cases. If you have more in this class (or worse), I'd be happy to hear.
Your worst case could be worse than the previous example which was my most time consuming problem. So, here is another one that took my program 0.00002s:
.........
.....1..2
..3.2..4.
....5..6.
.1.....2.
7..8.....
...7..3..
..2..6...
5.......7 -
I knew that was number I expected from your 80 lines :-\ My C/C++ program took about 0.0027s to crack it :)
-
"When in doubt, use brute force" (attributed to Ken Thompson). In the basic Algorithms course at the University (a long time ago :-)) we of course learned sorting algorithms - and learned that when sort a subsequence of say five or six numbers, managing a quicksort costs more administration than what you save. So, below 8 elements in a subsequence, you switch to a near-zero administration bubble sort. At least half of the students (myself as one) refused to take the professor's claim at face value, doing timing with quicksort (or other nlogn method) down to sorting even two elements. Surprise, surprise: The professor was right: With less than roughly 10 elements, no.brain bubble sort IS more efficient than the intellectually superior nlogn methods, if your goal is to get the job done. I use similar reasoning in my backtracking Sudoku: In a few places I make "unneccesary" cheks, but managing the required data structures to suppress the checks would cost more resources than simply doing them. You shouldn't spend too much time on supressing a few checks taking 30 nanoseconds to execute! My solver handles all the games I have tried in less than five milliseconds. I was hoping for someone to dig up games that is not handled well by backtracking methods - but that seems to be more difficult than solving a Sudoku game :-) Do you still believe that "a backtracking approach is not appropriate to the challenge"? Is that because its simplicity is intellectualy inferior, or do you believe that it is less efficient (i.e. slower) than other methods? I would be very curious to see an algorithmic encoding of these "logic" or "analythic" solution methods, strongly suspecting that the analysis required to analythically determine that "It is no use trying the value 3 in that square" would take far more resources than simply putting a 3 in there and see if all conditions are satisfied - even though some people condsider that intellectually inferior. The difficulty is to have those guys using "logic" or "analythic" solutions come out of magician mode and explain how they know that a 4 rather than a 3 would be suitable in a given square. If they manage to explain it, it will turn out just as algorithmic as backtracking.
Certainly, and I still stand by my statement. Yet you must understand that in a UI-based app like mine, much more time is spent waiting for user input than for anything else. My technique allows the engine to perform its work while the user is preparing to make the next click. A brute-force attack must wait until all the data is available before it can begin processing. Similarly, mine should detect a puzzle with no solution without having to "try" anything -- in fact, it doesn't "try" anything anyway, it simply responds to inputs as they arrive.
-
Your worst case could be worse than the previous example which was my most time consuming problem. So, here is another one that took my program 0.00002s:
.........
.....1..2
..3.2..4.
....5..6.
.1.....2.
7..8.....
...7..3..
..2..6...
5.......720 microseconds is impressive (assuming, of course, that your program is a general solver that can find a solution for every valid Sudoku game). Now, I didn't write my little routine in an attempt to create the world's fastest Sudoku solver (in that case, lots of people would have beaten me to it: I use a straightforward backtracking routine, and that has been done many times before!). What happened was that a colleague of mine with not-too-much formal education in programming asked me if I had any hints for making a Sudoku solver. "Why don't you start out with a simple backtracking algorithm?" I suggested. "Backtracking, what is that?" ... So I wrote this little routine to illustrate what backtracking is - not to win any speed competition. I've never tried to multithread backtracking, and am curious to see if multithreading can speed up backtracking algorithms, or if the administration eats up the gain from multithreading. If you want to measure reductions in total execution time, you do not do it on a problem solved in 20 microseconds! That is why I asked for hard-to-solve Sudokus, because that was the problem for the backtracking I had been written a couple of days ago, fresh in my mind. And Wikipedia claims that the general problem of Sudoku-solving is NP-complete, so I was assuming that I could easily find games that would take "ages" to find a solution to, as good candidates for speedup by engaging multiple CPU cores. You may have interpreted the discussion between W∴ Balboos and me as if I claim that backtracking is faster that "logic" and "analytical". That is not what I am saying, but that "logic" and "analytical" approaches are not in any way "intellectually superior" or principally different from any other algorithmic solution. "Logic" and "analysis" are algorithmic as well. W∴ Balboos seems to be wanting to split algorithmic solutions into two classes: Those never evaluating a case, and then rejecting it (that represents this detestable "trial and error"), and those that allow themselves to conclude that an alternative is not a viable case for further investigation. But it seems as if W∴ Balboos wants to keep the "logic" and "analytical" approaces to Sudoku in the "magic" realm that cannot be expressed algorithmically. I believe they can, and I believe that if you do, it will be difficult to find a clear cut distinction between intellectually inferior "trial and error" type algorithms on the one side and intellectually superior "logic" and "analysis" algorithms on the other side. Un
-
Would you care to reveal details about the logic of the program, or is that "company confidential"? Can you reveal whether it is multi-threaded or not, and how many CPU cores were activated in that run?
It is still a simple brutal search program though I added some cutoffs to improve efficiency and also optimized it quite a bit. I don't see a need to go parallel for classical Sudoku at all. So, the numbers I mentioned here is coming from one core off an old laptop with i5-4200M. It is not a secret at all. It is a result of a hobby project. I will publish the code along a short descriptions of design considerations when I get the time. In fact, I did promise a friend of mine a short article about it months ago :)
-
20 microseconds is impressive (assuming, of course, that your program is a general solver that can find a solution for every valid Sudoku game). Now, I didn't write my little routine in an attempt to create the world's fastest Sudoku solver (in that case, lots of people would have beaten me to it: I use a straightforward backtracking routine, and that has been done many times before!). What happened was that a colleague of mine with not-too-much formal education in programming asked me if I had any hints for making a Sudoku solver. "Why don't you start out with a simple backtracking algorithm?" I suggested. "Backtracking, what is that?" ... So I wrote this little routine to illustrate what backtracking is - not to win any speed competition. I've never tried to multithread backtracking, and am curious to see if multithreading can speed up backtracking algorithms, or if the administration eats up the gain from multithreading. If you want to measure reductions in total execution time, you do not do it on a problem solved in 20 microseconds! That is why I asked for hard-to-solve Sudokus, because that was the problem for the backtracking I had been written a couple of days ago, fresh in my mind. And Wikipedia claims that the general problem of Sudoku-solving is NP-complete, so I was assuming that I could easily find games that would take "ages" to find a solution to, as good candidates for speedup by engaging multiple CPU cores. You may have interpreted the discussion between W∴ Balboos and me as if I claim that backtracking is faster that "logic" and "analytical". That is not what I am saying, but that "logic" and "analytical" approaches are not in any way "intellectually superior" or principally different from any other algorithmic solution. "Logic" and "analysis" are algorithmic as well. W∴ Balboos seems to be wanting to split algorithmic solutions into two classes: Those never evaluating a case, and then rejecting it (that represents this detestable "trial and error"), and those that allow themselves to conclude that an alternative is not a viable case for further investigation. But it seems as if W∴ Balboos wants to keep the "logic" and "analytical" approaces to Sudoku in the "magic" realm that cannot be expressed algorithmically. I believe they can, and I believe that if you do, it will be difficult to find a clear cut distinction between intellectually inferior "trial and error" type algorithms on the one side and intellectually superior "logic" and "analysis" algorithms on the other side. Un
Certainly my solver is a general one, cracking any classical Sudoku problems. It can do exhaustive search to see if a problem has multiple solutions. It checks validity before search. I agree most what you said here. I said to a friend when discussing Sudoku: We all know that knowledge is power. But do you still need knowledge if you have power? :) Modern physics is trying to tell us that power and knowledge are the same thing. So, I picked power :)
-
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.
" 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. " In my case, it's because the cardinality of the set of possible values is 1 and the one element of the set is 4. Now if you want to insist that because I primed the set with all the values from 1 to 9 inclusive that I "tried" all those values then we definitely have a difference of opinion.
-
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.
Additionally, if you want puzzles that are better suited to back-tracking, you might want N-Queens or Knight's Tour.
-
try this one and report back:
.........
.......12
..3.45...
.........
..6...4..
.7.1.....
..82...7.
3.9.5....
4...6....But that and the other don't lead to a single solution, do they?
-
But that and the other don't lead to a single solution, do they?
The 2 puzzles I posted here are classical Sudoku that dictates one and only one possible solution.