Sudoku truths from Sudoku Assistant

Bob Hanson

Sudoku Assistant

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

This web-based JavaScript application now clearly demonstrates that:

--There is absolutely no difference in using forward vs. reverse logic.

--There is no particular need for "bifurcation".

--There is no particular need for "uniqueness tests".

--There is no particular need for "block row/column exclusion".

--X-wings, swordfish, hidden and naked ntuples are simply
different manifestations of the same thing -- namely, 2D subsets.

--Subset analysis IS required for general Sudoku solution using either
forward-directed ("This cell cannot be eliminated.")
or reverse ("This cell can be eliminated.") logic and is, in fact,
a form of logical bifurcation.

--There is no such thing as a "magic cell" except in the context of
whatever algorithm you happen to be using.

--The key to transcending "force chain logic" is to recognize when all
except ONE of a particular row, column, block, or cell are accounted
for. In that case, in a forward logic sense, if N-1 are FALSE the last
can be assigned TRUE, and we are off and running again. This is the
key component that removes the need for bifurcation.

--When doing this analysis, one need not test every node ("mark").
One simply needs to focus on the weak nodes and their associated
strong chains.

--The "Medusa" idea (3D strong chains) is simply a method of speeding
the overall solution process so that only two nodes in any particular
strong chain has to be tested, and so that nodes not directly
associated with a strong chain can be identified and ignored.

--recursive programming techniques fit such analyses well.

While it has only solved about 1500 puzzles, I cannot seem to find a puzzle the Sudoku Assistant cannot solve and am reasonably confident that the full 3D strong chain+weakly associated node+hypothesis is
in fact a complete system for solving nxn Sudoku.

I would very much like to find a puzzle that the Sudoku Assistant cannot solve, but I'm a bit skeptical now of that possibility.

Thanks again for all the great input from this forum.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

dukuso · Posted: Sat Nov 05, 2005 1:36 pm Post subject:

but if you want it to be taken serious, you'll have to
talk about its speed earlier or later.
I mean, without speed constraints I can do almost anything....

xyzzy · Posted: Sat Nov 05, 2005 4:18 pm Post subject:

But we already know trial and error can find all solutions without need for other techniques....

Bob Hanson · Posted: Sat Nov 05, 2005 8:22 pm Post subject:

sure. That's for the speed demons to work on. If this is trial and error, then so be it. I like the "reverse" logic because it is trial but no "error". It hones in on a specific proof. As with all proofs, there are generally different ways to get to the same solution. What it does NOT do is randomly select nodes, run the puzzle, and see what happens. It's very systematic, and it specifically chooses (a) just the weak nodes and (b) the strong chains as just TWO possibilities -- I think that's probably new here -- the consideration of all members of a chain or linked strong chain system as one "object" for testing. I know that when I turned that off, it went dreadfully slowly. So I know that it's important for speed. I think anyone who is using forced chain logic should consider doing this.

But the value is not that it can solve the puzzles fast. The value is that it is UNDERSTANDABLE and APPLICABLE to essentially any explanation desired. Show me a neat human device for solving Sudoku, and I'll show you the logical equivalent that explains why it works. THAT I think is the value here -- in the explanation of various devices -- XY-wings, XYZ-wings, I suspect in uniqueness tests, but I haven't seen an actual implementation of that yet.

As for trial and error. This is much more fundamental than trial and error. Or, to put it another way, this provides the rules for trial and error.

My understanding of trial and error -- correct me if I am wrong -- is that you pick a value, run with it until you either get stuck or there is an error. (So far the same, in a way.) If you get an error, you know something. If you don't get an error, do you then now try another value starting at that interim point, branching out as needed to try this and that? If so, then this is NOT trial and error. Each "trial" is done once. There is no branching, no further testing. Explore the consequences and go on.

Speed. I'm not interested in testing this. My suspicion is that if I can do this in the slowest language ever written -- JavaScript -- then if someone implemented this in C++, it would really fly. I could be wrong. Maybe just guessing is the way to go there.

What I'm interested in now is how the technique can be used to explain truly human devices. I think it has lots of potential there as an interactive learning tool.

In addition, it's interesting that all this can be displayed in simple -- ok, maybe not so SIMPLE -- table format that anyone familiar with such can understand if it's not TOO complex an example. I've highlighted some of the monsters, but most only go to AaBbCcDd or so, and they are perfectly understandable when you see the table format and read through the few lines of logical output.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

xyzzy · Posted: Sun Nov 06, 2005 1:07 am Post subject:

Bob Hanson · Posted: Sun Nov 06, 2005 12:00 pm Post subject:

dukuso · Posted: Sun Nov 06, 2005 1:29 pm Post subject:

another indication of "trial and error" could be whether
you get the same timing, same technics when you
solve an equivalent transformation of the puzzle.

xyzzy · Posted: Sun Nov 06, 2005 2:00 pm Post subject:

xyzzy · Posted: Sun Nov 06, 2005 2:13 pm Post subject:

Bob Hanson · Posted: Sun Nov 06, 2005 2:18 pm Post subject:

As I've said, the forward and reverse techniques lead to an identical result. I think we are in agreement there. It is simply interesting (to me at least) that you can work the logic both ways, and think of finding a logical inconsistency as finding a "verity" (I think it is called). I'm convinced the forward direction is easier to grasp and to see. When the reverse method was introduced here recently, in the context of bifurcation, it was thought it might be something new. My result of doing both in Sudoku Assistant demonstrates clearly that they produce identical results. The logic is precisely, as you say, the same.

forward logic ---> logical inconsistencies
forward logic + bifurcation --> verities

reverse logic ---> verities
reverse logic + bifurcation --> logical inconsistencies

That's all I'm saying.

Essentially, I'm done with the "reverse logic" idea now. I like the forward idea better EXCEPT for the minor play with words that you have to find "errors" that way. Then it "sounds" more like "trial and error", which some people seem to disparage. If someone says, "Well, your forcing chain idea is just trial and error," you can simply say that it can also be thought of strictly in terms of finding "verities" as well, using Nick70s "reverse logic" technique. Then there are "trials" but no "errors". As you say, it's all the same.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Sun Nov 06, 2005 5:40 pm Post subject:

sorry about the double post -- I didn't have time earlier to finish.

Ruud · Site Admin

Here's an approach to saving strong chains "on the fly":

Each time a candidate is eliminated, you probably want to check if that elimination caused a single. For this you need to maintain counters for # candidates left in the cell, and for # cells available for that digit in the row, column and box the cell belongs to.

When any of these counters reach 0, the puzzle has no solution.

When any of these counters reach 1, you found a single, and you can eliminate all competing candidates on the >1 counters.

When any of these counters reach 2, you found a strong link. If one of the 2 linked candidates already has a chain-ID, assign it to the other one. If none of them has a chain-ID, create a new one. If both have a different chain-ID, replace one of them, effectively combining them into one large chain.

The previous is probably something you already do in the Medusa routine, so it would not be to big a change to move that to "candidate elimination" routine.

It may look like all this maintenance would decrease your performance, but it is only executed when any counter reaches 2, which can happen only 256 times in a sudoku with 17 clues where every other cell has 2 candidates left, and each digit has 2 cells left in each house (I would be very interested to see that happen)

Linked lists in stead of counters are even better, but a little more complicated to implement.

Ruud.

Bob Hanson · Posted: Sun Nov 06, 2005 7:16 pm Post subject:

Ruud,

Bob Hanson

Dead End, but not really: Demonstration that any logical chain analysis is just trial and error and that "bifurcation" is just the beginning

See also: http://www.stolaf.edu/people/hansonr/sudoku/deadend.htm

The purpose of this posting is to demonstrate that

a) logical chain analysis including a step for checking for hidden singles does solve *just about* any 9x9 Sudoku.

b) "bifurcation" tabling logic, as presented in http://www.setbb.com/phpbb/viewtopic.php?t=300&mforum=sudoku
is equivalent to a "second pass" depth-search trial and error strategy.

Shown below is the configuration part way through the Sudoku Assistant analysis
of a puzzle from the top95 collection: