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 

Necessary and sufficient set of solving techniques

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



Joined: 20 Jan 2011
Posts: 3

PostPosted: Thu Jan 20, 2011 4:53 am    Post subject: Necessary and sufficient set of solving techniques Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3173
Location: near Detroit, Michigan, USA

PostPosted: Thu Jan 20, 2011 8:13 am    Post subject: Re: Necessary and sufficient set of solving techniques Reply with quote

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
View user's profile Send private message
xgameguy



Joined: 20 Jan 2011
Posts: 3

PostPosted: Thu Jan 20, 2011 6:31 pm    Post subject: Reply with quote

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
View user's profile Send private message
keith



Joined: 19 Sep 2005
Posts: 3173
Location: near Detroit, Michigan, USA

PostPosted: Thu Jan 20, 2011 9:34 pm    Post subject: Reply with quote

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
View user's profile Send private message
garytorborg



Joined: 19 Jan 2011
Posts: 28

PostPosted: Wed Feb 23, 2011 5:50 pm    Post subject: Re: Necessary and sufficient set of solving techniques Reply with quote

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
View user's profile Send private message Send e-mail
keith



Joined: 19 Sep 2005
Posts: 3173
Location: near Detroit, Michigan, USA

PostPosted: Wed Feb 23, 2011 7:13 pm    Post subject: Reply with quote

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
View user's profile Send private message
Pat



Joined: 23 Feb 2010
Posts: 165

PostPosted: Sun Feb 27, 2011 8:26 am    Post subject: Reply with quote

keith wrote:

    There are many that can only be solved by brute force (guessing)

extra-tough puzzles may need complicated "forcing nets"
    some call this guessing
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