|
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 ! ! ! !
| Ravings en masse^ |
|---|
| "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.
|
|
|
|
|
How do you distinguish between "trial and error" and "checking if conditions are met"?
|
|
|
|
|
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.
| Ravings en masse^ |
|---|
| "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.
|
|
|
|
|
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.
| Ravings en masse^ |
|---|
| "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.
|
|
|
|
|
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).
| Ravings en masse^ |
|---|
| "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.
|
|
|
|
|
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.
|
|
|
|
|
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.
| Ravings en masse^ |
|---|
| "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.
|
|
|
|
|
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.
| Ravings en masse^ |
|---|
| "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.
|
|
|
|
|
"
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 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.
| Ravings en masse^ |
|---|
| "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 |
|
|
|
|
|
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...
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
try this one and report back:
.........
.......12
..3.45...
.........
..6...4..
.7.1.....
..82...7.
3.9.5....
4...6....
modified 19-Mar-18 22:12pm.
|
|
|
|
|
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.
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
