| View previous topic :: View next topic |
| Author |
Message |
xgameguy
Joined: 20 Jan 2011
Posts: 3
|
 Posted: Thu Jan 20, 2011 4:53 am Post subject: Necessary and sufficient set of solving techniques |
 |
|
| I have only been doing VH puzzles for about a month, but have done dozens in that time. The many, sometimes complex techniques are interesting, but my scientific mind is more interested in the "elegant" (i.e. simplest and most straightforward) solutions. Which causes me to ask the question: "What is the smallest set of solution techniques that will solve all puzzles?" So far, I have been able to solve everything with basic techniques, x wings and XY chains. I suspect that xy chains longer than 2 links (i.e. xy wings) may be unnecessary. Is anyone aware of a puzzle that cannot be solved using just basic logic, x wings and xy wings? |
|
| Back to top |
|
 |
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Thu Jan 20, 2011 8:13 am Post subject: Re: Necessary and sufficient set of solving techniques |
|
|
| xgameguy wrote: | | Is anyone aware of a puzzle that cannot be solved using just basic logic, x wings and xy wings? |
xgameguy,
The "Very Hard" daily puzzles on this site, DailySudoku.com, are specially selected and can always be solved using only X-wings, XY-wings, and XYZ-wings as advanced techniques. In practice, most of them are one-steppers that need only an XY-wing.
That said, people often present solutions that use other techniques like Unique Rectangles, W-wings and M-wings.
In general, there are plenty of puzzles that cannot be solved using only the techniques you mention. There are many that can only be solved by brute force (guessing).
Here is such a puzzle:
| Code: | Puzzle: M463017sh+1451
+-------+-------+-------+
| 2 . . | . . 9 | 8 . . |
| . . 1 | . . . | 7 . . |
| . 4 . | 5 . . | 3 2 . |
+-------+-------+-------+
| . . . | . . . | 5 4 . |
| 8 . . | . . 1 | . . . |
| . . . | . 2 . | 9 . . |
+-------+-------+-------+
| . 7 . | . . 6 | . 9 . |
| 9 . 5 | 2 . . | . . 7 |
| . . 3 | . . . | . . . |
+-------+-------+-------+ |
and its solution
| Code: | Puzzle: M463017sh+1451
+-------+-------+-------+
| 2 3 6 | 7 1 9 | 8 5 4 |
| 5 8 1 | 3 4 2 | 7 6 9 |
| 7 4 9 | 5 6 8 | 3 2 1 |
+-------+-------+-------+
| 6 1 7 | 8 9 3 | 5 4 2 |
| 8 9 2 | 4 5 1 | 6 7 3 |
| 3 5 4 | 6 2 7 | 9 1 8 |
+-------+-------+-------+
| 4 7 8 | 1 3 6 | 2 9 5 |
| 9 6 5 | 2 8 4 | 1 3 7 |
| 1 2 3 | 9 7 5 | 4 8 6 |
+-------+-------+-------+ |
Keith |
|
| Back to top |
|
|
xgameguy
Joined: 20 Jan 2011
Posts: 3
|
| Posted: Thu Jan 20, 2011 6:31 pm Post subject: |
|
|
Keith,
Thanks for the response. If VH puzzles are preselected to be solvable with the smplest of the wing techniques, it makes sense that they would all be solvable with those techniques!!!
I see that the puzzle you cite as an example of one that requires brute force is not symetrical. All of the sudokus I have seen before have been symetrical. I wonder if a symetry limitation necesarily restricts the difficulty of a puzzle. Do you know if that is the case? |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Thu Jan 20, 2011 9:34 pm Post subject: |
|
|
| xgameguy wrote: | | I wonder if a symetry limitation necesarily restricts the difficulty of a puzzle. Do you know if that is the case? |
X,
Symmetry in Sudoku puzzles is simply an aesthetic issue. It became a custom in Japan, where the Sudoku craze first took hold.
The symmetry requirement can only make a puzzle less difficult. That does not mean it makes them easy! To try to explain:
First, accept that a valid Sudoku puzzle can only have a single solution. Each such puzzle has a "minimal" statement. That is, if any initial clue is deleted, the puzzle is invalid. There is no reason that the minimal set of clues should be symmetric.
So, to obtain symmetry, you have to add clues beyond the minimal set. That makes the puzzle "easier". If the added clues are only singles in the minimal puzzle, I think we would agree that the puzzle is not really "easier".
I don't know that symmetry confers any attributes on a puzzle. For example, Danny's puzzles all have the same symmetry, yet they are quite diverse in their difficulty and solution techniques.
It is interesting to note that Sudokus with the minimum number of initial clues (17) are generally not very difficult. If you go to the player's forum
http://forum.enjoysudoku.com/
you will find discussions on all sorts of things you (so far) have not had to worry about. Like: "What is the maximum number of initial clues a minimal Sudoku can have?"
A Google search on Sudoku Mathematics will bring up a lot of interesting information.
Keith |
|
| Back to top |
|
|
garytorborg
Joined: 19 Jan 2011
Posts: 28
|
| Posted: Wed Feb 23, 2011 5:50 pm Post subject: Re: Necessary and sufficient set of solving techniques |
|
|
| keith wrote: | | xgameguy wrote: | | Is anyone aware of a puzzle that cannot be solved using just basic logic, x wings and xy wings? |
In general, there are plenty of puzzles that cannot be solved using only the techniques you mention. There are many that can only be solved by brute force (guessing).
Keith |
I disagree that any puzzles have no solution other than guessing. All of us have had to resort to Brute Force from time to time, but I really can't bring myself to view it as a solving technique. After the fact, I have discovered several instances where I had used Brute Force when I could have used some kind of chain. A recent puzzle I posted at http://www.dailysudoku.co.uk/sudoku/forums/viewtopic.php?t=5535 is a good example. I had nearly given up on it after not being able to find any xy-wings, xyz-wings, or w-wings; at least none that resulted in any eliminations. Then, some people here showed me a chain (2 of them) that worked.
Somewhere along the way, there is a solution for even the toughest of puzzles that can be used to break down a puzzle by some kind of logic, though it may well be very, very complex. |
|
| Back to top |
|
|
keith
Joined: 19 Sep 2005
Posts: 3355
Location: near Detroit, Michigan, USA
|
| Posted: Wed Feb 23, 2011 7:13 pm Post subject: |
|
|
| Quote: | | All of us have had to resort to Brute Force from time to time, but I really can't bring myself to view it as a solving technique. |
Why not? Just call it "exhaustive search" which is a very respectable technique used in countless computer programs.
Keith |
|
| Back to top |
|
|
Pat
Joined: 23 Feb 2010
Posts: 207
|
| Posted: Sun Feb 27, 2011 8:26 am Post subject: |
|
|
| keith wrote: |
There are many that can only be solved by brute force (guessing) |
extra-tough puzzles may need complicated "forcing nets" |
|
| Back to top |
|
|
|
|
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
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
