Using almost locked set full grid example

Advanced methods and approaches for solving Sudoku puzzles

Using almost locked set full grid example

Postby bennys » Sat Oct 22, 2005 5:59 am

Image
bennys
 
Posts: 156
Joined: 28 September 2005

Postby Sue De Coq » Sat Oct 22, 2005 11:36 am

That's true (and clever) but, unfortunately, doesn't allow us to solve the puzzle. It would be interesting to see a puzzle that could not be solved were it not for this new technique.
Sue De Coq
 
Posts: 93
Joined: 01 April 2005

Postby Shazbot » Sat Oct 22, 2005 11:38 am

I don't understand this, but looking at the example I think it MAY help with a puzzle I'm stuck on at the moment.

Can someone tell me what is a locked set (and ALMOST locked set)? And if someone who understands what bennys is saying could please rephrase (almost-newbie here) so I can follow it better, I'd be very grateful.
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby stuartn » Sat Oct 22, 2005 11:46 am

and if Bennys could post it in the usual pastable format it would be most helpful!

stuartn
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby Sue De Coq » Sat Oct 22, 2005 11:51 am

HTH to clarify things:

The fact that 3 and 8 are candidates at Z means that we cannot have X=3 and Y=8. However, this is exactly what we would have if 2 and 5 were removed as candidates from X and Y. Note that if the cell r2c1 were to contain a 2 or a 5, r1c1 would have to contain a 5 or a 2 (i.e. the other one), whereupon we would be left with a contradiction. Therefore, r2c1 cannot contain a 2 or a 5.

Note that the candidates for r3c3 are 1 and 8. (Restrictions in Column 3 remove the seemingly plausible 2 as a candidate).

My solver has to revert to a forced chain in order to solver the published puzzle.
Sue De Coq
 
Posts: 93
Joined: 01 April 2005

Postby Shazbot » Sat Oct 22, 2005 12:05 pm

I guess it's hard to follow without seeing the rest of the candidates pencilled in. I don't follow the reasoning behind r3c3 <> 2, and wouldn't remove 2 and 5 from X and Y unless they were eliminated via a different method. Maybe this is a bit beyond me (and maybe THAT'S why I'm still stuck on that puzzle!)
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby Sue De Coq » Sat Oct 22, 2005 1:28 pm

Easy stuff first. Here's a copy of the puzzle that will fit on the screen for stuartn. The 'W' is my addition:

Code: Select all
 W 6 9 | 1 4 3 | 8 . 7
 . X 7 | 9 . . | . . 4
 4 Y . | 7 . . | . 9 3
-------+-------+------
 9 . . | 8 5 7 | 3 6 1
 7 Z . | 2 1 6 | 9 4 5
 6 1 5 | 3 9 4 | 2 7 8
-------+-------+------
 . 7 . | 5 8 9 | 4 1 .
 8 . . | 6 7 1 | 5 3 .
 . . . | 4 3 2 | 7 8 .


Here's solver log output that explains why 2 isn't a candidate for r3c3 and gives a forced chain that cracks the problem:

Code: Select all
The values 1, 3, 6 and 8 occupy the cells r3c3, r5c3, r7c3 and r9c3 in some order.
- The moves r3c3:=2 and r7c3:=2 have been eliminated.
Consider the chain r3c2-5-r3c6~8~r3c3-1-r9c3-1-r9c1-5-r9c2.
When the cell r3c2 contains the value 5, so does the cell r9c2 - a contradiction.
Therefore, the cell r3c2 cannot contain the value 5.


shazbot - 2 and 5 are removed from r2c1, not X and Y.

Now some chat. Here's a slightly more general way to look at the technique introduced by bennys. Note that since the values 2, 3, 5 and 8 fill the cells W, X, Y and Z, they form a disjoint subset (or quad). Normally, we only identify disjoint subsets that lie in a single sector and allow us to make immediate eliminations. However, even when no immediate eliminations are possible, disjoint subsets enforce useful restrictions. Consider the candidates 2 and 5 in Box 1. Were they to be placed anywhere other than in cells W, X and Y, we would no longer have four candidates with which to fill the disjoint subset {W,X,Y,Z}. On the other hand, the candidates 3 and 8 cannot immediately be eliminated from Box 1 because they are candidates for Z, which, crucially, lies outside Box 1.

The general rule here is 'Once a Disjoint Subset has been identified, the subset values should be removed as candidates from other cells in any sector that contains a subset cell, unless that subset value should occur in a subset cell outside of that sector'.

Does that make sense? It will give me something to code over the weekend!
Sue De Coq
 
Posts: 93
Joined: 01 April 2005

Postby bennys » Sat Oct 22, 2005 4:59 pm

i post it just to show how to make one step
However here is how we can continue
After some forced moves we get.
Image
bennys
 
Posts: 156
Joined: 28 September 2005

Postby Shazbot » Sun Oct 23, 2005 12:46 am

Thanks Sue for the more detailed explanation. Think I'll have to print this one off and study it for a while. I'm going into mind meltdown learning all these more advanced techniques....
Shazbot
 
Posts: 220
Joined: 24 September 2005


Return to Advanced solving techniques