Medusa + reverse logic solves all 95 of top95

Bob Hanson

It's true! Check it out yourself

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

select "number block input"
select "top95"

select "full" analysis (on the right)
check "Faster (don't show solver steps)"

select "automatic run"

The point of this is that straightforward logical analysis does indeed crack all these hard Sudoku puzzles. No "magic cells", no "n-constraints".

The analysis that finally cracked them was introduced by nick70, to whom I am grateful. I modified his analysis in the following way:

1) We are asking the question "Is this cell NOT X?" rather than "Is this cell X?"

2) We are looking primarily at strong chains, not just individual cells, because once the question is answered for any one node of a strong chain, it is answered for all members of that chain. Weakly associated nodes are also included. No other nodes need be considered.

The key aspect of the analysis are that it works backward to the question "Is Cell [m,n] NOT X?". The hypothesis is true if cells x,y,z are ....; cells xyz are .... if cells ... are NOT ....; cells ... ar NOT if cells ... ARE ... .... and so forth until a logical inconsistency is found.

No guessing, no backtracking (I think) -- or is this backtracking?

But I suspect that a forward-directed logic would do as well.

So, I guess I'm looking now for valid Sudoku puzzles that Sudoku Assistant cannot crack.

Thanks in advance.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

xyzzy · Posted: Tue Nov 01, 2005 9:50 pm Post subject:

Bob Hanson · Posted: Tue Nov 01, 2005 10:04 pm Post subject:

You're right. I said that wrong. This method does not find logical inconsistencies the way I said that. What it finds are proofs. It can't "disprove" -- the way a "trial" followed by an "error" can. I should have said:

The key aspect of the analysis are that it works backward to the question "Is Cell [m,n] NOT X?". The hypothesis is true if cells x,y,z are ....; cells xyz are .... if cells ... are NOT ....; cells ... ar NOT if cells ... ARE ... .... and so forth until a proof is found or there are no more considerations to check.

Now, that's not "trial and error", right? Because there is a trial, but no error.

Maybe it would be better called "hypothesize and prove"

Maybe that's the key: forward forcing chains starting with "If A then ....." only generally succeed if the result is found to be something like "X and Y both have to be TRUE, and they can't both be true"

To me this seems different.

"hypothesis and proof"?

Maybe equally "logical"
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

Simes · Posted: Tue Nov 01, 2005 11:55 pm Post subject:

Bob Hanson · Posted: Tue Nov 01, 2005 11:58 pm Post subject:

good point. My introduction of the Medusa idea was initially as an integration of the "X-cycle" "Y-cycle" business. And in that regard we have success in realm 1. It is, in fact, the synthesis and direct generalization of those two concepts.

2. Is it faster? I don't know and, frankly, I don't care. But I wouldn't be surprised if it were. Depends upon whether other techniques reuse their information between steps. They probably do, as that would be the effecient thing to do. Sudoku Assistant just starts all over each step. Still, I'd be interested in someone coding this in a "real" language and seeing how it stacks up. I'm not up to that task.

3. This is really my interest, and it is really why I like the "hypothesis and proof" idea that Nick70 introduced and I implemented. With it, I think all sorts of common practical encounters in real human Sudokus puzzles can be easily described. Show me an XY-wing or a Y-cycle, and I will show you all sorts of variations on the theme that are understandable in terms of small, simple strong chains and weakly associated nodes.

In any case, even if all methods of proof are logical, some are more "elegant" and some are clearly more "brute force." Sometimes brute force is the fastest way to get a job done. No doubt about it. But I would argue, as a professor, that there isn't that much to be learned from brute force. OK, so you have the solution....

Anyway, I think I understand how it works now. And that was really all I was after in the first place a few weeks ago when I started in on this.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

xyzzy · Posted: Wed Nov 02, 2005 1:03 am Post subject:

You can describe trial and error as choosing a hypothesis, assuming it is true, and then seeing if with that assumption the puzzle can be solved, in which case the hypothesis is true, or a contradiction is found, in which case the hypothesis is false. If neither is found, then nothing can be said about the hypothesis.

Of course you can do the opposite, assume the null hypothesis is true (null hypothesis = opposite of hypothesis), if a solution is found then the hypothesis is false, if a contradiction is found then the hypothesis is true.

I think this is generalization of every logic technique. Which is to say, every logic technique is just this process with certain restrictions placed on it.

For instance, naked singles. Suppose we find that cell 1,2 is 3 via a naked single. The hypothesis was "cell 1,2 is 3". We prove this by assuming the null hypothesis, "cell 1,2 is not 3". If no possible values remain, then we can reject the null hypothesis, which proves "cell 1,2 must be 3". The only way we are allowed to check for a contradiction is by checking if no possible values remain for the cell.

Every logic technique is just a way of placing restrictions on what you are allowed to choose for a hypothesis, what you are allowed to do when searching for a contradiction or solution, and if both contradictions and solutions are allowed as proofs/disproofs or just one with the other considered to prove/disprove nothing.

Sometimes the restrictions on what can be done to prove/disprove the hypothesis make the proof much faster. The restrictions on what can be a hypothesis sometimes limit what need be done to find a proof or disproof, thus making it faster.

Lummox JR · Posted: Wed Nov 02, 2005 4:09 am Post subject:

My solver also solves all the top95. The only advanced techniques it needs beyond coloring are advanced coloring (multiple digits) which I believe is equivalent to your Medusa analysis, and bifurcating implication chains.

Bob Hanson · Posted: Thu Nov 03, 2005 5:12 am Post subject:

yes, I think these probably amount to the same. I did see that except for some block exclusion, nothing more than the strong chain/weak link (amounting to forward nonbifurcating implications) along with the "hypothesis and proof" reverse logic elimination does the job. But because I'm interested in illustrating human methods, the rest is there as well.

Have you found other puzzles, then, that stump this strategy?

take a look at the logic analysis http://www.stolaf.edu/people/hansonr/sudoku is now generating. No bifurcation needed, I think, because it uses the reverse "proof" rather than "disproof" logic introduced by Nick70. After solving the "Proof" example, look down the list and click on one of the "Table" links. You should (maybe not on some machines) get a popup table describing the logic in detail.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr