Solution to dml #15

Advanced methods and approaches for solving Sudoku puzzles

Solution to dml #15

Postby gurth » Sat Dec 23, 2006 9:58 am

Solution to dml #15

Code: Select all
 *-----------*
 |..3|2..|...|
 |.4.|.9.|...|
 |6..|..8|.1.|
 |---+---+---|
 |2..|...|..3|
 |.1.|..6|.4.|
 |..7|...|5..|
 |---+---+---|
 |...|..1|..2|
 |.9.|.4.|.6.|
 |...|5..|7..|
 *-----------*   SE 10.7


Note: This solution is designed to be followed using the Simple Sudoku program.
"..." means proceed as far as SS allows, following the hints given by SS in the order given.
This will facilitate rapid checking of this solution.

"?" introduces a move that will be disproved by contradiction. (These moves are only introduced when SS grinds to a halt, saying "no hint available".) In order to "play" this move, you will have to turn off the "block invalid moves" feature of the program. Then insert the move and follow all hints given until you see a contradiction. Once you find the contradiction, you must retrace (withdraw in reverse order) all moves made since the disproved move, by clicking the "undo" arrow repeatedly. Then "correct" the disproved move. EG if this move was "?3f6", then REMOVE the 3 at f6, because you have proved the 3 at f6 false.

SOLUTION:

(1) ...

(2) ?1d5...?? -1d5.

(3) ?2c7... (?1h7...??)-1h7... (?6g5...??)-6g5, (?6g3... ((?9c9??))-9c9...??)-6g3, (?6d2...??)-6d2...?? -2c7.

(4) ?2f6... (?1f5...??)-1f5... (?1k9...??)-1k9... (?6a9... ((?9c7...??))-9c7...??)-6a9...?? -2f6...

(5) ?1h1... (?4d6...??)-4d6, (?4k1...??)-4k1...?? -1h1.

(6) ?6g2... (?3g4...??)-3g4, (?3g5...??)-3g5...?? -6g2.

(7) ?6b9...?? -6b9.

(8) ?6a9... (?4f1... ((?5a2...??))-5a2, ((?7c2...??))-7c2...??)-4f1... (?4k1... ((?8b7...??))-8b7... ((?9c7...??))-9c7...??)-4k1... (?9a1...??)-9a1...?? -6a9...

(9) ?1a1...?? -1a1...

(10) ?1b1, (?4f6...??)-4f6... (?4g3...??)-4g3... (?4c4...??)-4c4...?? -1b1...

(11) ?4k3... (?4c4...??)-4c4...?? -4k3...End.
______________________________________________________________________________________
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Postby RW » Tue Dec 26, 2006 11:04 am

Gurth, I know it's not very easy to find a solution like this and I'm aware that you probably put a lot of time into finding short solutions to these puzzles. However, applying numbers in SS to see if they lead to a contradiction is not a very revolutionary technique, it's called T&E and is probably the oldest trick in the book. My question is - does this technique deserve 24 own threads in the "Advanced Solving Techniques" forum? 24 threads that don't give any new ideas of how to use the technique, only lists candidates in hard puzzles that can be eliminated.

There's already almost a thousand threads here, finding the essential ones is hard enough without having the first two pages stuffed with puzzle solutions. As I said, I know you're doing a hard job that is of interest to people who want to study hard puzzles. But please, try to reconsider your way of posting the solutions. I tried to start a thread for solutions to ravels list a while ago, which apparently wasn't a hit, maybe you could start your own thread. That would keep them together, make them easier to find for people interested in them and it would leave some visibility in this forum for threads that actually are discussing advanced solving techniques.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ravel » Thu Dec 28, 2006 12:28 am

Thanks RW,
i now also can understand better Ron's POV. The times have changed. A half year ago the hardest have been solved on paper. But now programs can provide "shorter" solutions much faster. For the new hardest sudokus there have been published only program aided solutions. So i wonder, if a new hardest thread should not be started in the programmers forum.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby wapati » Thu Dec 28, 2006 12:58 am

RW wrote:Gurth, I know it's not very easy to find a solution like this and I'm aware that you probably put a lot of time into finding short solutions to these puzzles. However, applying numbers in SS to see if they lead to a contradiction is not a very revolutionary technique, it's called T&E and is probably the oldest trick in the book. ...........

RW


This is how I view forcing chains.

I would wlecome a GOOD suggestion that might let me think ForcingChains is not T&E.
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada

Postby gsf » Thu Dec 28, 2006 3:49 am

ravel wrote:Thanks RW,
i now also can understand better Ron's POV. The times have changed. A half year ago the hardest have been solved on paper. But now programs can provide "shorter" solutions much faster. For the new hardest sudokus there have been published only program aided solutions. So i wonder, if a new hardest thread should not be started in the programmers forum.

I know its the season of good will, but ...
the programmer's forum has regressed to a dlx wiki
or worse, help me do my project

the best algorithmic discourse seems to be here
even for the hardest, it will be algorithm concepts, and not raw compute power
or coding, that will advance sudoku
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Carcul » Thu Dec 28, 2006 8:04 pm

Ravel wrote:For the new hardest sudokus there have been published only program aided solutions.


As I said before, I solved Puzzle Dml1 only on paper.
The times have changed? Why? Perhaps only the way of thinking of some people have really changed.
And by the way, if one is supposed to solve those "hardest" Sudokus with the aid of a computer, why not do the same with the easiest ones?

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ronk » Thu Dec 28, 2006 8:54 pm

Carcul wrote:And by the way, if one is supposed to solve those "hardest" Sudokus with the aid of a computer, why not do the same with the easiest ones?

While many people do climb stairs to get to the 3rd floor, most will take an elevator to the 100th floor.:D
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Fri Dec 29, 2006 11:15 am

Carcul wrote:As I said before, I solved Puzzle Dml1 only on paper.
I never saw the solution.
The times have changed? Why?
Because the hardest known now are 2 classes harder than those a half year ago. The solving&rating programs needed an update to provide solutions for this generation. That means that solving techniques which were sufficient for the old ones are not enough to solve the recent hardest.
Can you give a "better" solution to "Ocean's Christmas present" than the one i found in about an hour with my programs help (posted in the hardest thread) ? Or can you solve the puzzles in the hardest list to tell us, which really are the hardest ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gurth » Sat Dec 30, 2006 9:55 am

Good points, ravel.

I suggest we not waste time pandering to the sentiment against Contradiction Nets, which is obviously the only technique advanced enough to cope with the ultras at this time. Let's get on with our work, leon and ravel, in developing these NEW techniques!
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Postby Myth Jellies » Sun Dec 31, 2006 9:10 pm

There is no NEW technique here. Guessing, Ariadne's thread, T&E, bifurcation, plug & play, brute force, error chains, or whatever you are currently calling it--contradiction chains--have been around and have been used to solve puzzles from the very start. Most everyone already knows that you can use tentative assumptions about the truth of candidates to solve every conceiveable sudoku. Not sure why you all missed the memo:) . Solutions found without ever assuming a candidate is true or false are the same as your solutions, so obviously they won't be better; however, I and many other solvers of logic problems object to your "tentative assumptions" as a means to an end. They are equivalent to guessing. While that may be an easier path to the solution, it is an unsatisfactory path to be taken only after you have given up on finding a non-assumptive path to the solution.

There is no guarantee that every 3x3 sudoku puzzle has a non-assumptive path to a solution, but there is no guarantee that there isn't either. Certainly all 2x2 sudokus can be solved non-assumptively. The number of 3x3 puzzles we can solve non-assumptively has increased a staggering amount over what it used to be, and it is rather reckless to claim that the current list of difficult puzzles will never be solved in such a fashion. That will only be the case if everyone gives up and uses tentative assumptions about candidates.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ravel » Tue Jan 02, 2007 5:49 pm

Oh well, i have heard some criticism now from people, who IMHO are not authorized for that, simply because they dont have any alternatives. Why dont you stay in your ivory tower, far away from the hardest sudokus ?

It is one thing to say, that those solutions should not be posted in more than one thread. This i can accept and also, that the better forum could be the General instead of the Advanced Techniques.

But i cannot accept this condemnation of using contradiction chains, found with more or less t&e, by people, who do nothing better: How are all the holy big fishes, AIC's or whatever found nowadays ? By intensive use of programs, written for that purpose. And what are the programs doing ? Pure t&e. That cannot be a question.

What are the "new techniques", that were found last year ? Kraken fish ? New UR types ? Combined ALS's ?
Take a well known pattern, add one or more numbers to make it "almost", combine it with a short chain and maybe another almost pattern and give the whole thing a name. That was, what i saw last year, not very revolutionary either, i think.
If i would try to find a good "new" pattern, i would search for the most common pattern of elimination chains with n cells and give it a name. I am sure, it would be more common and effective than those techniques.
The only real new technique i remember was "Gurth's symmetrical placement".

And dont forget, we are talking about really hard puzzles here. Not one in the hardest list has been solved with all the arsenal of extensions of sophisticated pattern oriented or non assumptive techniques. The first ones are simply too weak. And the latter ones ? I dont doubt, that each known puzzle can be solved with them. Just allow many AND's and OR's in your non assumptive chains and i am sure you can express each contradiction chain as a "good" one (it is the same thing as it was with the "good" forcing chains and the "bad" contradiction chains). Nothing but a matter of complexity. But who do you think would like to read such a solution ? It will not be much better readable than the computer output of a program, which calculates the solution in milliseconds with a simple t&e algorithm.

Now look at this:

Code: Select all
dml11
100050000006009000080200004040030008007000060900000100030800002000004050000010700
r4c4<>9(r2c9<>5,r3c1<>3,r5c7<>4),r4c3<>1,r9c8<>4,r5c1<>8(r2c9<>1,r1c9<>6,r5c4<>9,r4c1<>6),
r6c8<>3,r1c6<>8,r8c5<>2,r1c3<>4,r2c2<>2,r1c2<>9

dml12
003900000040070001600002000800000002070050030009000400200001008000040050000600900
r2c1<>5(r1c2<>2,r5c1<>1),r3c9<>3,r6c5<>2(r4c5<>6,r7c7<>6),r5c6<>4,
r3c8<>9(r6c5<>8,r2c6<>6,r3c4<>4,r1c2<>2),r1c2<>1

dml20
100050080000009003000200400004000900030000007800600050002800060500010000070004000
r3c1<>3(r2c1<>4,r7c2<>9,r6c5<>9,r7c7<>3,r2c7<>5,r1c4<>3),r3c1<>6,r3c1<>9(r2c1<>4,r7c2<>9,r1c7<>6),
r1c2<>4,r6c2<>1,r5c1<>9,r1c3<>9,r5c4<>5

Ocean's Christmas present for gsf
000001020300040500000600007002000006050030080400000900900002000080050400001700000
r2c2<>1(r3c8<>1,r2c6<>7,r7c2<>7),r2c3<>9,r4c2<>9(r6c2<>3,r1c7<>6),r5c9<>1,r8c9<>2,r3c2<>1,
r1c1<>7,r5c7<>2,r5c4<>1,r4c1<>7,r1c1<>5

Here you have 4 of the hardest known puzzles wtih a solution written in 2 lines only. You want to verify it ? Take a simple solver with basics implemented and you can do it in 15 minutes. You want to see the details graphically and optimized ? The Sudoku Explainer can show you.

Give me a better way to find and represent solutions and i will accept the criticism. And be sure that you might not need a new technique, but at least a new strategy to be able to find them.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Tue Jan 02, 2007 6:42 pm

ravel wrote:Ocean's Christmas present for gsf
000001020300040500000600007002000006050030080400000900900002000080050400001700000
r2c2<>1(r3c8<>1,r2c6<>7,r7c2<>7),r2c3<>9,r4c2<>9(r6c2<>3,r1c7<>6),r5c9<>1,r8c9<>2,r3c2<>1,
r1c1<>7,r5c7<>2,r5c4<>1,r4c1<>7,r1c1<>5
[/code]
Here you have 4 of the hardest known puzzles wtih a solution written in 2 lines only. You want to verify it ? Take a simple solver with basics implemented and you can do it in 15 minutes. You want to see the details graphically and optimized ? The Sudoku Explainer can show you.

Give me a better way to find and represent solutions and i will accept the criticism. And be sure that you might not need a new technique, but at least a new strategy to be able to find them.

I believe the discourse has been cordial to this point
and would like to see it stay that way

how is the above any different from just positing the solution grid?
granted, its smaller, but does it give any hint about how to approach the other hardest puzzles?
does it give any hint about how this one short solution could be determined out of the umpteen possible solutions?

Ocean's Christmas gift in particular requires 2 concurrent guesses to make any contradiction chain productive
how do you pick the first guess, and then the second, to know that a chain will be productive?
how many guesses did it take you to get to this short solution?
if you hit upon in at first glance then please tell how you did it
the lack of codifying where to start and how to proceed is the crux of the complaint(s) here
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Tue Jan 02, 2007 9:28 pm

removed
Last edited by StrmCkr on Sat Dec 13, 2014 6:30 am, edited 1 time in total.
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 841
Joined: 05 September 2006

Postby ravel » Tue Jan 02, 2007 11:12 pm

gsf wrote:how do you pick the first guess, and then the second, to know that a chain will be productive?
how many guesses did it take you to get to this short solution?

I progammed it this way:
I defined as a "node" the grid when stuck with basic methods.
1. Going through the nodes, look, which (wrong) numbers can be eliminated and which "progress" they would bring (where "progress" is the number of eliminations, that are possible, when the number can be eliminated).
2. If the progress is greater than 3 eliminations (chosen heartily), add the best (here i accepted those which were not worse than the 2nd best number of remaining candidates for this level = point number) to the nodes.
If the progress is less than 3 eliminations, search for subnets, add 3 points for the rating and add them to the nodes.

This way i found about 100 solutions with the final rating each time, mostly differing only in the last 2 steps, but sometimes with other subnets.

For the hardest i calculated subnets for about [edit] 65 grids.
ravel
 
Posts: 998
Joined: 21 February 2006


Return to Advanced solving techniques