Sudoku Assistant at your service

Bob Hanson · Posted: Thu Nov 03, 2005 9:43 pm Post subject: Sudoku Assistant at your service

http://www.stolaf.edu/people/hansonr/sudoku

I just wanted to take the time to point out that this web site is really for everyone and anyone. I'm happy to have provided it, and I hope that some people will experiment with it on their own.

So far I haven't found a puzzle it can't solve, although I believe there should be one out there somewhere. I've now run all top95 and Mark Becker's "impossible" 520 through it successfully.

I think it bears looking at, because it is all pretty straightforward stuff, with no "bifurcation" and no "backtracking" no "guessing" no "magic cells."

It just solves the Sudoku using logic and standard "known" ideas like naked/hidden ntuples and such. The two "new" ideas here are the 3D representation of "strong chains" and the use of "weak nodes" as the starting point for logical hypothesis and proof.

One feature I just added is kind of cool. From the "number block input" link you can indicate a URL from anywhere on the web that is a file containing lines having 81 characters each -- 0 or . for "unknown". It will load these into a select box, and you can then experiment all you want stopping the calculation at various points by NOT allowing one or another method, or stepping through one step at a time to see what it is doing.

Thanks to all on this list for all the great discussion leading to this. I really can't take a whole lot of credit for the ideas, just, maybe, a bit of extension of those I've read about and, of course, for the JavaScript implementation.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

xyzzy · Posted: Fri Nov 04, 2005 11:38 am Post subject:

Here is my restatement of hypothesis and proof. I believe this describes the algorithm exactly, I have just written TRUE and FALSE backwards and added some clarification.

1. Pick a node and assume it is true. We now call this node 'ESLAF' (false backwards) and know, by our guess, that it is the only true node in its four subsets.

2. Mark all eliminations that can be made from this assumption with a capital 'A', and make the eliminations. To be confusing, these capital labeled nodes are called 'EURT' (true backwards). Calling a node 'EURT' or labeling it with a capital means it has been eliminated.

3. Any singles which become apparent from the eliminations/marking in step 2 are labeled with a lowercase 'a' and are now known to be the only true node in their group. These nodes are called 'ESLAF', because we know they are true, like the the node in 1, which we assumed was true.

4. From the true aka ESLAF nodes found in step 3, we eliminate all the other nodes in the same subsets, since we now know they are false. Again, because these nodes were eliminated, we label with with a capital letter (B this time) and call them EURT nodes.

5. Recursively find singles aka ESLAF aka lower case letter nodes and make the eliminations aka EURT nodes aka capital letter nodes that the singles nodes make apparent.

6. Check to see if we have either of the following three forcing conditions within any subset (all of a specific candidate in a row, column, or block, or all the candidates of a given cell):

All members are EURT aka have been eliminated. This is a contradiction and so the original guess is proven to be wrong. This means the original node, our trial, can be eliminated, as we have found an error.
Two members are ESLAF aka known to be the only true node. This is a contradiction, since only one node in any given subset can be true. The orginal guess must be incorrect and so the original node can be eliminated.
All but one member has been labeled EURT aka eliminated. The remaining member now must be true (it's a single) and so can be labeled ESLAF. This is not a contradiction, but does allow more eliminations.

If either ofthe first two of these is the case, we are done. The hypothesis is proven and the node can be eliminated.

If it's the third possibility we have a new ESLAF node to work with. We mark all other nodes in its subsets with capitals aka eliminate them.

Bob Hanson · Posted: Sat Nov 05, 2005 4:03 am Post subject:

Right, as funny as that sounds, (it is really very clever!!), I think it is correct, and illustrates that the process should work forward or backward.

My introduction to this was from Nick70, who was illustrating how "forward bifuraction" is equivalent to "direct, reverse logic". What you have shown here, I think, is that bifurcation really is not necessary. If you follow the forward logic and, in particular, include that last step 6.3, then it is quite possible that the same result for "hypothesis and disproof" (what we have here) will arise as for "hypothesis and proof" (what Sudoku Assistant currently does).

It would be helpful to all, I think, to write that out again without all the dardkcab ffuts. Because I think it is really very important for the forward-logic-chain people to understand it.

To be fair, the "forward logic" can be seen as:

1. Hypothesis that a node can be eliminated.
2. Propose that it is instead NOT eliminated ("TRUE").
3. Prove that this is not possible, thus proving the hypothesis.

and the "reverse" then is:

1. Hypothesize that a node can be eliminated.
2. Prove that this is necessary, thus proving the hypothesis.

So, sure, it's all the same principle. (Logic!)

It would be great if someone took Sudoku Assistant and added this forward logic. It shouldn't be too hard to do. Then we could have a fun comparison.

The only real difference is that the forward-direct logic described here ends up finding contradictions, and the reverse-directed logic used by Sudoku Assistant finds truths directly. But in either case the conclusion is either "node X can be eliminated" or "I don't know."

What the above shows, if it bears out in solving Sudokus, is that bifurcation APPEARS to be unnecessary, particularly with Step 6.3. That's the key step, either forward or backward. I suspect those doing bifuraction have not considered this key step.

I find it particularly interesting that we can solve all 520 "impossible 520" and all 95 "top95" puzzles using the reverse logic ALONE and starting SPECIFICALLY with only a small subset of the nodes (the weakly assocated non-chain nodes, to be exact). They do not have to be tested for "Is this node TRUE" only "can this node be eliminated."

This works mostly because this is the set of nodes that are specifically forced FALSE by strong chains. (They are the highlighted nodes on Glenn Fowler's page, though there he is highlighting cells, not marks. This would be akin to highlighting just the mark, not the whole cell.

I don't know that that is true of the forward direction. Can anyone at least demonstrate that? Which nodes would they be? My suspicion is that they would be a complementary set. Perhaps the real optimization is achieved by selecting a direction based on the number of nodes involved.

The "Medusa" idea in 3D or the X-cycles/Y-cycles business in 2D takes the forward steps through step 6.2, I think. That's the "standard" treatment.

Step 6.3 is the key, then, in either direction.

Nice work!
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Sat Nov 05, 2005 12:30 pm Post subject:

OK, that's done. Forward logic wins the day.

http://www.stolaf.edu/people/hansonr/sudoku

can be set to forward "disproof" or reverse "proof"

Of course, any forcing chain forward

T-->--F--T-->--F

etc. is identical to

F--<--T--F--<--T

so these methods are, in fact, identical.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr