trial and error / forcing chains

Advanced methods and approaches for solving Sudoku puzzles

trial and error / forcing chains

Postby vvill » Fri Dec 02, 2005 1:53 am

I'm new to formal sudoku techniques but I've been using most of the techniques I've found mentioned here through intuition / learning / etc.

My question is, at what point would you resort to using forcing chains or trial and error? I really dislike having to use these methods as they don't seem "logical" to me...

Also - a quick query about Pappocom difficulty levels - is there a set difference between Hard and Very Hard? For example, could I be guaranteed that I could solve all Hard puzzles without needing trial and error?
vvill
 
Posts: 4
Joined: 01 December 2005

Postby Shazbot » Fri Dec 02, 2005 6:26 am

You can solve ALL Pappocom puzzles without trial and error - it's just likely a technique you haven't learned yet.

From what I've read about Forcing Chains on the Sadman site, they're similar to colouring (this would be a good spot for someone to point me to a discussion on the differences, if there are any). I'm learning to do colouring, and finding it really helpful. This (or forcing chains) should not be necessary on ANY Pappocom puzzles to my knowledge.

Pappocom Hard puzzles might require you to use the xwing technique, while Very Hard could require a swordfish. I moved over to Angus J's Simple Sudoku which requires combinations of xwing, swordfish and colouring to solve the Extreme puzzles (harder than the Pappocom Very Hard) - and today (though if I continued looking I may have found something more simple) I solved my first puzzle using the next # up from swordfish - 4 interlocking columns/rows (what's that called again?)

To learn these techniques, visit either AngusJ's site or the SadMan techniques site
Shazbot
 
Posts: 220
Joined: 24 September 2005

Postby SarC » Fri Dec 02, 2005 10:54 am

I solved my first puzzle using the next # up from swordfish - 4 interlocking columns/rows (what's that called again?)


Jellyfish:D
SarC
 
Posts: 13
Joined: 25 September 2005

Postby vvill » Fri Dec 02, 2005 3:16 pm

Shazbot wrote:From what I've read about Forcing Chains on the Sadman site, they're similar to colouring (this would be a good spot for someone to point me to a discussion on the differences, if there are any). I'm learning to do colouring, and finding it really helpful. This (or forcing chains) should not be necessary on ANY Pappocom puzzles to my knowledge.

Pappocom Hard puzzles might require you to use the xwing technique, while Very Hard could require a swordfish.
To learn these techniques, visit either AngusJ's site or the SadMan techniques site


Ok thanks. I'm stuck only on a Hard:( Crap, I thought I was decent at Sudoku. I've visited Sadman's site, but I guess there's something I'm missing. I've been trying to spot something by intuition, as I prefer to find out techniques by my own logic rather than reading up somewhere.
vvill
 
Posts: 4
Joined: 01 December 2005

Re: trial and error / forcing chains

Postby tso » Fri Dec 02, 2005 7:08 pm

vvill wrote:I'm new to formal sudoku techniques but I've been using most of the techniques I've found mentioned here through intuition / learning / etc.

My question is, at what point would you resort to using forcing chains or trial and error? I really dislike having to use these methods as they don't seem "logical" to me...


Though this often asked question seems sensible, it is faulty. Like asking if there is a bookcase so tall that you cannot reach the top shelf -- the answer depends entirely on how tall you are, if you have a step ladder, how willing you are to stand on the top of a teetering step ladder, etc.

Take this puzzle for example, posed in another thread:

Code: Select all
  1    24   3    | 49   5    6    | 7    8    29   
  6    24   7    | 1    49   8    | 25   3    259 
  8    5    9    | 7    3    2    | 6    4    1   
 ----------------+----------------+--------------
  59   7    8    | 29   6    4    | 25   1    3   
  2    3    6    | 8    1    5    | 4    9    7   
  59   1    4    | 3    29   7    | 8    6    25   
 ----------------+----------------+--------------
  3    8    5    | 24   24   9    | 1    7    6   
  7    6    1    | 5    8    3    | 9    2    4   
  4    9    2    | 6    7    1    | 3    5    8   


Until recently, most solvers would have had to search for a forcing chain by one method or another to complete this puzzle, for example:

Code: Select all
  .    .    .    | 49-------------------------29   
  .    .    .    | |    .    .    | .    .    |   
  .    .    .    | |    .    .    | .    .    |   
 ----------------+-|--------------+-----------|--
  .    .    .    | 29---------------25   .    |   
  .    .    .    | .    .    .    | . \       |   
  .    .    .    | .    .    .    | .  +------25   
 ----------------+----------------+--------------
  .    .    .    | .    .    .    | .    .    .   
  .    .    .    | .    .    .    | .    .    .   
  .    .    .    | .    .    .    | .    .    .   


You can easily follow around the path and see that no matter what value r4c4 is, r1c4 must be 4.

One way of finding such a chain is by drawing lines between cells that have only two candidates and labeling those lines with the shared candidate:


Code: Select all
  .    .    .    | 49-----------(9)-----------29   
  .    .    .    | |    .    .    | .    .    |   
  .    .    .    |(9)   .    .    | .    .    |   
 ----------------+-|--------------+----------(2)-
  .    .    .    | 29------(2)------25   .    |   
  .    .    .    | .    .    .    | . \       |   
  .    .    .    | .    .    .    | . (5)-----25   
 ----------------+----------------+--------------
  .    .    .    | .    .    .    | .    .    .   
  .    .    .    | .    .    .    | .    .    .   
  .    .    .    | .    .    .    | .    .    .   


As you follow the labels around the loop -- you *know* that because there are two 9s in a row and no other duplication that we can remove the 9 from r1c4 where they intersect. No trial and error here. You can learn the underlying logic -- or you can use the tactic without knowing why it works.

While I wouldn't consider this "resorting to forcing chains", as for many of us, this is the cherry on the top of the puzzle, you might find it tedious to find chains in some or most cases.

But in this case, there's another way, discovered just recently:

Code: Select all
  1    24   3    | 49   5    6    | 7    8    29   
  6    24   7    | 1    49   8    | 25   3   [259]
  8    5    9    | 7    3    2    | 6    4    1   
 ----------------+----------------+--------------
  59   7    8    | 29   6    4    | 25   1    3   
  2    3    6    | 8    1    5    | 4    9    7   
  59   1    4    | 3    29   7    | 8    6    25   
 ----------------+----------------+--------------
  3    8    5    | 24   24   9    | 1    7    6   
  7    6    1    | 5    8    3    | 9    2    4   
  4    9    2    | 6    7    1    | 3    5    8   


Notice that the cell in [brackets] is the only one with three possible values while all the other undecided cells have exactly two. In this situation -- without having to know why -- you can solve the puzzle. Simply examine the row, box or column -- it does not matter which -- in which this 3- possibility-cell sits. Look to see which candidate occurs THREE times (The others will all occur twice or not at all.) That candidate is solution to that cell! The candidate '2' appears three times in row 2, three times in column 9, three times in box 3.

You don't have to know why if you don't want to, though it's fascinating to learn. As long as the puzzle has a unique solution, it works. And even you will have to admit -- that applying this tactic is ridiculously easy and the very opposite of trial and error. If you know why it works, it will seem logical. If you don't, it will seem magical.

If this position is dubbed into Pappocom software, it is rated as ARGUABLY UNFAIR/VERY HARD -- harder than anything that it will generate itself. But once you know this tactic, the puzzle is actually trivial.

As recently as May, puzzles like this were viewed by a significant contingent as being unsolvable without "bifurcation", guessing or trial and error. See Dead easy -- but beyond "logic".


Don't let me mislead you -- there are plenty of Sudokus that currently no human has been able to solve with pencil and paper in a purely logical and satisfying way -- but we generally assume that this is a temporary condition that will change with new discoveries. The line between solvable and intractable will continually be pushed back. Unfortunately, there will never be a simple way to decide which group a puzzle belongs in that's quicker than solving it. Luckily, there are many people creating software solvers that use human implementable logic. You could for example, enter a puzzle into Sudoku Susser, set it to only use that tactics you are comfortable with. If it cannot solve the puzzle, you can discard it an try another. If it can, print it out and have fun.


Also, you are conflating trial and error with forcing chains. Trial and error is a *method*. Forcing chains, like naked pairs is a *pattern*. You might find *either* pattern by any number of methods, including, but not limited to, trial and error. I'll go out on a limb and say that most of the regular reader/posters in this forum who use forcing chains to solve puzzles find them by means other than trail and error. It is my opinion that if you don't like finding forcing chains, its because you don't know how to find them in a methodical way.

vvill wrote:Also - a quick query about Pappocom difficulty levels - is there a set difference between Hard and Very Hard? For example, could I be guaranteed that I could solve all Hard puzzles without needing trial and error?


To be accurate, X-wings are *never* required by Pappocom Hard. Swordfish are *never* required by any level Pappocom puzzle.
Trial and error is *never* required by any level Pappocom puzzle.
As I said earlier, Trial and error is *never* required for *any* puzzle, though there very well may be those that are clearly beyond *current* capabilities and techiques of all human solvers. (I wouldn't be surprised if an idiot-savant (Is that term PC?) pops up who can do the most intractable puzzles as if it were simple arithmetic.))

That being said, it is quite possible to find an x-wing, swordfish or other pattern in a puzzle that doesn't *require* it to solve. It may be more fun to notice and utilize a naked triple when a naked single is staring you in the face on the other corner of the puzzle.

Further, to be completely accurate, a puzzle cannot actually *require* an x-wing (or other pattern). Though there might not be simpler path than identifying and x-wing in a particular case, there's always a more complex method.

No one other than Wayne seems to know exactly what criteria he uses to assign ratings. I believe he's stated that it's based on a number of variables that cannot be reduced to a simple "all hard puzzles have tactic A". It may be that you will find some puzzles rated "Very Hard" easier than others rated "Hard" because of which tactics you are more comfortable with.
tso
 
Posts: 798
Joined: 22 June 2005

Postby Shazbot » Fri Dec 02, 2005 10:37 pm

thanks tso for pointing out my error. You're right - I never encountered swordfish patterns until I started using Simple Sudoku (I recall installing that software to try some of the more advanced techniques), but I have used xwings often on Pappocom puzzles - though there may have been an easier technique that I missed.

thanks also for the link to the other thread and your explanation of that puzzle. I TOTALLY don't understand that discussion, but am going to revisit and work through the example - can't let an opportunity for such an easy method of elimination pass by.
Shazbot
 
Posts: 220
Joined: 24 September 2005


Return to Advanced solving techniques