Forcing Chains

Advanced methods and approaches for solving Sudoku puzzles

Postby sirdave » Tue Mar 20, 2007 6:35 pm

Neunmalneun wrote:Sirdave:

"Also, in the end, it's all about solving elegance". I think that is the only question we disagree about.....

I don't mind guesswork at all and I can't see the moral distinction between patterns and chains. If you look for your missing key you would not care if your way to find it was elegant or if you looked into the same drawer for several times. You are just relieved when you found it in the end.


"I only resort to forcing chains when all other techniques including nice loops have a escaped me and it is only one type of forcing chain- the classic double-implication forcing chain." I can't see the logic here. If you eventually resort to forcing chains, why don't you use them before if (it gives you an easier solution)? That looks to me as if you deliberately avoid an earlier solution just for elegant's sake.


Of course, everyone has the right to solve a Sudoku puzzle however they want; there's nothing moral involved in the premise. My concern is more for those budding Sudoku players who are trying to figure out what direction to take and what methods to learn and having learned them, what order to use them in. Discussions like this can be very confusing to them. Also, I firmly believe that the interest in Sudoku over the last 2 years has increased in direct proportion to the advances that have been made in the solving process.

Regarding my 'solving elegance' remark- perhaps I didn't explain the concept (as I use it) well enough. It's not just about the sophistication of the solution, although I admit to the fact that I am much prouder of a puzzle solution that involves using methods that are as far removed from guessing as possible, it's also about efficiency. Let's assume that I am solving one of the more difficult Diabolicals and have 'used up' all of the basic and most of the more advanced methods leaving me with a choice between nice loops and forcing chains. Which to use first?

After a lot of exposure to nice loops one gets to the point where one can play around with the various kinds of nice loops which may very well not only solve one cell, but raise possibilities for solving other cells. This usually doesn't take very long. However, with forcing chains you can spend a lot of time trying to find a chain that works to solve just one cell. For me it's just not as efficient and, in addition, I admit that personally for me, it's too close to guesswork. However, if I come up dry with nice loops, I can resort to the forcing chain sledgehammer to solve a cell that may get me back on track. As I mention above, I am actually hoping for the day where I get to the point where I won't have to use the forcing chain option.
Last edited by sirdave on Tue Mar 20, 2007 2:43 pm, edited 2 times in total.
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby sirdave » Tue Mar 20, 2007 6:41 pm

gsf wrote:
sirdave wrote:
gsf wrote:
sirdave wrote:Basic elimination + only hidden singles solves most puzzles without recursion or at most 2-level recursion?

How can that be possible in light of how extensive this section of the forum (Advanced solving techniques) is? What you mean by 'most puzzles'?

to date even the hardest 9x9 sudoku have at least one singles backdoor of size 2
http://forum.enjoysudoku.com/viewtopic.php?p=34684#p34684


With all due respect, you have moved from stating that premise as a 'concept' and 'conjecture' (in your post that you show a link to above) to stating it as fact now.

the fact is that no puzzle has yet been found to refute the conjecture (that's why I said "to date")
that's the essence of a conjecture
no proof for it or against it yet


Thanks for the clarification. I guess I'd feel a little better about the 'no puzzle has yet been found to refute the conjecture' if there were people out there actively trying to refute it.:D BTW: I was going to modify my post to make it sound less abrupt ('cause I didn't mean it that way) before you replied, but I got involved in my other reply above.
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby ravel » Tue Mar 20, 2007 7:38 pm

sirdave wrote:I guess I'd feel a little better about the 'no puzzle has yet been found to refute the conjecture' if there were people out there actively trying to refute it.:D
There has been made a lot of effort in this dierection in the last year, namely by all the people, that tried to find ultra hard puzzles (and had successfully crossed many new milestones).
In fact, also a puzzle with only 2 backdoor pairs was found by dml and one with 3 by Mike Metcalf. If you think, that easily could be improved - they both have an Explainer rating above 11:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby sirdave » Tue Mar 20, 2007 7:58 pm

ravel wrote:
sirdave wrote:I guess I'd feel a little better about the 'no puzzle has yet been found to refute the conjecture' if there were people out there actively trying to refute it.:D
There has been made a lot of effort in this dierection in the last year, namely by all the people, that tried to find ultra hard puzzles (and had successfully crossed many new milestones).
In fact, also a puzzle with only 2 backdoor pairs was found by dml and one with 3 by Mike Metcalf. If you think, that easily could be improved - they both have an Explainer rating above 11:)


Interesting, but would this have any practical effect on the direction solving methods are going or is it of theoretical interest only. I'd hate to think that it is mistaken by newcomers as a support for solving using only hidden singles and trial and error to find those backdoors.
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby ravel » Tue Mar 20, 2007 8:21 pm

There are so much sudokus (about 10^25 non isomorphic ones), that you can find more for each level of difficulty (or allowing an elegant solution using the technique you prefer), than you can solve manually in lifetime.

I dont know anybody, who likes to try each candidate and follow all singles until one is found, that finally solves it. Puzzles, where this method might be effective, for me are too hard for having fun in solving them manually - and people, who do have, i think, use other methods like nice loops or forcing nets (btw you seem to have a very restricted definition for nice loops, since each forcing chain and even forcing net can be represented as nice loop also - just look at Carculs solutions).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby gsf » Tue Mar 20, 2007 8:35 pm

sirdave wrote:Thanks for the clarification. I guess I'd feel a little better about the 'no puzzle has yet been found to refute the conjecture' if there were people out there actively trying to refute it.:D BTW: I was going to modify my post to make it sound less abrupt ('cause I didn't mean it that way) before you replied, but I got involved in my other reply above.

I periodically scrape the forums and always check the hardest threads
its seems that the hardest puzzles would have the best chance of breaking the conjecture

btw, ruud generated some pencilmark only grids with size 3 and size 4 singles backdoors
the smallest singles backdoor for this one is size 4, and the quick rating fails after 110046 propositions
i.e., it searched for singles backdoors of size 2 and found none after 110046 propositions
(edit: there is only one singles backdoor of size 4: [24]2[35]6[47]3[96]8)
Code: Select all
# Ruud's pencilmark only singles backdoor size 4

  13567     12469      2378   |  123579     2345      2678   |   4589     123579    456789
   2589    1346789     1345   | 1234568    23569      1345   | 1346789    124679     1267
   1234      5679      1578   |  235789    14678     23479   |   3568     246789    134789
------------------------------+------------------------------+------------------------------
   3478     35789     145679  |   1578     12347     13479   | 1234567    123469    126789
  134679   12345789    2579   |  14568     234569    25689   |  12456     234578     2356
  12679     13569   123456789 |  234589    24789     13469   |  24589      2378     12349
------------------------------+------------------------------+------------------------------
  35789     25678     346789  |   1359     246789   1245678  |   1459     125679    123569
   1689      5679     12349   |   3468      1369     24589   |  12678     12457     34579
   2459     124578    13567   |  235679     1258     136789  |   3478      4578      3689
Last edited by gsf on Tue Mar 20, 2007 5:45 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Tue Mar 20, 2007 8:50 pm

sirdave wrote:Interesting, but would this have any practical effect on the direction solving methods are going or is it of theoretical interest only. I'd hate to think that it is mistaken by newcomers as a support for solving using only hidden singles and trial and error to find those backdoors.

part of the work/fun in searching for harder puzzles is characterizing what makes the puzzles hard
some of those characterizations take the form of solving techniques, and others more abstract metrics
neither is right or wrong
both can benefit from advances in the other, especially when correlations arise

although using singles may not be the solution technique of choice
right now singles seem to be a reasonable basis for a hardness metric
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby sirdave » Tue Mar 20, 2007 9:34 pm

ravel wrote:There are so much sudokus (about 10^25 non isomorphic ones), that you can find more for each level of difficulty (or allowing an elegant solution using the technique you prefer), than you can solve manually in lifetime.

I dont know anybody, who likes to try each candidate and follow all singles until one is found, that finally solves it.

If I'm not mistaken that is what _m_k is suggesting above in #2 of his solving process.

Puzzles, where this method might be effective, for me are too hard for having fun in solving them manually - and people, who do have, i think, use other methods like nice loops or forcing nets....


Agree completely. I'd hate to have to do it in those puzzles that come to a halt (after basic methods) with 5 candidates or more in most of the cells.:)

btw you seem to have a very restricted definition for nice loops[/i], since each forcing chain and even forcing net can be represented as nice loop also - just look at Carculs solutions).


No, I understand that, though it may have appeared otherwise from my responses above. Perhaps it's just that while I might be perfectly able to represent a double-implication forcing chain that I've found as a nice-loop, at this point in my solving, I find it easier to find a forcing chain in the traditional way which still smacks a bit of trial & error (ie. sequentially plug the values in a source bi-value cell and see if the value in a destination bi-value cell is the same for both source values).
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby sirdave » Tue Mar 20, 2007 9:38 pm

gsf wrote:
sirdave wrote:Interesting, but would this have any practical effect on the direction solving methods are going or is it of theoretical interest only. I'd hate to think that it is mistaken by newcomers as a support for solving using only hidden singles and trial and error to find those backdoors.

part of the work/fun in searching for harder puzzles is characterizing what makes the puzzles hard
some of those characterizations take the form of solving techniques, and others more abstract metrics
neither is right or wrong
both can benefit from advances in the other, especially when correlations arise

although using singles may not be the solution technique of choice
right now singles seem to be a reasonable basis for a hardness metric


Very helpful perspective and that's just what I think needed clarification.
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby wapati » Tue Mar 20, 2007 9:41 pm

sirdave"][quote="ravel wrote: I find it easier to find a forcing chain in the traditional way which still smacks a bit of trial & error (ie. sequentially plug the values in a source bi-value cell and see if the value in a destination bi-value cell is the same for both source values).


I do know that Chains are often "easier"
I admit to using short chains, when I see them in a pattern search.

They are NEVER my first choice.
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada

Postby _m_k » Thu Mar 22, 2007 1:19 am

I am very honored to be quoted in this very important topin on Sudoku; however, since it is taken out of context, I have to clarify my claim for a sake of other readers.

I never claimed:

"Basic elimination + only hidden singles solves most puzzles without recursion or at most 2-level recursion."

but I claim:

"All puzzles can be solved by contradiction chains if recursion is allowed. Depth of recursion will be reduced if some solving techniques are employed in addition to the basic elimination. Typically, I prefer to include only hidden singles [my edit: in contradiction chains and recursion], because with this [my edit: hidden singles. Basic elimanation is understood.] I can solve most puzzles without any recursion or with at most two level recursion."

Whether I recommend contadiction chains to beginners is another matter; however, I do claim:

If there is a contradiction chain (using basic and hidden singles only without recursion), then it is the simplest. and therefore the best, way to explain that a particular candidate can be removed from a certain cell.
[For example, see my posy of March 19, 2007.]

Unfortunately (from my point of view, and therefore fortunately from all "pure" Sudokists' point of view), many of "pure" solving techniques cannot be obtained from contradiction chains using only basic and hidden singles WITHOUT recursion. So these advanced "pure" solving techniques are definitely valuable tools in Sudoku, and I highly recommend beginners to study them

M.K.
_m_k
 
Posts: 13
Joined: 01 February 2007

Postby leon1789 » Thu Mar 22, 2007 6:37 pm

sirdave wrote:Basic elimination + only hidden singles solves most puzzles without recursion or at most 2-level recursion?

An other conjecture.... This method solves all puzzles :
-- only one guess on a bivalue cell or a bilocation number
-- contradiction nets using singles and locked sets in 1-level recursion

for example http://forum.enjoysudoku.com/viewtopic.php?p=39490#p39490
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby udosuk » Thu Mar 22, 2007 10:43 pm

leon1789 wrote:An other conjecture.... This method solves all puzzles :
-- only one guess on a bivalue cell or a bilocation number
-- contradiction nets using singles and locked sets in 1-level recursion

Try to solve this puzzle using your method:
Code: Select all
1.......2
.3..4..5.
..6...7..
...1.3...
.8..7..4.
...4.6...
..2...6..
.5..3..8.
9.......1
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby _m_k » Thu Mar 22, 2007 11:48 pm

Two different ways to find a solution:

Step 1: Use basic, hidden singles, pairs, triples, quads, and locked.
Step 2: Use basic, hidden singles, chains, and recursion.

Solution 1 after Step 1: Four level recusion
Trying 8 at (7, 1): Trying 7 at (2, 1): Trying 4 at (1, 2): Trying 6 at (1, 8):
Solution 2 after Step 1: Four level recusion
Trying 3 at (9, 3): Trying 7 at (2, 1): Trying 4 at (1, 2): Trying 6 at (1, 8):

I see that this must be a difficult puzzle because I need four level of recursion.

M.K.
_m_k
 
Posts: 13
Joined: 01 February 2007

Postby sirdave » Fri Mar 23, 2007 12:45 am

_m_k wrote:Two different ways to find a solution:

Step 1: Use basic, hidden singles, pairs, triples, quads, and locked.
Step 2: Use basic, hidden singles, chains, and recursion.

Solution 1 after Step 1: Four level recusion
Trying 8 at (7, 1): Trying 7 at (2, 1): Trying 4 at (1, 2): Trying 6 at (1, 8):
Solution 2 after Step 1: Four level recusion
Trying 3 at (9, 3): Trying 7 at (2, 1): Trying 4 at (1, 2): Trying 6 at (1, 8):

I see that this must be a difficult puzzle because I need four level of recursion.

M.K.


My main problem is that 'Trying' equals guessing. And the guessing not only involves the choice of which number to plug in, it also applies, for the most part, to the choice of cells to start in. This isn't a judgment on those that want to do it, rather it is making clear to the uninformed what the difference is between the above method and using the methods that go beyond 'locked': fishy strategies, ALC, AICs, nice-loops etc.

Let's take Scrabble as an analogy. I can study all the various 1, 2, 3 and 4 letter words that give the Scrabble player the edge and then along with a good basic vocabulary play regulation Scrabble. Or I can just play with various random combinations of letters until a one of them is accepted. One method is fun, involves skills that are learned and that result in a consistent successful strategy, the other IMO isn't and doesn't.

Tell me where I'm wrong.:D
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

PreviousNext

Return to Advanced solving techniques