Solution to dml #4

Advanced methods and approaches for solving Sudoku puzzles

Solution to dml #4

Postby gurth » Thu Dec 14, 2006 10:33 am

Solution to dml #4

EMERGING STRATEGIES

Often one finds a more or less complete conjugate chain of 5-candidates. (Replace 5 by x if you want to be more general.) Two 5-candidates per unit. Half of them are true, and half false.

Using the method of contradiction (as opposed to what is called guesswork) we may not DIRECTLY test the true candidates: only the false. The reason is obvious: testing the true 5s cannot lead to a contradiction.

Here is the rub: experience bears out that in more than 90% of cases, testing the true 5s directly (which can't lead to a contradiction, and so may not be done) DOES usually lead to many more results (eliminations and placings) than testing the false 5s.

The obvious and most direct approach would be to take a false 5 and show it leads to a contradiction. This would then immediately place all the true 5s. Unfortunately, testing a false 5 usually leads to almost nothing, and very little success.

THERE IS A WAY AROUND THIS DIFFICULTY. A way to exploit the fact that placing TRUE 5s leads to many results:

Test some false candidate that forces all the true 5s to be placed! Such a candidate is any false candidate in the same cell as a false 5! Call it Candy. Assuming Candy, all the true 5s are immediately placed, with many results, leading easily (in comparison to other tactics) to a contradiction. Thus all candidates Candy are sitting ducks, eady and ripe for speedy elimination.

So, once you have fashioned that nice conjugate chain of 5s (or x's), or even before, start eliminating Candies, and don't stop until you have done them all.

This is exactly the technique I used almost exclusively on dml #4, and mostly on dml #3 before that.


Code: Select all
dml #4 : SR 10.6, gsfr 99961
 *-----------*
 |8..|..3|...|
 |.7.|.6.|.9.|
 |..4|5..|...|
 |---+---+---|
 |..2|...|..4|
 |.3.|..1|.7.|
 |5..|...|8..|
 |---+---+---|
 |...|..9|..1|
 |.6.|.7.|.3.|
 |...|2..|5..|
 *-----------*   


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) ... (Right now my strategy is already clearcut: I will create one conjugate chain of all the 5s, and create bivalues in all the "wrong" 5-cells in that chain: starting with g2.)

(2) ?4g2... (?2h0...??)-2h9, (?2h7...??)-2h7... (?7g7...??)-7g7... (?2a8...??)-2a8...?? -4g2.

(3) ?2g2... (?4f4...??)-4f4, (?4f5...??)-4f5, (?4f6... ((?6k8...))-6k8...??)-4f6... (?6k8...??)-6k8...?? -2g2...

(4) ?5a9... (?8d4...??)-8d4, (?8d6...??)-8d6, (?8d5...??)-8d5...?? -5a9.

(5) ?1a8...?? -1a8.

(6) ?2a8...?? -2a8.

(7) ?6a8...?? -6a8.

(8) ?5a3...?? -5a3.

(9) ?3b3...?? -3b3...

(10) ?6e9...?? -6e9. (a short step).

(11) ?9e9...?? -9e9. (a short step).

(12) ?3d5...?? -3d5. (singles only in this step).

(13) ?9d5...?? -9d5. (singles only in this step).

At this point I have reached my first aims stated above. The next thing is two steps to force one of those not-5 bivalues (here 45a8) to become true, by eliminating the other two 4s in the column). There shouldn't be much left to do after that.

(14) ?4k8... (?7c7...??)-7c7... (?7d4...??)-7d4, (?7d6...??)-7d6...?? -4k8.

(15) ?4g8 (I'm hoping this might be the last step! as everything is set up for a kill) ...(?7c7... ((?7d1...??))-7d1...??)-7c7, (?7d4...??)-7d4, (?7d6... ((?3b1...??))-3b1...??)-7d6... (?7g3...??)-7g3... (?7f4...??)-7f4...?? -4g8...59 singles to End.

Notice that all my net steps, 2 to 14, did not solve a single cell. All cells were solved consecutively as singles at the very end.

PS My solution to dml#2 is now also complete, and posted on a new thread. It is very much a follow on from this, as the two puzzles are very similar.
_____________________________________________________________________________
gurth
 
Posts: 358
Joined: 11 February 2006
Location: Cape Town, South Africa

Postby leon1789 » Thu Dec 14, 2006 5:20 pm

It's impossible to solve this puzzle with this method :
studies on bivalue cells and bilocation numbers in contradiction nets and subnets using singles and locked sets !:!::(:(
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby ravel » Thu Dec 14, 2006 7:33 pm

leon1789 wrote::(:(
Why:( ? I am glad to know a first one:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby leon1789 » Thu Dec 14, 2006 7:49 pm

ravel wrote:
leon1789 wrote::(:(
Why:( ? I am glad to know a first one:)

I thought that all puzzles were soluble with this method...:(:!:
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby StrmCkr » Fri Dec 15, 2006 7:39 am

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

Postby leon1789 » Fri Dec 15, 2006 9:28 am

An other method : studies on bivalue cells and bilocation numbers in contradiction nets and subnets, using elementary methods. Here, elementary methods are singles, locked sets, box/line reductions.

Code: Select all
   123 456 789
  *-----------*
a |8..|..3|...|
b |.7.|.6.|.9.|
c |..4|5..|...|
  |---+---+---|
d |..2|...|..4|
e |.3.|..1|.7.|
f |5..|...|8..|
  |---+---+---|
g |...|..9|..1|
h |.6.|.7.|.3.|
k |...|2..|5..|
  *-----------*


Notation : C#z means -zC is proved, because C=z is a move that will be disproved by contradiction using elementary methods. Moreover, "bold" results are definitively true.

1) g5#5,

2) now, if d2=8 then f2#4, g2#4, e5#8, c5#8, and contradiction using elementary methods,
so -8d2,

3) now, if c1=6 then h3#1, and contradiction using elementary methods,
so -6c1,

4) now e1#4,
5) f3#1,
6) e5#4,
7) e9#5,
8) d1#7,
9) b3#5,
10) c6#2,
11) b3#3, and finish with elementary methods.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby gsf » Fri Dec 15, 2006 11:53 am

leon1789 wrote:Here, elementary methods are singles, locked sets, box/line reductions.

1) g5#5,

2) now, if d2=8 then f2#4, g2#4, e5#8, c5#8, and contradiction using elementary methods,
so -8d2,

how does d2=8 (r4c2=8) lead to f2#4 (r6c2<>4) using elementary methods?
are you nesting if then?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby StrmCkr » Fri Dec 15, 2006 12:49 pm

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

Postby leon1789 » Fri Dec 15, 2006 2:31 pm

gsf wrote:
leon1789 wrote:Here, elementary methods are singles, locked sets, box/line reductions.

C#z means (...) C=z is a move that will be disproved by contradiction using elementary methods.

1) g5#5,

2) now, if d2=8 then f2#4, g2#4, e5#8, c5#8, and contradiction using elementary methods,
so -8d2,

how does d2=8 (r4c2=8) lead to f2#4 (r6c2<>4) using elementary methods?
are you nesting if then?

-5g5 is proved. (sorry for this coordinates, but it's shorter than r7c5<>5 , isn't it?)

Now, "d2=8 and f2=4" lead to a contradiction (using singles, locked sets, and reductions) so : if d2=8 then f2#4...
Do you want that I explain all stages to prove "d2=8 and f2=4" lead to a contradiction?
...Perhaps, we have different definitions of "reduction" of box/line?
Last edited by leon1789 on Fri Dec 15, 2006 10:40 am, edited 1 time in total.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby ravel » Fri Dec 15, 2006 2:37 pm

gsf wrote:how does d2=8 (r4c2=8) lead to f2#4 (r6c2<>4) using elementary methods?
are you nesting if then?
f2#4 is a subnet leading to a contradiction, given that d2=8. After that 4 can be eliminated from f2 and the forcing net for d2=8 is continued with elementary methods and the next subnet, until it leads to a contradiction itself.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby leon1789 » Fri Dec 15, 2006 2:44 pm

thanks ravel:D
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby gsf » Fri Dec 15, 2006 3:26 pm

ravel wrote:
gsf wrote:how does d2=8 (r4c2=8) lead to f2#4 (r6c2<>4) using elementary methods?
are you nesting if then?
f2#4 is a subnet leading to a contradiction, given that d2=8. After that 4 can be eliminated from f2 and the forcing net for d2=8 is continued with elementary methods and the next subnet, until it leads to a contradiction itself.

wait a second
there's no forcing nets in elementary methods are singles, locked sets, box/line reductions

I take the technique statement to mean:
method wrote:make a guess on a bivalue/bilocation cell and then use the elementary techniques to find contradictions


can you elaborate on this to explain what's really going on
thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby ronk » Fri Dec 15, 2006 3:43 pm

leon1789 wrote:1) g5#5,

2) now, if d2=8 then f2#4, g2#4, e5#8, c5#8, and contradiction using elementary methods,
so -8d2,

So contradiction effectively is g5#8 ... meaning no digit 8 can be placed in column 5?

So using a little bit of psuedo-code we have ...
Code: Select all
d2=8;
if (f2=4 contradictory) {
  f2<>4;
  if (g2=4 contradictory) {
    g2<>4;
    if (e5=8 contradictory) {
      e5<>8;
      if (c5=8 contradictory) {
        c5<>8;
        if (g5=8 contradictory) {
          d2<>8 (g5 last possible location for 8 in col 5);
        } else {
          do something else;
        }
      } else {
        do something else;
      }
    } else {
      do something else;
    }
  } else {
    do something else;
  }
} else {
  do something else;
}

Typically, what would be the "do something else?"

What do you do if you stumble onto a magic cell?

Have you tried expressing the multiple inferences of this error net with implication streams?

Can this method be described by anything other than "brute force" or "guessing" or "trial & error?"
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby leon1789 » Fri Dec 15, 2006 4:37 pm

leon1789 wrote:C#z means (...) C=z is a move that will be disproved by contradiction using elementary methods. Here, elementary methods are singles, locked sets, box/line reductions.

2) now, if d2=8 then f2#4, g2#4, e5#8, c5#8, and contradiction using elementary methods,
so -8d2,


I prefer this code (thanks to gsf) :
Code: Select all
if d2=8
then
  use elementary methods for some trivial eliminations

  if f2=4
  then contradiction using elementary methods
  therefore f2<>4

  if g2=4
  then contradiction using elementary methods
  therefore g2<>4

  if e5=8
  then contradiction using elementary methods
  therefore e5<>8

  if c5=8
  then contradiction using elementary methods
  therefore c5<>8

  finally elementary methods lead to a contradiction
therefore d2<>8


make a guess on a bivalue/bilocation cell,
(then use elementary methods for some trivial eliminations)
and then make an other guess on a bivalue/bilocation cell
and then use the elementary techniques to find contradictions

ronk wrote:Can this method be described by anything other than "brute force" or "guessing" or "trial & error?"

I don't know
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby ravel » Fri Dec 15, 2006 11:33 pm

I would like to compare leons method with Mighty Mutant Jellyfish or other exotic patterns.
ronk wrote:Typically, what would be the "do something else?"
If you dont find such a fish, you would search for another one (and very likely with the little help of a program).
What do you do if you stumble onto a magic cell?
Ok, this cant happen when fishing. It is a matter of taste. It is a good argument (and i think gsf's POV), that it is allowed to use it, when it is easier to find it than to eliminate any other candidate.
Have you tried expressing the multiple inferences of this error net with implication streams?
Have you read many of Maria's or Carcul's solutions to very hard puzzles? Beside of the idea, which candidate to eliminate or which almost pattern to use and maybe one or 2 surprising parts in a chain (note that both of them used a kind of subnets) it is not very exciting. If you only want a detailed (but not optimized) proof, you can output all the following basic steps (until the first contradiction) by any solver that has implemented basics.
Can this method be described by anything other than "brute force" or "guessing" or "trial & error?"
You will not find an exotic fish without "trial & error". Another word for "brute force" would be patience. "guessing" for me is "trial & error" without a concept.
ravel
 
Posts: 998
Joined: 21 February 2006

Next

Return to Advanced solving techniques