dailysudoku.com Forum Index dailysudoku.com
Discussion of Daily Sudoku puzzles
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

The Hunt (how to spot and shoot those winged creatures)

 
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology
View previous topic :: View next topic  
Author Message
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Mon Feb 04, 2008 7:45 pm    Post subject: The Hunt (how to spot and shoot those winged creatures) Reply with quote

I found this sentence today in the Daily Sudoku section:

Quote:
...Unfortunately for me it is one of those VH's for which will have to go in the unsolved archive. I just don't have the techniques for solving this variety. All I do is stare at it for ages not able to see any way through. Sad


... which made me realize that the problem is not really to understand the more advanced techniques, but to apply them in real-life situations like looking for that one crucial step needed to solve today's daily vh.

The problem with hunting, I would assume, is not loading the gun or pulling the trigger. Could it be that the problem lies with

- finding your prey
- and aiming the gun (stone, arrow, ...)

????

This is about

THE HUNT




HOW to find those x-wings, xy-wings and stuff ???

It is not terribly hard to do, so don't expect any deep insights !

Which is exactly what this mini-thread is about: solving sudoku is nothing like epiphany. Nor samadhi. No sudden insight (mostly).
More like C.S.I., I guess. Try one approach. Try another. Find a clue. Repeat.

I hope to bring this process out of the esoteric cercles of the initiated into the everyday world. After all, even the very hard sudoku are nothing more than grid of 81 squares that can be solved by logic alone.

I've shamelessly copied the posts over from the Daily Sudoku section (hope I'm not violating any forum rules Smile ) - the puzzle in question is the Feb. 3, 2008 "very hard"

Don't forget: HAVE FUN ! (Having fun is much easier with the right tools)

___


edit: the painting is "The Hunt" by Claude Monet
edited again to correct typos
edited agein to inlude music when clicking the picture. Sergej Prokoffjev: "Peter and the Wolf" - "The Hunters".


Last edited by nataraj on Fri Feb 15, 2008 5:52 pm; edited 3 times in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Mon Feb 04, 2008 7:47 pm    Post subject: Reply with quote

Mindwarp wrote:
Ah we are back, unfortunately for me it is one of those VH's for which will have to go in the unsolved archive. I just don't have the techniques for solving this variety. All I do is stare at it for ages not able to see any way through. Sad


Mindwarp, I am sure you are not the only one. This puzzle is somewhat more difficult than the usual VHs, because the more obvious singles and naked pairs don't go as far as usual.

After basics, this is what you should have:
Code:

+--------------------------+--------------------------+--------------------------+
| 5       234     2369     | 17      1267    126      | 8       2349    234      |
| 239     7       239      | 4       8       5        | 6       239     1        |
| 246     8       1        | 9       26      3        | 7       5       24       |
+--------------------------+--------------------------+--------------------------+
| 34      345     7        | 2       9       14       | 135     8       6        |
| 23469   2345    2369     | 8       1456    146      | 12359   23      7        |
| 8       1       269      | 56      3       7        | 259     24      245      |
+--------------------------+--------------------------+--------------------------+
| 12      6       5        | 3       12      9        | 4       7       8        |
| 7       9       4        | 56      256     8        | 235     1       235      |
| 123     23      8        | 17      12457   124      | 25      6       9        |
+--------------------------+--------------------------+--------------------------+


If you have more candidates in some cells, you are probably missing a triple or a box/line interaction.

But even if you got here clean, there are many cells with more than two candidates, and the search for xy-wings doesn't turn up any results at this point.

This is when looking for x-wings or similar patterns become necessary.

What I do is, I take each number (1,2,3...) in turn (actually I start with those that already have many solved cells - it is easier to spot patterns if only few cells remain ...)

Let's see, what we have:
"many": 8 (9 solved), 7 (7 solved)
"some": 1,5,6 (4 solved) 3 (3)
"few": 2 (only 1 solved)

8 is fully soved - nothing to do

7 is almost solved, only r19c45 remain. This is the x-wing pattern we are looking for: 4 cells in a square. Unfortunately, if there are no other cells with this number (7) in it, there is nothing else to do. But remember the pattern - two rows with 2 sevens each, and at the same columns. Or two columns with 2 sevens each, and at the same rows.

I gave the clue in my previous post, so let's look at "5".

The rows yield nothing - a few rows with only 2 fives, but at wildly different column positions.

But the columns: There are 3 columns with exactly two 5s: cols 2,4,9.

In columns 4 and 9, the fives are at rows 6 and 8.

Heureka! The x-wing pattern! It means that in rows 6 and 8 the two "5"s must be at columns 4 and 9. Thus we can eliminate "5" from all the other columns in those two rows.

That removes 5 from r4c7 and r8c5 and r8c7.

I remember I used to look at the grid forever in those situations. What I found out is that one needs a search pattern. It is much too frustrating to look at the same cells over and over again - only to realize later that the solution was there all the time but I did not know what to look for.

So try this
a) Do a rough estimate (for each number 1,2,3...) of how many cells are SOLVED with that number. "rough" means "many", "some", "few"
b) Start with the "many". Look for rows with only 2 occurrences of that number. Look for the xwing pattern. Do the same for columns.
c) Work your way down to "some" and "few".
d) Even if nothing was found, at that point you KNOW there are no x-wings and something else is needed. Coffe break, most probably Wink

It is a bit tedious. But does NOT take very long. We are talking 5-10 minutes for a whole puzzle, max. And it beats staring at the thing "for ages" Smile anytime.

And - psychologically speaking - this strategy (or any other structured search pattern) gives one the feeling of being in control, of having a plan. And that is much much better than a random search...

_____

Just for the record: if we had continued with "6", we would have found nothing with this simple search pattern. The "skyscraper" pattern (two rows with 2 candidates each but ony with ONE position shared) in columns 1 and 6 is only slightly more difficult to spot (in this case it allows to remove 6 from r1c3 and r3c5), the "kite", "turbot fish" and other patterns (so called "coloring" techniques, or the Empty Rectangle in Johan's post) need differnt searches.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Mon Feb 04, 2008 7:51 pm    Post subject: Reply with quote

melis wrote:
OK, got the 5 x-wing and cleaned it up a bit, but am stuck again! Just don't want to give up, otherwise I'm never going to learn. Any advice? Confused


ravel wrote:
There is one more advanced step needed (i suppose you noticed the pairs and had some singles).
Code:
 *-----------------------------------------------------*
 | 5     24   2369  | 1   7   26   | 8      2349  234  |
 | 39    7    239   | 4   8   5    | 6      239   1    |
 | 46    8    1     | 9   26  3    | 7      5     24   |
 |------------------+--------------+-------------------|
 | 34    45   7     | 2   9   14   | 135    8     6    |
 | 3469  245  2369  | 8   45  146  | 12359  23    7    |
 | 8     1    269   | 56  3   7    | 29     24    245  |
 |------------------+--------------+-------------------|
 | 2     6    5     | 3   1   9    | 4      7     8    |
 | 7     9    4     | 56  26  8    | 23     1     235  |
 | 1     3    8     | 7   45  24   | 25     6     9    |
 *-----------------------------------------------------*

In boxes 1 and 2 you can find 2 xy-wings. Both solve the puzzle.
Alternatively you have Johan's ER or the skyscraper in 6 (columns 1 and 6).


Again, it is helpful to use a search pattern.

Try this on for size:

Starting at the top left, take one row at a time, going from left to right, and look for bi-value cells (those cells with exactly two candidates in them).

In ravel's grid, the first such cell would be r1c2 {2,4}

For each cell found, look
- to the right in the same row
- down in the same column
- in the same box
and see if there are any other bi-value cells that share one candidate with the first cell found

In ravel's grid, that "second cell" would be r1c6 {2,6}

Now we need to look for the third cell that makes up the xy-wing. And as it happens, we know exactly what to look for: a cell with {4,6} in it that "sees" either the first or the second cell. We don't have to look far:
- row 1,
- columns 2,6
- boxes 1,2

Now, aren't we lucky today? r3c1 is such a cell! And we have found an xy-wing. Remains to see whether it solves anything: this xy-wing (46-24-26) removes 6 from all cells that see r3c1 and r1c6, and that would be r1c3 and r3c5. r3c5 is especially valuable, because it solves a cell r3c5=2.

Usually, at this point the search stops and we solve the sudoku.

Just for demonstration purposes, let us continue the search pattern.

There are no more cells with {4,6}

Look for other "second cells":
- nothing in row 1
- {4,5} in col 2 (r4c2). Look for {2,5}. No such luck
- {4,6} in box 1 r3c1. Look for {2,6) ... r1c5, we got that. r3c5 is good!

We found another xy-wing. This xy-wing (24-46-26) removes 2 from all cells that see r1c2 and r3c5, there is only one such cell r1c6 and it solves r1c6=6

No more second cells can be found, continue with all other possible first cells:

Take {2,6} in r1c6. The search becomes progressively faster because we only need to look right and down and box, not left and up (we already did these).

Possible "second cells": only one.
{2,4} (r9c6), with third cell {4,6}: such a cell exists, but not in rows 1,9, col 6 or boxes 2,8 -> no wing

Next "first cell": [3,9} in r2c1.
Second cells: none in r2, {3,4} in c1 (but no third cell {4,9}), none in box 1.

And so on.

A simple search pattern, guaranteed to find xy-wings if any exist.
And fast. The long explanation may look forbidding, but with a little practice it takes only a few minutes for the whole puzzle.

Only a little longer if one includes xyz-wings in the search.

Good hunting! Waidmannsheil!
Back to top
View user's profile Send private message Send e-mail Visit poster's website
melis



Joined: 04 Feb 2008
Posts: 6
Location: Berkshire, England

PostPosted: Thu Feb 14, 2008 2:58 pm    Post subject: The Hunt Reply with quote

Thanks, nataraj, for the advice on "The Hunt". Have found it very helpful, along the lines of "Teach a man to fish......".

Great Monet! (For some reason, "Peter and the Wolf" runs through my head now!)
Back to top
View user's profile Send private message
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Fri Feb 15, 2008 5:50 pm    Post subject: Reply with quote

Thx for the feedback, melis! I've added the music to the picture.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
nataraj



Joined: 03 Aug 2007
Posts: 1048
Location: near Vienna, Austria

PostPosted: Fri Feb 22, 2008 10:55 pm    Post subject: Reply with quote

And here you can take a look at the Academy Award winning
Peter & the Wolf, also with the Prokovjeff's music

__

edited Feb 25 to change Academy Award "nominated" to "winning" Smile


Last edited by nataraj on Mon Feb 25, 2008 6:38 am; edited 1 time in total
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Myth Jellies



Joined: 27 Jun 2006
Posts: 64

PostPosted: Sun Feb 24, 2008 7:03 am    Post subject: Reply with quote

Note that nataraj's almost solved sevens make excellent fodder for almost UR type deductions.

Code:
+--------------------------+--------------------------+--------------------------+
| 5       234     2369     |*17     *17+26   126      | 8       2349    234      |
| 239     7       239      | 4       8       5        | 6       239     1        |
| 246     8       1        | 9       26      3        | 7       5       24       |
+--------------------------+--------------------------+--------------------------+
| 34      345     7        | 2       9       14       | 135     8       6        |
| 23469   2345    2369     | 8      *1456    146      | 12359   23      7        |
| 8       1       269      | 56      3       7        | 259     24      245      |
+--------------------------+--------------------------+--------------------------+
| 12      6       5        | 3      *12      9        | 4       7       8        |
| 7       9       4        | 56      256     8        | 235     1       235      |
| 123     23      8        |*17     *17+245  124      | 25      6       9        |
+--------------------------+--------------------------+--------------------------+

Note that in columns 4 & 5, the only way to avoid the deadly 17 pattern in r19c45 is for either r5c5 or r7c5 to be 1 (the sevens are locked in the UR), therefore we can eliminate the ones in r19c5.
Back to top
View user's profile Send private message
Marty R.



Joined: 12 Feb 2006
Posts: 5770
Location: Rochester, NY, USA

PostPosted: Sun Feb 24, 2008 5:07 pm    Post subject: Reply with quote

Quote:
Note that in columns 4 & 5, the only way to avoid the deadly 17 pattern in r19c45 is for either r5c5 or r7c5 to be 1 (the sevens are locked in the UR), therefore we can eliminate the ones in r19c5.

I had to stare at that for a few minutes before realizing you were just stating the same logic differently from how I learned it.

The way I learned is that it's a Type 4 UR because the 7's are a strong link in c5, therefore r19c5 cannot contain a 1. The end result, not the opening hypothesis, is that r5c5 or r7c5 must be 1. Smile
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    dailysudoku.com Forum Index -> Solving techniques, and terminology All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group