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.
" 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.
-
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 think you and I are on the same page here. However, I did feed the two puzzles that were provided into my engine and it didn't reach a solution. I believe mine needs more sophistication, but I wonder what yours makes of them.
-
I think you and I are on the same page here. However, I did feed the two puzzles that were provided into my engine and it didn't reach a solution. I believe mine needs more sophistication, but I wonder what yours makes of them.
PIEBALDconsult wrote:
but I wonder what yours makes would have made of them.
(FIFY) It probably would have failed. Sophistication was added in stages (based on ease of translating thought to code). Single-Box Level: 1 - does row have 8 of 9 already determined? Fill in (the most obvious). 2 - intersection of two rows: does it exclude all but one value? Sector Level (a 3x3): 3 - Exclude current contents of the 3x3, and does it force the single remaining value? 4 - Include intersecting row and column in this consideration. This worked for easy and less easy boards. The difficulty of translating thought to code keeps increasing. If it failed to change anything on a pass then game-over. Score-keeping for each box was kept with a bitmask for that box (I like bitmasks) that needed to match mask 1 - 9 (initialize to 0x1F). Could be checked, for example, via a switch. But this was long ago and more sophisticated play put it out of its misery.
"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