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: 3344 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 Xwings, XYwings, and XYZwings as advanced techniques. In practice, most of them are onesteppers that need only an XYwing.
That said, people often present solutions that use other techniques like Unique Rectangles, Wwings and Mwings.
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: 3344 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 xywings, xyzwings, or wwings; 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: 3344 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: 182

Posted: Sun Feb 27, 2011 8:26 am Post subject: 


keith wrote: 
There are many that can only be solved by brute force (guessing) 
extratough 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
