The New Sudoku Players' Forum

[leon1789]

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.

[udosuk]

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

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]

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

[leon1789]

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 )

[gsf]

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

[udosuk]

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?

[gsf]

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


[udosuk]

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?

[leon1789]

Try these puzzles instead (...)

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

[udosuk]

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

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

[gsf]

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

[leon1789]

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.

[ronk]

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

[leon1789]

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 ?

[ronk]

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