Can't solve hard puzzles

Advanced methods and approaches for solving Sudoku puzzles

Can't solve hard puzzles

Postby Cec » Wed Jul 13, 2005 2:04 pm

Hi Suduko friends. I started the following hard (very hard?) puzzle:

*4* *5* ***
**6 **2 **9
58* 1*6 ***

*6* 82* ***
8** *** **5
*** *73 *8*

*** 7*9 *24
6** 3** 9**
*** *6* *7*
I got as far as this:

*4* 957 ***
**6 4*2 **9
58* 1*6 ***

*65 82* ***
8** 69* **5
*** 573 *8*

358 719 624
6** 348 951
*** 265 *7*

Looking at Blocks 3,6 and 9, ie columns 7,8 and 9, the following
candidates exist which I think is a "X -Wing" pattern which I don't
fully understand even after reading the explanatory notes from
www.angusj.com/sudoku/hints.php:

1238 136 12368
134578 134 9
2347 34 27

1347 13479 137
12347 13469 5
124 8 126

6 2 4
9 5 1
138 7 138

I suspect candidates 1,3 and 8, which appear in each of the four
corner cells, r1c7, r1c9, r9c7 and r9c9, provide the necessary
rectangular pattern for a valid X-Wing. However, from this
point on I am stumped!! I would appreciate help in explaining
to me which candidates can be eliminated so I can proceed
further.

For what it's worth, I enjoy solving these puzzles but become
frustrated when I can't. The help I get from this forum is what
keeps me interested to learn more hints to solve these puzzles

Regards Bonsai Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Postby su_doku » Wed Jul 13, 2005 2:11 pm

Before donning wings - X or others, try to fill the 2 cells in box 2.
su_doku
 
Posts: 30
Joined: 19 March 2005

Postby scrose » Wed Jul 13, 2005 2:15 pm

After applying su_doku's hint, fill two cells in row 3. You will not need to look for an x-wing in the remainder of the puzzle.

Update: cecbevwr, you are correct that there is an x-wing in the 8's, but I cannot spot an x-wing in the 1's or 3's.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby QBasicMac » Wed Jul 13, 2005 5:16 pm

In your 3x3 that says
82*
69*
573

You have goofed. "6" is incorrect. You cannot solve.

Hey, try my excellent SuDoku Scratch Pad (SSP) at
www.SuDoku.funURL.com

It will not allow you to goof.

By the way, I solved it but it was very hard. I had to do 5 guesses.

I guess like this:

Save the game as G1
Guess, If it doesn't work out, restore G1 and guess again, otherwise
Save the game as G2
Guess, If it doesn't work out, restore G2 and guess again, otherwise
etc.
If all guesses fail on a given level, restore back to the last game where there are values you haven't tried yet.

Lots of work, but with SSP you don't have to do all the save/restore drudgery work. At a place where you normally would have done all the save-stuff, instead just hit "F" (free guess) and try. If it fails, continue down the list of legal values (using F) until you get a hit.

Reduces game time considerably while not being what I would call a cheater.

Mac

P.S. This game has no unique solution. There are a pair of values here
x-x --- ---
--- --- ---
--- --- ---

--- --- ---
--- --- ---
x-x --- ---

--- --- ---
--- --- ---
--- --- ---

That are matched. You can solve two ways.

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby QBasicMac » Wed Jul 13, 2005 5:26 pm

Arrgh! Never mind!!

"measure twice, cut once"

I forgot that rule!

I checked and had entered your puzzle incorrectly.

Sorry.

Mac
www.SuDoku.funURL.com
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Can't solve hard puzzles

Postby Cec » Thu Jul 14, 2005 9:25 am

Thanks Su_duko and others for your prompt response. Silly me! how did I miss the 8 in Block 1 which enabled filling the two cells in Block 2. Also filled a further two cells in Block 3 thanks to Scrose.
Pleased to note Scrose confirmed my thoughts that there is an x-wing in this puzzle although it is not necessary to use it to solve the remainder of this puzzle which I eventually did from the above clues.
However, as stated in my post, knowing that a x-wing exists but then not knowing what to do to eliminate candidates is still my problem which I would love to have explained in simple terms to help me solve other problems which require applying this knowledge.
I am even more confused with Scrose stating there is a x-wing in the 8's but not in the 1's or 3's even though, from looking at my puzzle stage, each of the three candidates 1,3 and 8 all existed at the four corner cells, r1c7,r1c9,r9c7 and r9c9.
I know I'm still learning but if x-wings help to solve puzzles then understanding how they work would be of benefit.
Welcome QBasicMac - I feel better now knowing I'm not the only one who doesn't always measure twice before I cut.

Regards Bonsai Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Re: Can't solve hard puzzles

Postby scrose » Thu Jul 14, 2005 2:44 pm

cecbevwr wrote:...each of the three candidates 1,3 and 8 all existed at the four corner cells, r1c7,r1c9,r9c7 and r9c9.

Because of the 1 at r8c9, there cannot be candidate 1's at r1c9, r9c7, or r9c9.

The candidate 3's at r1c7, r1c9, r9c7, and r9c9 do not form an x-wing because there are more than two candidate 3's in each of columns 7 and 9, and there are more than two candidate 3's in row 1.
scrose
 
Posts: 322
Joined: 31 May 2005

Can't solve hard puzzles

Postby Cec » Fri Jul 15, 2005 9:51 am

Thanks again to Scrose for your usual prompt reply and explaining (I should have initially spotted this myself) why candidate 1's can be eliminated at r1c9, r9c7 and r9c9 due to the 1 already at r8c9.
I hope I'm not overstaying my welcome in exceeding any time limit with my dilemma on x-wings where this particular example still confuses me as follows:
You say that "the candidate 3's at r1c7,r1c9, r9c7 and r9c9 do not form an x-wing because there are more than two candidate 3's in each of columns 7 and 9, and there are more than two candidate 3's in row 1". If a valid x-wing pattern requires the same candidate to occupy NO MORE THAN TWO cells in a column (or row), then I must conclude that the same candidate can only occur twice in the same column in row 1 and row 9. On this basis, how can an x-wing in the 8's exist (formed by the four corner cells r1c7,r1c9, r9c7 and r9c9) when column 7 contains THREE candidate 8's in rows 1,2 and 9?

Regards Bonsai Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Postby scrose » Fri Jul 15, 2005 11:22 am

cecbevwr wrote:...how can an x-wing in the 8's exist (formed by the four corner cells r1c7,r1c9, r9c7 and r9c9) when column 7 contains THREE candidate 8's in rows 1,2 and 9?

The x-wing exists because there are only two candidate 8's in rows 1 and 9. It is the candidate 8 at r2c7 that the x-wing allows you to eliminate.

To paraphrase from angusj's description: Given a specific candidate, the x-wing pattern requires either two rows containing exactly two cells with this candidate in each row, and these candidates must share the same two columns or two columns containing exactly two cells with this candidate in each column, and these candidates must share the same two rows.
scrose
 
Posts: 322
Joined: 31 May 2005

Can't solve hard puzzles

Postby Cec » Fri Jul 15, 2005 12:51 pm

Scrose - Once again you are spot on. Thanks again for your help.
Regards, Bonsai Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Can't solve hard puzzles

Postby Cec » Sat Jul 16, 2005 2:13 pm

Notwithstanding recent help from Scrose and reading notes from www.angusj.com/sudoku/hints.php: my dilemma with x-wing patterns still baffles me. Assuming my previous posted puzzle is still online, Blocks 3, 6 and 9 showed candidates 3 and 8 existed at the four corner cells, r1c7, r1c9, r9c7 and r9c9.

Scrose states that "the candidate 3's (at the above four corner cells) do not form an x-wing because there are more than two candidate 3's in each of columns 7 and 9 and there are more than two candidate 3's in row 1". Scrose further states that " the x-wing exists because there are only two candidate 8's in rows 1 and 9 " which allows another candidate 8 at r2c7 to be eliminated.

My dilemma is that whilst it is true that there are more than two candidate 3's in columns 7 and 9, these candidates would be eliminated by choosing candidate 3 (as an alternative to candidate 8) at r1c7 and choosing another candidate 3 (again as an alternative to candidate 8) at cell r9c9 to form an x-wing pattern. The candidate 8's would presumably each occupy a vacant cell in Blocks 3 and 9.

I'm sure there is an explanation as to why candidate 8 is placed in cell r1c7 and r9c9 to form the x-wing pattern and not candidate 3 but I just can't see why. I've been worrying that I may be a "few cents short of a dollar" but am relieved to see another reader in today's forum having similar problems to apply x-wing patterns. My apologies for not remembering her name which I saw in today's post but I don't know how to "save" this message to extract her name from the new topics as I've failed once attempting to do this which required re-typing.

I know I've been "hammering" this x-wing dilemma and your help and patience would be appreciated.

Regards Bonsai Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Postby scrose » Sat Jul 16, 2005 2:45 pm

cecbevwr, in another thread (which might be the one you were referring to) I wrote a long explanation of identifying an x-wing, which you may find helpful.

I will attempt to provide a similar explanation for how to identify an x-wing in the second grid (your progress grid) that you provided. I offer this explanation only to demonstrate why there is not an x-wing in the candidate 1's or 3's using the cells r1c7, r1c9, r9c7, and r9c9, and why there is an x-wing in the candidate 8's. Remember, the x-wing technique is not required to solve this puzzle, as pointed out by su_doku.

First, here is the set of pencilmarks for the puzzle as it stands.

Code: Select all
 {12}    4       {123}   | 9       5       7       | {1238}  {136}   {2368}
 {17}    {137}   6       | 4       {38}    2       | {13578} {13}    9
 5       8       {2379}  | 1       {3}     6       | {2347}  {34}    {237}
-------------------------+-------------------------+-------------------------
 {1479}  6       5       | 8       2       {14}    | {1347}  {1349}  {37}
 8       {1237}  {12347} | 6       9       {14}    | {12347} {134}   5
 {1249}  {129}   {1249}  | 5       7       3       | {124}   8       {26}
-------------------------+-------------------------+-------------------------
 3       5       8       | 7       1       9       | 6       2       4
 6       {27}    {27}    | 3       4       8       | 9       5       1
 {149}   {19}    {149}   | 2       6       5       | {38}    7       {38}

Clearly there cannot be an x-wing in the candidate 1's using the cells r1c7, r1c9, r9c7, and r9c9 because the 1 at r8c9 has eliminated the candidate 1's from the cells r1c9, r9c7, and r9c9.

Next, lets look at the candidate 3's.

Code: Select all
 . . 3 | . . . | 3 3 3
 . 3 . | . 3 . | 3 3 .
 . . 3 | . 3 . | 3 3 3
-------+-------+-------
 . . . | . . . | 3 3 3
 . 3 3 | . . . | 3 3 .
 . . . | . . . | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | 3 . 3

I will again review the conditions for an x-wing. To paraphrase from angusj's description: Given a specific candidate, the x-wing pattern requires either two rows containing exactly two cells with this candidate in each row, and these candidates must share the same two columns or two columns containing exactly two cells with this candidate in each column, and these candidates must share the same two rows.

It usually doesn't matter if you examine rows or columns first. Personally, in my head, I find it easier to examine columns first. So, to start, I am looking for columns that contain exactly two candidate 3's. Only columns 2 and 5 each have exactly two candidate 3's. However, columns 2 and 5 share only row 2. Because we can't find two columns (that each contain exactly two candidate 3's) that share the same two rows, we cannot find an x-wing by looking at the columns.

So lets look for rows that contain exactly two candidate 3's. Only row 9 has exactly two candidate 3's. Because we can find only one row that contains exactly two candidate 3's, we cannot find an x-wing by looking at the rows.

Therefore there is not an x-wing in the candidate 3's.

Finally, lets look at the candidate 8's.

Code: Select all
 . . . | . . . | 8 . 8
 . . . | . 8 . | 8 . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | . . .
-------+-------+-------
 . . . | . . . | . . .
 . . . | . . . | . . .
 . . . | . . . | 8 . 8

To start, I am looking for columns that contain exactly two candidate 8's. Only column 9 has exactly two candidate 8's. Because we can find only one column that contains exactly two candidate 8's, we cannot find an x-wing by looking at the columns.

So lets look for rows that contain exactly two candidate 8's. It is easy enough to see that rows 1, 2, and 9 each have exactly two candidate 8's. Check if any of these three rows share the same two columns. Rows 1 and 2 share only column 7. Rows 2 and 9 share only column 7. However, rows 1 and 9 share columns 7 and 9! We have found two rows containing exactly two cells with candidate 8's in each row, and the candidate 8's share the same two columns. We have identified the x-wing!

The x-wing lets us deduce that if an 8 is in cell r1c7 then an 8 is in cell r9c9, or if an 8 is in cell r1c9 then an 8 is in cell r9c7. Therefore, the only cells in column 7 that can contain candidate 8's are r1c7 and r9c7. Therefore the candidate 8 can be eliminated from r2c7. The only candidate 8 remaining in row 2 is at r2c5. (The reason the x-wing technique is not required is because the candidate 8 at r2c5 is the only candidate 8 remaining in box 2. This is generally easier to spot than an x-wing.)

Make sure you understand and have mastered the simpler techniques (such as candidate restrictions, pairs, triples) before trying to tackle puzzles that require advanced techniques (such as x-wing, swordfish, colouring, forcing chains).

Use of the x-wing, swordfish, colouring, and forcing chain techniques should be a last resort only, especially if you are playing on paper. These techniques rely heavily on having a complete, minimal, and accurate set of pencilmarks. If you make a mistake with your pencilmarks or haven't eliminated enough of them, it becomes much more difficult (in some cases, impossible) to apply these techniques.
scrose
 
Posts: 322
Joined: 31 May 2005

Can't solve hard puzzles

Postby Cec » Sun Jul 17, 2005 11:04 am

Thanks (and another thanks) to Scrose for your comprehensive and clear explanation which has finally enabled me to understand the conditions for a x-wing pattern. Yes, it was also helpful reading your other explanation on this same topic in another thread prompted by "Goldie" who I hope will also benefit from your response to me.
I realize that understanding x-wing patterns is one thing but the next challenge for me will be to identify the existence of such a pattern in future puzzles which I can't solve from the "simpler" techniques such as candidate restrictions, pairs, triples,etc.
Regards Bonsai Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Can't solve hard puzzles

Postby Cec » Mon Jul 18, 2005 11:17 am

After perservering and receiving considerable help from this forum in explaining what a x-wing pattern means, I suspect from the number of views this topic has accrued, that I haven't been alone in not understanding this particular topic.

Whilst now recognizing angusj's notes are correct in his description of the x-wing pattern (www.angusj.com/sudoku/hints.php:), I certainly struggled for quite a while to comprehend the explanation given even after reading it many times over. My ability to comprehend matters isn't what it used to be and is certainly no reflection on this author and others whose comments on suduko puzzle solving have helped me a lot.

This forum is great for me in learning tips from others and presumably for me to recipricate in also passing on my thoughts. I know I'm relatively new but based on the problems I encountered in failing to understand what an x-wing pattern meant, my definition would go something like this:

An x-wing pattern is formed when four identical candidates occupy any four cells which form the corners of a rectangle whose opposing sides share the same row (or column) and that such candidates are not in any other cells in the same rows and columns which are consistent with the sides of this rectangle.

I wasn't sure if my above comments form a new topic or extension of the above subject "Can't solve hard puzzles" so I opted for sending it as a reply under this same subject and await interest to any responses.

Regards Bonsai Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Re: Can't solve hard puzzles

Postby simes » Mon Jul 18, 2005 7:32 pm

At the risk of confusing you again...
cecbevwr wrote:... and that such candidates are not in any other cells in the same rows and columns...

If both those are true, then finding the XWing won't allow you to eliminate any candidates. There has to be some candidates in other cells in the same rows or columns so they can be eliminated.
Last edited by simes on Sun Dec 11, 2011 10:13 am, edited 1 time in total.
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Next

Return to Advanced solving techniques