Forcing Chains

Advanced methods and approaches for solving Sudoku puzzles

Postby udosuk » Fri Mar 23, 2007 2:58 am

sirdave wrote: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.

I could see how _m_k picked his first cell to guess... After naked quads, swordfish etc you arrive the following state:
Code: Select all
 *--------------------------------------------------------------------*
 | 1      479    45789  | 35789  569    5789   | 3489   369    2      |
 | 278    3      789    | 26789  4      12789  | 189    5      689    |
 | 2458   249    6      | 23589  1259   2589   | 7      139    3489   |
 |----------------------+----------------------+----------------------|
 | 2457   24679  4579   | 1      2589   3      | 2589   2679   5789   |
 | 2356   8      1359   | 259    7      259    | 12359  4      3569   |
 | 2357   1279   3579   | 4      2589   6      | 23589  12379  35789  |
 |----------------------+----------------------+----------------------|
 | 38     147    2      | 5789   159    45789  | 6      379    34579  |
 | 467    5      147    | 2679   3      12479  | 249    8      479    |
 | 9      467    38     | 2578   256    24578  | 2345   237    1      |
 *--------------------------------------------------------------------*

There are only 2 cells with 2 candidates left: r7c1+r9c3={38}

So naturally, he plugged in both 3 & 8 in r7c1, and then in turn he tried out other cells with 2 candidates left to guess his way to the solution... So the choice of cells isn't the issue here... The issue is how he conveniently ignored the fact that the values he didn't pick for (such as 3 in r7c1) didn't lead to obvious contradiction, so it's not a logical approach at all to proceed to the solution...

And it's totally off the point to perform 4 levels of recursion, when this puzzle, like all others discovered so far, needs only 2 levels of recursion with singles to get to the solution (e.g. r19c2=[47])... But even this is off the point, as the special thing about this puzzle is that no 1-level recursion, even using singles, locked sets and naked pairs, can solve this puzzle...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby leon1789 » Fri Mar 23, 2007 6:56 am

udosuk wrote:
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
   123456789
  +----------
A |1.......2
B |.3..4..5.
C |..6...7..
D |...1.3...
E |.8..7..4.
F |...4.6...
G |..2...6..
H |.5..3..8.
K |9.......1



(no initial guess on a bivalue cell or a bilocation number)
10 contradiction nets using singles and locked sets in 0-level recursion
f7#1, b7#8, c6#1, c5#8, f3#1, c9#3, a4#3, h7#4, k7#5, a8#3, finished

_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.

:!:perhaps, there is a misunderstanding on the word "recursion"...
Last edited by leon1789 on Fri Mar 23, 2007 3:10 am, edited 2 times in total.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby udosuk » Fri Mar 23, 2007 7:01 am

leon1789 wrote:(no initial guess on a bivalue cell or a bilocation number)
10 contradiction nets using singles and locked sets in 0-level recursion
f7#1, b7#8, c6#1, c5#8, f3#1, c9#3, a4#3, h7#4, i7#5, a8#3, finished

I made a mistake about "locked sets" (thought it meant "locked candidates")... Your method involving the use of triples & quads in the contradiction nets/chains so of course it's solvable...

Try these puzzles instead:
Code: Select all
.....1.2.
3...4.5..
...6....7
..2.....6
.5..3..8.
4.....9..
9....2...
.8..5.4..
..17.....


.....1.2.
3...4.5..
...6....7
..2.....1
.8..9..3.
4.....8..
5....2...
.9..3.4..
..67.....


5.......9
.2.1...7.
..8...3..
.4.7.2...
....5....
.....6.1.
..3...8..
.6...4.2.
9.......5


..34...8.
.....92..
....6...1
..7.1....
.6...2...
5..8...4.
.1....9..
8......3.
..45....7


..63.....
.4..7....
1....82..
3..9..1..
.7.....4.
..5.....6
9..2....8
....6..5.
.....13..
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby RW » Fri Mar 23, 2007 10:48 am

sirdave wrote: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.

IMO the first option is boring, anything that involves learning a dictionary by heart is boring. The second option leaves room for creativity and invention and leads to interesting, fun and different games every time. While playing scrabble with my friends we have come up with countless good and very useful words that without doubt should be in the dictionary, but for some reason they are not.

Applying a bunch of learned techniques on a sudoku also gets boring for me. I had the most fun solving sudokus the first 6 months, before I read any technique guides or knew anything about online sudoku forums. This was a time of discovery and invention, I constantly found new techniques and methods to make deductions. By the time I found this forum I had pretty much discovered all known techniques already on my own. Lately I haven't solved that many sudokus, because it gets harder and harder to discover anything new the more I've learned. When I see a new variant I usually solve a few of them, as that again lets me come up with a new set of techniques, but when I'm done with that my interest quickly fades away.

When I solve I mostly use forcing chains, because they come in a variety of different shapes and provide the most interesting deductions. Using forcing chains I still every now and then can find patterns that I haven't seen before. Scanning a partially solved grid for a certain known pattern is mechanical and boring and doesn't appeal to me at all.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby udosuk » Fri Mar 23, 2007 6:52 pm

RW wrote:Lately I haven't solved that many sudokus, because it gets harder and harder to discover anything new the more I've learned. When I see a new variant I usually solve a few of them, as that again lets me come up with a new set of techniques, but when I'm done with that my interest quickly fades away.

I feel bored with "Vanilla Sudoku" (meaning normal) puzzles too... But I never get bored with Killer Sudoku, especially those bundle with other variants... Such as this one:
Code: Select all
4........
.....8...
.........
.........
.........
.........
.........
...2.....
........6

X puzzle (no repeating on each diagonal)
Disjoint Group puzzle (no repeating at the same spot of each block)
All mini-rows/mini-cols sum to the same total

Or, if you don't like counting, this one:
Code: Select all
.........
.........
...9.....
.........
.........
.........
.....1...
.........
.........

\ puzzle (no repeating on leading diagonal)
Disjoint Group puzzle (no repeating at the same spot of each block)
Non-cons puzzle (neighbouring cells cannot be consecutive)
Half Windoku (no repeating in r234c234 & r678c678)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby wapati » Fri Mar 23, 2007 9:05 pm

RW wrote:Scanning a partially solved grid for a certain known pattern is mechanical and boring and doesn't appeal to me at all.

RW


Yep, I can relate, as with crossword puzzles.

I am ecstatic when a new word, or one long forgotten, comes to mind.

Your post suggests worse than that. Yep, you should go.


What digit has not been seen??
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada

Postby sirdave » Sat Mar 24, 2007 12:58 am

RW wrote:This was a time of discovery and invention, I constantly found new techniques and methods to make deductions. By the time I found this forum I had pretty much discovered all known techniques already on my own. Lately I haven't solved that many sudokus, because it gets harder and harder to discover anything new the more I've learned. When I see a new variant I usually solve a few of them, as that again lets me come up with a new set of techniques...

RW


Well, don't keep them all to yourself. How about sharing some of them!
Edit: added:D smiley.
Last edited by sirdave on Sat Mar 24, 2007 11:51 am, edited 2 times in total.
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby udosuk » Sat Mar 24, 2007 8:54 am

sirdave wrote:Well, don't keep them all to yourself. How about sharing some of them!

RW has been sharing many great ingenious new techniques in the General/puzzle & Advanced solving techniques sections... And probably in other forums... One example is when Gurth posted his emeralds (symmetrical puzzles) RW was inventing quite a few nice new techniques on them (I contributed a bit too)...


Regarding the 2 puzzles I posted (4 & 2 clues respectively), they both had unique solutions (no extra digits were needed)... I was hoping the forcing chains and T&E specialists can demonstrate how to solve them... Would gsf's programs crack them?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby sirdave » Sat Mar 24, 2007 3:50 pm

udosuk wrote:
sirdave wrote:Well, don't keep them all to yourself. How about sharing some of them!

RW has been sharing many great ingenious new techniques in the General/puzzle & Advanced solving techniques sections... And probably in other forums... One example is when Gurth posted his emeralds (symmetrical puzzles) RW was inventing quite a few nice new techniques on them (I contributed a bit too)...


Yeah, I know- it was my poor attempt at being humorous- I should have put a smiley on my post. I thought his post suggested that he had a few he wasn't telling us about.:D
sirdave
2010 Supporter
 
Posts: 36
Joined: 04 January 2006

Postby _m_k » Sat Mar 24, 2007 4:12 pm

Udosuk:

I did not ignore that the other choices will lead to a contradiction. I did not wish to mention them because they were very long: 19 tries are required for Trying 3 at (7, 1).

Your new puzzles:
Solutions using only minimum size cells:

Puzzle 1: 306 tries
Trying 5 at (1, 4): Trying 8 at (3, 7): Trying 3 at (1, 7): Trying 9 at (1, 9): Trying 7 at (1, 5): Trying 6 at (1, 1): Trying 7 at (2, 3):
Trying 3 at (3, 6): Trying 8 at (3, 7): Trying 3 at (1, 7): Trying 9 at (1, 9): Trying 7 at (1, 5): Trying 6 at (1, 1): Trying 7 at (2, 3):

Puzzle 2: 4042 tries
Trying 9 at (7, 4): Trying 8 at (2, 4): Trying 5 at (1, 4): Trying 6 at (1, 2): Trying 8 at (1, 1):
Trying 4 at (9, 6): Trying 8 at (2, 4): Trying 5 at (1, 4): Trying 6 at (1, 2): Trying 8 at (1, 1):

Puzzle 3: 706 tries
Trying 2 at (1, 7): Trying 9 at (3, 2): Trying 6 at (2, 3): Trying 3 at (2, 1): Trying 1 at (1, 2): Trying 4 at (1, 3): Trying 8 at (1, 8): Trying 6 at (1, 4): Trying 7 at (1, 5): Trying 8 at (2, 5): Trying 4 at (3, 4):
Trying 1 at (3, 9): Trying 9 at (3, 2): Trying 6 at (2, 3): Trying 3 at (2, 1): Trying 1 at (1, 2): Trying 4 at (1, 3): Trying 8 at (1, 8): Trying 6 at (1, 4): Trying 7 at (1, 5): Trying 8 at (2, 5): Trying 4 at (3, 4):
Trying 4 at (7, 1): Trying 2 at (1, 7): Trying 3 at (2, 1): Trying 1 at (1, 2): Trying 7 at (3, 1): Trying 4 at (1, 3): Trying 8 at (1, 8): Trying 6 at (1, 4): Trying 7 at (1, 5): Trying 8 at (2, 5): Trying 4 at (3, 4):
Trying 2 at (9, 3): Trying 2 at (1, 7): Trying 3 at (2, 1): Trying 1 at (1, 2): Trying 7 at (3, 1): Trying 4 at (1, 3): Trying 8 at (1, 8): Trying 6 at (1, 4): Trying 7 at (1, 5): Trying 8 at (2, 5): Trying 4 at (3, 4):

Puzzle 4: 360 tries
Trying 3 at (2, 9): Trying 1 at (2, 4): Trying 7 at (1, 6): Trying 5 at (1, 5):
Trying 4 at (3, 7): Trying 1 at (2, 4): Trying 7 at (1, 6): Trying 5 at (1, 5):
Trying 5 at (4, 6): Trying 7 at (1, 6): Trying 5 at (1, 5): Trying 8 at (2, 5):
Trying 4 at (5, 5): Trying 7 at (1, 6): Trying 5 at (1, 5): Trying 8 at (2, 5):

Puzzle 5: 388 tries
Trying 9 at (5, 3): Trying 3 at (3, 3): Trying 2 at (2, 3): Trying 5 at (2, 1): Trying 9 at (1, 8): Trying 4 at (1, 7): Trying 2 at (1, 6): Trying 1 at (1, 5):
Trying 1 at (6, 2): Trying 3 at (3, 3): Trying 2 at (2, 3): Trying 5 at (2, 1): Trying 9 at (1, 8): Trying 4 at (1, 7): Trying 2 at (1, 6): Trying 1 at (1, 5):

Solutions with minimum tries using all cells:

Puzzle 1: 46335 tries
Trying 7 at (1, 5): Trying 2 at (5, 4):
29 more solutions with two tries

Puzzle 2: 48492 tries
Trying 8 at (2, 4): Trying 5 at (9, 5):
55 more solutions with two tries

Puzzle 3: 52652 tries
Trying 4 at (9, 8): Trying 9 at (2, 6):
5 more solutions with two tries

Puzzle 4: 44488 tries
Trying 5 at (1, 5): Trying 7 at (5, 7):
27 more solutions with two tries

Puzzle 5: 48581 tries
Trying 7 at (4, 8): Trying 8 at (2, 7):
Trying 8 at (2, 7): Trying 7 at (4, 8):
Trying 3 at (7, 2): Trying 5 at (4, 6):
Trying 5 at (4, 6): Trying 3 at (7, 2):
Last edited by _m_k on Sat Mar 24, 2007 10:56 pm, edited 1 time in total.
_m_k
 
Posts: 13
Joined: 01 February 2007

Postby udosuk » Sat Mar 24, 2007 5:04 pm

_m_k,

Those aren't my puzzles... I just picked them from this thread some puzzles which are proved to be good work-outs for T&E players... Looks like on St Patrick Day there were a new batch of puzzles produced which are more difficult than those 5...:!:

Looks like you're using a program to find all those "2-tries/guesses" solutions... gsf's programs would do the same thing... I was sort of expecting the forcing chain/T&E experts could demonstrate some "1-try/guess" solutions...:!:

_m_k wrote:I did not ignore that the other choices will lead to a contradiction. I did not wish to mention them because they were very long: 19 tries are required for Trying 3 at (7, 1).

Wouldn't that makes your solving process 19-level recursion? What kind of human would perform this manually?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby _m_k » Sat Mar 24, 2007 11:53 pm

Udosuk:
I did give 1-try/guess solutions! There were no 1-try solutions, but all 2-try solutions are listed.

It is interesting to note how many tries are requed to find minimum cell soltions and to find the minimum try solutions. The minimum try solution is of greatest theoritical interest, but it requires much more tries than minimum cell solutions.

I should have stated that it takes 19 sets of recursion steps (each from 3 to 7 levels of recursion) to show that other choices will lead to a contradiction. I know that is too much for humans.

Leon1789:
Will you please explain the following? It sounds interesting and I like to learn in detail.

10 contradiction nets using singles and locked sets in 0-level recursion
f7#1, b7#8, c6#1, c5#8, f3#1, c9#3, a4#3, h7#4, k7#5, a8#3, finished

Anyone:
Are there any difference between guessing, trial & error, and forcing chain?
_m_k
 
Posts: 13
Joined: 01 February 2007

Postby gsf » Sun Mar 25, 2007 1:45 am

udosuk wrote:... Would gsf's programs crack them?

the basic sudoku constraints are pretty well ingrained in my code
it would be straightforward to add additional bitmask constraints like X or DG
(I did this with my NxN pseudocoup)
but functional constraints would take a different tactic from the first byte of code
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby udosuk » Sun Mar 25, 2007 4:24 am

_m_k:

Your "2-try solutions" are equivalent to the "backdoor twins" as discussed by gsf much earlier to this... All sudoku puzzles (discovered so far) have backdoor twins (under singles), and it's not difficult at all to write a program to find them all, so it's hardly any achievement...

More preferably, one should pick 2 cells with 2-3 candidates each, and show that all other choices of candidates lead to contradiction (using logic as simple as possible, such as singles only). That's way better than saying "if I pick cell A as x and cell B as y, I will reach the solution"...

And, if it takes 7 levels of recursion to prove a contradiction, I don't think it's a legitimate solving process at all...


gsf:

If by "functional constraints" you mean something like "sum of mini-rows" or "non-consecutiveness" then I agree... Because without these you cannot have a puzzle with fewer than 8 clues (free permutation of symbols is allowed)...

I was speculating how much work would take you to implement "non-consecutiveness" in your program... The logic would go like "if cell A is x, then eliminate x-1,x+1 from all 4 neighbours of cell A"...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Sun Mar 25, 2007 7:54 am

udosuk wrote:gsf:

If by "functional constraints" you mean something like "sum of mini-rows" or "non-consecutiveness" then I agree... Because without these you cannot have a puzzle with fewer than 8 clues (free permutation of symbols is allowed)...

I was speculating how much work would take you to implement "non-consecutiveness" in your program... The logic would go like "if cell A is x, then eliminate x-1,x+1 from all 4 neighbours of cell A"...

I almost replied that it would be easy
for solving it would be -- just some extra bitmask operations for each assignment
but for generation it would be a problem because the bitmask ops I have are their own inverse
i.e., assigning a value to a cell involves some bitmask ops on the 4 9-bit cell/row/col/box masks
undoing that assigment is the same sequence of bitmask ops
undoing a non-consecutive assignment would involve looking at the neighborhood of the cell
and a fast undo is essential for generation that starts with a full grid
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

PreviousNext

Return to Advanced solving techniques