Vidar's Monster #3

Advanced methods and approaches for solving Sudoku puzzles

Postby tarek » Mon Feb 20, 2006 1:26 pm

ronk wrote:[r4c5]-3-(UR:[r4c9]=3|7=[r4c7])-7-(ALS:[r4c4]=7|3=[r46c4])-3-[r4c5] implying r4c5<>3


Interesting, I must confess that I haven't thought about it this way:D
User avatar
tarek
 
Posts: 2608
Joined: 05 January 2006

Postby vidarino » Mon Feb 20, 2006 1:33 pm

ronk wrote:
vidarino wrote:I'm just going to give this one a bump back on track... Any other takers on solving it, except tarek (thanks!)?:)

Sorry I got off-topic there asking gsf about his solver. Actually thought about starting a thread, but figured that would be a bit presumptuous.


No worries, if you look back I even helped bringing the thread off-topic myself. ;)

Just as I was about to give up, I noticed a Unique Rectangle and Almost Locked set at this point ...


Nice one!:)

This is exactly why I ask for humans to try to solve the puzzles. There's no flopping way in heck I'll be able to program my solver to use tricks like that.:)

(My solver does break it, though, but only with the help of no less than 27 forcing chains and nets of various lengths and implication sizes. (Basically pure guesswork with limited look-ahead.) Far from an optimal solution anyhow.)

(Edit: Oops, seems ronk solved another puzzle instead of this one. I'm letting the comment stand, because it was a very clever solution.:) )

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Postby ronk » Mon Feb 20, 2006 2:06 pm

vidarino wrote:Nice one!:)

This is exactly why I ask for humans to try to solve the puzzles. There's no flopping way in heck I'll be able to program my solver to use tricks like that.:)


Thanks, but unfortunately that was Henk's puzzle on the Programmers Forum. (I put a link in my earlier post.) I guess now I'm obligated to work some more on yours.:)

Hoping the rest of the day goes better, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby tarek » Mon Feb 20, 2006 2:15 pm

I just noticed ronk's note about solving another puzzle:D

basically my solver at this stage gets stumped.......

Code: Select all
*--------------------------------------------------------------------------*
| 5       1269    1369   | 8       1237    27     | 4       3679    1379   |
| 12346   8       136    | 234     9       247    | 1367    5       137    |
| 134     19      7      | 5       134     6      | 139     8       2      |
|------------------------+------------------------+------------------------|
| 1278    1257    4      | 29      278     3      | 12579   279     6      |
| 1267    3       1568   | 2469    2467    245789 | 1279    2479    15789  |
| 9       267     568    | 1       2467    24578  | 237     2347    3578   |
|------------------------+------------------------+------------------------|
| 136     169     13569  | 7       2346    249    | 8       2369    359    |
| 367     4       3689   | 2369    5       289    | 23679   1       379    |
| 3678    5679    2      | 369     368     1      | 35679   3679    4      |
*--------------------------------------------------------------------------*


As my solver stops looking for chains (if they have more than singles in a node), it had to guess 6 times before finding some easier stuff to do......

6 simple guesses (1 look ahed with singles), I didn't go for the magic cell, staying with going for the "The cell that will generate the simplest cascade if it had a contradiction", If I attacked the grid with a "Deep" guess, then it would have a simpler cascade to follow as there are several bivalued cells around at this level. My solver opted for the longer solution !

Tarek
User avatar
tarek
 
Posts: 2608
Joined: 05 January 2006

Postby Graeme » Wed Feb 22, 2006 10:51 am

My solver solved this without needing to resort to brute-force trial & error, *however*, it did use a technique I've called Error Chains, which work like forcing chains in reverse, that are IMHO easier to spot for humans in *some* circumstances. I also needed to set the guess impliction to use hidden singles as well as naked-singles.

The solver also used regular hidden singles, block/line reduction, naked subsets and x-wing.

I'm happy to post the solve log if anyone's interested.
Graeme
 
Posts: 18
Joined: 06 February 2006

Postby ronk » Wed Feb 22, 2006 11:43 am

Graeme wrote:My solver solved this without needing to resort to brute-force trial & error [edit: .................] I also needed to set the guess impliction to use hidden singles as well as naked-singles.

Since neither uses logic to make a deduction, I see little difference between "a guessing implication" and "trial & error".

Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Graeme » Wed Feb 22, 2006 12:11 pm

I agree, and don't want to restart the T&E debate. Error Chains are like Nishio, Forcing Chains and other related techniques that test the implications of candidate guesses in a single cell. I think this is called single-level backtracking, or something similar around here.

My point was that the solver did not need to use brute force trial & error (unlimited guesses until a solution is found).

Hope that makes sense:)
Graeme
 
Posts: 18
Joined: 06 February 2006

Postby maria45 » Wed Jul 26, 2006 3:07 pm

Hello Vidar,
vidarino wrote:I'm just going to give this one a bump back on track... Any other takers on solving it, except tarek (thanks!)?:)


my solution:

dk15=8 > eh1!=8, ef5!=8
dk27=5 > fg2!=5, ef7!=5

b1=4, (a2=2, a6=7, b6=2, c5=5, b4=3, a5=1, g6=4, e4=4, f8=4
b3=1 or b3=6, f36=58, e9=8, b9=1 > b7!=1
f3=6 or f3!=6, f36=58, e9=8, b9=1, b2=6 > aegh3!=6, a8=6, b7=7, b9=1, b3=6, f36=58, e9=8, f6=8, e6=5, f3=5, e3=1, d2=7, d48=29, d5=8 contradiction to f6=8 >) b1!=4, c1=4

b4=3, (b6=4, g5=4, e4=4, f8=4, c5=1, b1=2, c2=9, c7=3, a3=3, f9=3, e9=8, g9=5, k2=5, d7=5, f36=58, ag2=16, f27=27, f5=6, ae5=27, d5=8, f6=5, f3=8, k1=8, k5=3, h6=8, e3=5, d1=1, e7=1, e1=6, g1=3, h1=7, h9=9, h3=6, h47=2 contradiction >) b4!=3, ac5=13, ab6=7

b4=4, ab6=27 or b6=4, g5=4, def5=2 > ef6!=2

e6=9, (d4=2, b4=4, g5=2, g6=4, f6=5, h6=8, k5=6, e4=6, d5=8, g8=6, b7=6, h1=6, cg2=19, h9=7, b39=13, b1=2, b6=7, a6=2, a2=6, f3=6, e3=8, f9=8, k48=39, k7=5, e9=5, k2=7, k1=8, g3=5, g1=3, h3=9, g2=1, c2=9, d2=5, f2=2, h4=3, k4=9, k8=3, g9=9, f7=3, c5=3, a5=1, a3=3, b3=1, b9=3, a9=0 contradiction >) e6!=9, de4=9

e4=6, d4=9 or e4!=6, hk4=6, k5=8, d458=279 > d7!=9

e4=9, (d4=2, b4=4, hk4=36, k5=8, d5=7, d8=9, h3=8, d1=8, d8=9, g5=2, h7=2, h6=9, g6=4, g9k7=59, k27=59, e1f2=27, ef3=6, b7=6, a2=6, cg2=19, k2=5, d2=1, cg2=9 contradiction >) e4!=9, d4=9

e4=6, (k4=3, h4=2, b4=4, g8=2, d8=7
h3=8 or h6=8, k5=6, k8=9, g6=9, h3=9 > h3=89
h8=9 or h8=6, g5=6, cg2=19 > k2!=9, k78=9
k2=5 or g3=5, g9=3, h9=7, h7=6, h1=3, b9=1, a9=9, c2=9, h3=9, k1=8, k2=7 > k2!=6
h1=6, h79=37, g9=5, d7=5, cg2=19, d2=2, d5=8, k5=6, g!=6 contradiction > h7=6, k8=9, a8=6, e8=4, f8=3, f7=2, bc7=3, k27=57
g5=6 or g5=4, f5=7, f2=6 > g2!=6, cg2=19, a2=2, a6=7, d2=5, d7=1, e7=9, c7=3, b7=7, b9=1, a9=9, c2=9, g2=1, k2=7, f2=6, f5=7, f6=4, e5=2, d5=8, d1=2, e1=7, e3=1, box1!=1 contradiction >) e4!=6, hk4=36, k5=8, h3=8, d1=8, ef6=58, d27=15, e1f2=27, ef3=6, a2b1=26, g7=1

a2=6 or b1=6, a8=6, g2=6 > k2!=6

k7=5, ef69=58 non-unique contradiction > k2=5, which solves the remaining numbers.

Greetings, Maria
maria45
 
Posts: 54
Joined: 23 October 2005

Previous

Return to Advanced solving techniques