Medusa + reverse logic solves all 520 of impossible.db

Bob Hanson

OK, I need a puzzle that Sudoku Assistant doesn't solve. Who's got it?

With

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

the entire set of 520 puzzles at

http://home.comcast.net/~mshelor/files/impossible.db

is solved in 50 minutes on my lab Gateway PC. (Averaging about 6 seconds each; Opera turns out to be an order of magnitude faster than MSIE here, by the way). This could be faster, but I figure that it's more fun to watch the solution go than try to get it very fast. JavaScript will never be very fast, anyway.

The two techniques, in addition to standard cross-hatching, block row/column exclusions, subsets, and grids that make this happen include:

Medusa:

Really just full 3D forcing chains -- no "bifurcation"

Hypothesis and Proof:

Postulating "X can be eliminated" followed by direct logical proof that this statement is true.

I think there's a puzzle out there that can stall this, but I just can't find it.
I wish someone would code this in a language that could process 200M of these so we could see what sticks.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

Have you tried the folowing famous puzzles?

Menneske 2155141

Lummox JR · Posted: Fri Nov 04, 2005 1:14 am Post subject:

My solver rates these fairly low. The infamous 48-unwind was already known to fall to one round of advanced coloring, but of the group Tilp's toughest is the only one that presents a big enough challenge to use bifurcating chains. Given that Bob's solver is using some form of that technique now, I doubt there's a puzzle it won't solve.

The puzzle example you got from my post is apparently not a uniqueness 3; it uses tests 2 and 4. Since it uses nothing more complex, my solver rates it with fairly low difficulty.

The sticking point with the last puzzle appears to be a quad in column 1. Kinda hard to find, but not impossible, and after that it hardly poses any challenge.

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

Menneske 2155141

http://www.stolaf.edu/people/hansonr/sudoku/index.htm?t-6t-4t-7t,,-3,-6tt,-9,-1,,-8tttt-5,,-1,-8t,-3t,-3,,-6,,-4,-5,,-4,,-2t,-6,,-9,,-3tt,,-2t,,-1

32 steps. The only interesting thing there is in Step 9:
13 strong chains
r3c7 ISN'T 3: strong incompatibility on 3 at cell r3c7 (involving nodes r3c7#3 chain 1(0) and r3c2#3 chain 1(0))

Rubylips 48-Unwind

http://www.stolaf.edu/people/hansonr/sudoku/index.htm?t,,-3,,-6ttt-1t-9,-7,-5t,-8tt-9,,-2t,,-8,,-7,,-4t,,-3,,-6tt-1t,-2,-8,-9t-4ttt-5,,-1

Again, nothing much there except

Step 10
18 strong chains
r4c8 ISN'T 7: strong incompatibility on 7 at cell r4c8 (involving nodes r4c8#7 chain 5(1) and r4c8#3 chain 5(1))

Tilps toughest

http://www.stolaf.edu/people/hansonr/sudoku/index.htm?t-1t-7t,-2,,-6,-9t,,-9t,,-3,,-8,-2tt,-4,-6,,-6,-4tt-5,-7,,-5,-8tt,-2,-1,,-8t,,-9t,,-1,-6,,-7t,-4t-2

This is more interesting. 49 steps required. Try it yourself and see. Too much interesting stuff to highlight here.

Uniqueness sample by Lummox JR, on the players forum. Requires test 3.

http://www.stolaf.edu/people/hansonr/sudoku/index.htm?,,-9ttt-5,,-6t-4,-7t-7,,-4,-9,,-1t,,-6t-2,,-5t-1,,-3t,-4,-6tttt,,-2,,-7,-3,-9t,-7,,-6tt-1t,,-8

22 steps. Only one interesting feature:

Step 14
28 cells left to solve
6 strong chains
r1c9 ISN'T 2: strong incompatibility on 2 at cell r1c9 (involving nodes r1c9#2 chain 1(0) and r1c4#2 chain 1(0))

One found at http://www.pmilne.net/SuDoku/

http://www.stolaf.edu/people/hansonr/sudoku/index.htm?ttt,-1,-7,-3t-8,-9t-4,-9,-8t-7,-2tt,,-2,-5,-6t,-4,,-5t,-5,-7,-3tt,,-6,-2t-3,-5,-8t-5,-1t-9,-4,-7

19 steps; nothing special of note.

Is it really possible that this is as hard as they get?
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

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

try 16*16 then !

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

nah, just the same only bigger, I'm sure.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Ruud · Site Admin

With the current speed of Sudoku Assistant, trying 16x16 might not be a good idea.

O(9^4) = 6561
O(16^4) = 65536

(I think)

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

that would be only a factor of 10 !
It's NP-complete, so expect exponential behaviour.
Or you can't solve even averagel puzzles.

xyzzy · Posted: Sun Nov 06, 2005 3:16 pm Post subject:

Bob Hanson · Posted: Tue Nov 08, 2005 10:02 pm Post subject:

xyzzy · Posted: Fri Nov 11, 2005 2:26 am Post subject:

Bob Hanson · Posted: Fri Nov 11, 2005 2:41 pm Post subject:

prior to this you've checked for all X-wing-like objects?
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

xyzzy · Posted: Fri Nov 11, 2005 10:16 pm Post subject:

Yes, there should be no locked tuples in any dimension than result in eliminations.

Bob Hanson · Posted: Fri Nov 11, 2005 10:43 pm Post subject:

yes, but I mean ALL objects of that nature, not just tuples? Just the general class of objects that "transcend" strong edges. Once those are gone, I would think the rest is cleanup.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

Bob Hanson · Posted: Mon Nov 14, 2005 7:40 pm Post subject:

Thanks for this example. It got me thinking more about what the
Sudoku Assistant is doing. I've added more discussion there.

Yes, I agree that (mostly) what this is is a breadth ONLY strategy. The one added technique, {?FFF...} --> {TFFF...}, is actually just the first step of a second-pass depth-like strategy. It amounts to looking for hidden singles.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr