Forcing Chains

Advanced methods and approaches for solving Sudoku puzzles

Postby leon1789 » Sun Mar 25, 2007 2:54 pm

_m_k wrote: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

C#z means C=z is a disproved move by a contradiction net using singles, triples, quads... so -zC is proved.
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

Starting point : try f7=1 and find a quick contradiction (using singles, triples, quads). So f7#1 definitively.
Now, try b7=8 and find a contradiction. So b7#8 definitively.
And so on... c6#1, c5#8, f3#1, c9#3, a4#3, h7#4, k7#5, a8#3, and finish (using singles, triples, quads).

At the end, a unique solution is find and proved , and there are no recusion, but only 10 iterative steps :
Code: Select all
  if f7=1
  then contradiction
  therefore f7#1
  if b7=8
  then contradiction
  therefore b7#8
  if c6=1
  then contradiction
  therefore c6#1
  ...
  if a8=3
  then contradiction
  therefore a8#3
  finally a singles,triples,quads application leads to a solution


The "2 backdoor guess" does not prove the uniqueness of the solution : for me, it's a big difference between a simple guessing (no proof) and a dynamic forcing chain (valid proof).

I will post solutions for the five puzzles, but they are a little bit hard.:) Here, 1-level recursion is obligatory.
Last edited by leon1789 on Sun Mar 25, 2007 11:05 am, edited 1 time in total.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby udosuk » Sun Mar 25, 2007 3:05 pm

leon1789 wrote:At the end, a unique solution is find and proved , and there are no recusion, but only 10 iterative steps.

The "2 backdoor guess" does not prove the uniqueness : for me, it's a difference between a simple guessing (no proof) and a dynamic forcing chain (valid proof).

Correct. You used forcing chains involving triples/quads (or hidden pairs) to solve that puzzle without any recursion, so it's definitely a logically legit way to solve this puzzle properly (instead of trying to guess your way to the solution grid)...

The tricky thing about that puzzle is you cannot solve it merely by forcing chains with singles/locked candidates/naked pairs without recursion...

leon1789 wrote:I will post solutions for the five puzzles, but they are a little bit hard.:)

If you can solve any of those 5 puzzles without recursion, it will give you a lot of kudos and respect in this forum... So do go for it...:!:
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby udosuk » Sun Mar 25, 2007 3:15 pm

gsf wrote:
udosuk wrote: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

Okay, how long would it take you to write a program to verify that the following non-cons DG X puzzle has a unique solution, and find that solution?
Code: Select all
142......
.........
.........
.........
.........
.........
.........
.........
.........
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby leon1789 » Sun Mar 25, 2007 3:50 pm

udosuk wrote:If you can solve any of those 5 puzzles without recursion, it will give you a lot of kudos and respect in this forum... So do go for it...:!:

With this method (dynamic contradiction chain involving locked sets), I need one level recursion (and only one) on a bivalue cell or a bilocation number in order to prove the solution.

However, with an advanced mathematical method, I think it's possible to have no recursion. But it's an other story...:)
Remark : dynamic contradiction chains involving locked sets are a particular case of a general als technique.
(sorry for my poor english:( )
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby gsf » Mon Mar 26, 2007 10:40 am

udosuk wrote:Okay, how long would it take you to write a program to verify that the following non-cons DG X puzzle has a unique solution, and find that solution?
Code: Select all
142......
.........
.........
.........
.........
.........
.........
.........
.........

1.5 sec @ 2Ghz singles forward check search
142597368795863142368241795836415279279638514514972836951724683427386951683159427
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby udosuk » Mon Mar 26, 2007 1:20 pm

gsf wrote:1.5 sec @ 2Ghz singles forward check search

Marvellous! You're great!:)

I don't suppose it's too much to ask if your program can find a small set of backdoor cells (prefereably minimal) to reach the solution?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Mon Mar 26, 2007 4:09 pm

udosuk wrote:
gsf wrote:1.5 sec @ 2Ghz singles forward check search

Marvellous! You're great!:)

I don't suppose it's too much to ask if your program can find a small set of backdoor cells (prefereably minimal) to reach the solution?

the singles backdoor size is 4 (minimal by definition)
there are 12 singles backdoors
determining the singles backdoors took 3 extra sec
Code: Select all
# 4 [21]=7 [43]=6 [61]=5 [86]=6
# 4 [21]=7 [61]=5 [77]=6 [86]=6
# 4 [24]=8 [26]=3 [42]=3 [59]=4
# 4 [24]=8 [26]=3 [44]=4 [68]=3
# 4 [24]=8 [26]=3 [45]=1 [68]=3
# 4 [24]=8 [26]=3 [68]=3 [75]=2
# 4 [24]=8 [42]=3 [66]=2 [84]=3
# 4 [24]=8 [77]=6 [84]=3 [95]=5
# 4 [32]=6 [43]=6 [61]=5 [86]=6
# 4 [32]=6 [61]=5 [77]=6 [86]=6
# 4 [58]=1 [67]=8 [76]=4 [79]=3
# 4 [61]=5 [77]=6 [86]=6 [91]=6
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby udosuk » Tue Mar 27, 2007 5:34 am

Excellent! The impressive running time is probably due to your great programming skills...

I'm sure HATMAN will be glad (he discovered a lot of puzzles like these)... So essentially they can be a range of 7-clue singles-only puzzles...

Would you like to make your program available to the public?
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby leon1789 » Tue Mar 27, 2007 2:20 pm

udosuk wrote:Try these puzzles instead (...)

leon1789 wrote:I will post solutions for the five puzzles, but they are a little bit hard.:) Here, 1-level recursion is obligatory.


Method :
-- only one guess on a bivalue cell or a bilocation number
-- (in 1-level recursion) contradiction nets using locked sets (singles, triples, quads, etc.).

Conjecture : this method solves all puzzles.

Coordinates :

Code: Select all
  123456789
 +---------
a|
b|
c|
d|   
e|
f|
g|
h|
k|

---------------------------------------------

A solution for "Ocean Christmas present for gsf" (in 31 eliminations)

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


if b4=2 then
f4#5, d4#8, f3#8, g4#3, g9#1, c1#2, f4#1, b9#8, b3#9, c8#9, b6#8, b6#9, k7#2, contradiction

so b2=2, and then
c7#1, c8#1, d8#1, b9#8, b3#9, b3#8, d6#7, f4#5, a5#8, a3#9, d2#9, g7#3, c2#1, c8#9, a9#3, b8#1, h9#2, b3#6, finished

---------------------------------------------
A solution for "Ocean's New Year's present for RW" (in 45 eliminations, a record for me !)

Code: Select all
.....1.2.
3...4.5..
...6....7
..2.....1
.8..9..3.
4.....8..
5....2...
.9..3.4..
..67.....


if f5=2 then
k2#1, d8#7, a2#4, d2#7, h4#1, a3#7, g7#3, h9#5, g3#1, d8#6, d2#6, k2#3, d5#5, k9#2, h9#6, k7#2, d5#7, c2#2, b8#9, g2#3, g5#6, c5#8, contradiction,

so c5=2, and then
c6#9, b9#9, a7#6, d4#4, d6#3, e9#6, b8#9, d8#6, f3#1, a9#3, k9#2, d6#7, h8#1, a9#6, c7#1, b3#1, g2#4, f4#3, c3#4, e4#2, e6#4, k7#2, a3#4, finished

---------------------------------------------

A solution for "m_b_metcalf" (in 30 eliminations)

Code: Select all
5.......9
.2.1...7.
..8...3..
.4.7.2...
....5....
.....6.1.
..3...8..
.6...4.2.
9.......5


if a2=3 then
c2#9, d8#9, b5#4, c5#9, b5#6, d8#6, g4#5, c4#2, a3#7, d8#8, d7#5, c5#7, e8#9, d5#9, f5#9, c4#9, c9#1, h4#3, g6#7, contradiction

so b1=3, and then
b3#9, h4#9, b7#6, b6#5, e8#8, c4#5, f2#5, d7#9, c9#2, d1#8, c1#4, finished

---------------------------------------------

A solution for "dml 3/07 3.070533s" (in 27 eliminations)

Code: Select all
..34...8.
.....92..
....6...1
..7.1....
.6...2...
5..8...4.
.1....9..
8......3.
..45....7


if a5=2 then
b5#3, c2#8, c1#4, e8#9, b3#1, f9#3, e9#3, c7#3, h4#1, f7#3, d8#9, b2#8, c6#3, c3#8, a6#5, contradiction

so c4=2, and then
c6#5, a2#5, k6#1, g5#8, b5#5, c8#9, e8#7, b3#8, h7#1, f5#9, a6#5, e4#7, finished

---------------------------------------------

A solution for "??" (in 36 eliminations)

Code: Select all
..63.....
.4..7....
1....82..
3..9..1..
.7.....4.
..5.....6
9..2....8
....6..5.
.....13..


if c3=7 then
e4#8, g2#3, d6#2, a2#5, f4#1, c2#5, k1#8, d6#7, f7#7, b6#6, b4#1, b4#5, c2#9, b8#1, contradiction

so a1=7,and then
h9#7, b3#3, c9#3, c8#3, c5#9, a5#5, k8#7, c9#9, b3#9, b8#1, c8#9, b7#5, k1#5, f8#7, e4#8, a6#5, b7#6, c8#7, k2#6, b3#8, a7#5, a8#1, finished
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby udosuk » Tue Mar 27, 2007 5:47 pm

Impressive. Although they're solving processes of 2-level T&E, you made them systematical by restricting the 1st branching on bi-value cells/strong links and insisted on testing both branches. I think it's the next best thing than solving them with 1-level T&E... Bear in mind many of them are SE 11+ puzzles...:!:
leon1789 wrote:A solution for "??" (in 36 eliminations)
Code: Select all
..63.....
.4..7....
1....82..
3..9..1..
.7.....4.
..5.....6
9..2....8
....6..5.
.....13..

This was in fact just an isomorph of dml 1/07 (SE 11.1, gsf 99998):
Code: Select all
..3.....9
4......2.
.8.6..1..
2....4...
.9.8....7
..5.3....
...9..8..
.....5.3.
.7..1...6

So well done for solving that too...

If you need more data to test your conjecture just check out the last 2 pages of "The hardest sudokus" thread... For example, you can try coloin's St.Patrick-16, which has the top gsfQ rating (most complicated under singles propositions)...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Tue Mar 27, 2007 6:59 pm

leon1789 wrote:A solution for "Ocean Christmas present for gsf" (in 31 eliminations)

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


if b4=2 then
f4#5, d4#8, f3#8, g4#3, g9#1, c1#2, f4#1, b9#8, b3#9, c8#9, b6#8, b6#9, k7#2, contradiction

can you describe the exact logic behind
Code: Select all
if b4=2 then f4#5

using locked sets (singles, triples, quads, etc.)
here's the pencilmark grid after the b4=2 assignment
Code: Select all
 5678   4679  456789 | 3589    789     1   |  368     2    3489 
   3    1679   6789  |   2      4     789  |   5     169    189 
 1258   1249   4589  |   6     89    3589  |  138   1349     7   
---------------------+---------------------+---------------------
  178   1379     2   | 14589  1789   45789 |  137   13457    6   
  167     5     679  |  149     3    4679  |  127     8     124 
   4    1367   3678  |  158   12678  5678  |   9    1357   1235 
---------------------+---------------------+---------------------
   9    3467   34567 | 1348    168     2   | 13678  13567  1358 
  267     8     367  |  139     5     369  |   4    13679  1239 
  256   2346     1   |   7     689   34689 | 2368   3569   23589

thanks
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby leon1789 » Tue Mar 27, 2007 8:10 pm

gsf wrote:can you describe the exact logic behind
Code: Select all
if b4=2 then f4#5

using locked sets (singles, triples, quads, etc.)

Try b4=2... Then a big Dynamic Contradiction Forcing Chain begining with f4=5 and using singles (for this example), disproves f4=5.
-- only one guess on a bivalue cell or a bilocation number
-- (in 1-level recursion) contradiction nets using locked sets (singles, triples, quads, etc.).

Contradiction nets using locked sets (singles, triples, quads, etc.) are particular cases of general als technique.
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby ronk » Tue Mar 27, 2007 8:52 pm

leon1789 wrote:
Code: Select all
.....1.2.
3...4.5..
...6....7
..2.....6
.5..3..8.
4.....9..
9....2...
.8..5.4..
..17.....


if b4=2 then
f4#5, d4#8, f3#8, g4#3, g9#1, c1#2, f4#1, b9#8, b3#9, c8#9, b6#8, b6#9, k7#2, contradiction

You choose b4=2 because it is a bilocation number. But then you choose f4#5, which appears to be neither a bivalue nor a bilocation number. What is the rationale for that choice:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby leon1789 » Wed Mar 28, 2007 5:21 pm

ronk wrote:You choose b4=2 because it is a bilocation number. But then you choose f4#5, which appears to be neither a bivalue nor a bilocation number. What is the rationale for that choice:?:


First :
In the recursion level, if you want absolutely to choose a bivalue ceils or bilocation numbers, it's possible that you can't prove anything : some puzzles are very hard... So, it's logical to enlarge the choice with all candidates in order to have a good conjecture:)

Second :
The classical als technique operates with any almost locked set (not only bivalue ceils, etc.). So there is no raison to analyse only bivalue ceils and bilocation numbers, isn't it ?:)
leon1789
 
Posts: 37
Joined: 15 November 2006

Postby ronk » Wed Mar 28, 2007 5:39 pm

leon1789 wrote:
ronk wrote:You choose b4=2 because it is a bilocation number. But then you choose f4#5, which appears to be neither a bivalue nor a bilocation number. What is the rationale for that choice:?:


First :
In the recursion level, if you want absolutely to choose a bivalue ceils or bilocation numbers, it's possible that you can't prove anything : some puzzles are very hard... So, it's logical to enlarge the choice with all candidates in order to have a good conjecture:)

Second :
The classical als technique operates with any almost locked set (not only bivalue ceils, etc.). So there is no raison to analyse only bivalue ceils and bilocation numbers, isn't it ?:)

I don't see an answer to my question in there anywhere. Are you saying f4#5 is part of an almost-locked-set (ALS):?: If so, please identify the ALS.

If not part of an ALS, what made f4#5 a more promising number to try than any other:?:
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques

cron