One flew over the backdoors

Everything about Sudoku that doesn't fit in one of the other sections

Re: The hardest sudokus (new thread)

Postby dobrichev » Thu Dec 06, 2012 9:14 pm

ronk wrote:Andrew Stuart has proposed the number of quads backdoors of maximum size as a new metric for difficult puzzles.

"Quads backdoors" means, in addition to the backdoors guesses, the techniques used are singles, locked candidates, naked and hidden subsets (pairs, triples, and quads).

Limiting the techniques to singles, the "level" distribution for latest champagne's collection of hardest is
Code: Select all
   7505 1
 594036 2
   4744 3
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

backdoor 3 in singles

Postby dobrichev » Mon Jan 07, 2013 7:14 pm

Hi,

Please somebody confirm that this family of puzzles has low rating but has backdoor of size 3 when limiting the techniques to singles.
Code: Select all
........1.....2.3.....4.5.6..1.6.7.5..6.5.1...8.....9...541.....3.......9....8... ED=5.6/1.2/1.2
........1.....2.3.....4.5.6..1.6.7.5..6.5.1...8.....9...541.....3.......2....9... ED=5.6/1.2/1.2
........1.....2.3.....4.5.6..1.5.6....7.6.1.5.8.....9...641.....3.......2....9... ED=5.6/1.2/1.2
........1.....2.3.....4.5.6..1.5.6....7.6.1.5.8.....9...541.....3.......2....9... ED=5.6/1.2/1.2
........1.....2.3.....4.5.6..1.5.6....5.6.1.7.8.....9...641.....9.......2....9... ED=5.6/1.2/1.2
........1.....2.3.....4.5.6..1.5.6....5.6.1.7.3.....8...641.....9.......2....9... ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..2..6....4.17....6..........6....8..5..4.1...7..5.9.4 ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...7.....8...419.....3.......8....7... ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...7.....8...419.....3.......2....8... ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...2.....7...418.....7.......3....7... ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..1.4.5....6.5.1.4.7.....8...519.....3.......2....8... ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..1.4.5....6.5.1.4.7.....8...419.....3.......2....8... ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....8.......3....7... ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....8.......2....8... ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....2.......3....7... ED=5.6/1.2/1.2
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.3.....7...518.....9.......2....9... ED=5.6/1.2/1.2
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: The hardest sudokus (new thread)

Postby coloin » Mon Jan 07, 2013 8:55 pm

This is the result of gsf's -q2 command

Code: Select all
c:\Suxx>sudoku-64 -q2 test1.txt
........1.....2.3.....4.5.6..1.6.7.5..6.5.1...8.....9...541.....3.......9....8... #  1447 FNBP C21.m/M2.11.12516
........1.....2.3.....4.5.6..1.6.7.5..6.5.1...8.....9...541.....3.......2....9... #  1223 FNBP C21.m/M3.3157.168
........1.....2.3.....4.5.6..1.5.6....7.6.1.5.8.....9...641.....3.......2....9... #   605 FNBP C21.m/M2.77.340
........1.....2.3.....4.5.6..1.5.6....7.6.1.5.8.....9...541.....3.......2....9... #   605 FNBP C21.m/M2.77.340
........1.....2.3.....4.5.6..1.5.6....5.6.1.7.8.....9...641.....9.......2....9... #  1036 FNBP C21.m/M2.22.5960
........1.....2.3.....4.5.6..1.5.6....5.6.1.7.3.....8...641.....9.......2....9... #   796 FNBP C21.m/M2.44.2831
........1.....2.3.....1.4.5..2..6....4.17....6..........6....8..5..4.1...7..5.9.4 #   489 FNBP C21.m/M2.18.2548
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...7.....8...419.....3.......8....7... #  1058 FNBP C21.m/M3.1298.409
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...7.....8...419.....3.......2....8... #   911 FNBP C21.m/M3.2376.223
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...2.....7...418.....7.......3....7... #   558 FNBP C21.m/M2.11.23840
........1.....2.3.....1.4.5..1.4.5....6.5.1.4.7.....8...519.....3.......2....8... #   552 FNBP C21.m/M2.55.2023
........1.....2.3.....1.4.5..1.4.5....6.5.1.4.7.....8...419.....3.......2....8... #   552 FNBP C21.m/M2.55.2023
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....8.......3....7... #  1103 FNBP C21.m/M3.1133.469
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....8.......2....8... #   851 FNBP C21.m/M2.22.5662
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....2.......3....7... #   838 FNBP C21.m/M3.2002.265
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.3.....7...518.....9.......2....9... #   634 FNBP C21.m/M2.33.3366


i always thought M3 meant backdoor of size 3 - but it depends where you limit your techniques......

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: The hardest sudokus (new thread)

Postby dobrichev » Mon Jan 07, 2013 9:29 pm

So only 5 of them are M3, but based on techniques including "B", which gsf explains as "Box claim" which is above "singles". Am I right?

Glenn?
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: The hardest sudokus (new thread)

Postby eleven » Mon Jan 07, 2013 9:44 pm

coloin wrote: - but it depends where you limit your techniques......C

In the manpage gsf's writes, that the default for his backdoor search is FNBTHW (FN singles, B box-line, TH tuples, W x-wing swordfish).
[Edit: no, those options bring backdoor size 1, and FNB 1 or 2, don't know, what is used for q2]

Here is the output for -qFN, which confirms the backdoor sizes 3:
Code: Select all
........1.....2.3.....4.5.6..1.6.7.5..6.5.1...8.....9...541.....3.......9....8... # 99629 FNG C21.m/M3.1892.280
........1.....2.3.....4.5.6..1.6.7.5..6.5.1...8.....9...541.....3.......2....9... # 99513 FNG C21.m/M3.1562.340
........1.....2.3.....4.5.6..1.5.6....7.6.1.5.8.....9...641.....3.......2....9... # 99405 FNG C21.m/M3.2189.242
........1.....2.3.....4.5.6..1.5.6....7.6.1.5.8.....9...541.....3.......2....9... # 99405 FNG C21.m/M3.2189.242
........1.....2.3.....4.5.6..1.5.6....5.6.1.7.8.....9...641.....9.......2....9... # 99485 FNG C21.m/M3.2431.218
........1.....2.3.....4.5.6..1.5.6....5.6.1.7.3.....8...641.....9.......2....9... # 99408 FNG C21.m/M3.2442.217
........1.....2.3.....1.4.5..2..6....4.17....6..........6....8..5..4.1...7..5.9.4 # 99554 FNG C21.m/M3.1553.342
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...7.....8...419.....3.......8....7... # 99503 FNG C21.m/M3.1221.435
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...7.....8...419.....3.......2....8... # 99490 FNG C21.m/M3.1122.473
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...2.....7...418.....7.......3....7... # 99442 FNG C21.m/M3.1496.355
........1.....2.3.....1.4.5..1.4.5....6.5.1.4.7.....8...519.....3.......2....8... # 99414 FNG C21.m/M3.1628.326
........1.....2.3.....1.4.5..1.4.5....6.5.1.4.7.....8...419.....3.......2....8... # 99414 FNG C21.m/M3.1628.326
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....8.......3....7... # 99573 FNG C21.m/M3.1133.469
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....8.......2....8... # 99472 FNG C21.m/M3.1826.291
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....2.......3....7... # 99470 FNG C21.m/M3.1936.274
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.3.....7...518.....9.......2....9... # 99441 FNG C21.m/M3.1771.300
eleven
 
Posts: 1534
Joined: 10 February 2008

Re: The hardest sudokus (new thread)

Postby coloin » Mon Jan 07, 2013 10:10 pm

So -q1 would have been more appropriate. Thanks eleven.
Code: Select all
c:\Suxx>sudoku-64 -q1 test1.txt
........1.....2.3.....4.5.6..1.6.7.5..6.5.1...8.....9...541.....3.......9....8... #  3798 FNP C21.m/M3.1892.280
........1.....2.3.....4.5.6..1.6.7.5..6.5.1...8.....9...541.....3.......2....9... #  3335 FNP C21.m/M3.1562.340
........1.....2.3.....4.5.6..1.5.6....7.6.1.5.8.....9...641.....3.......2....9... #  1072 FNP C21.m/M3.2189.242
........1.....2.3.....4.5.6..1.5.6....7.6.1.5.8.....9...541.....3.......2....9... #  1072 FNP C21.m/M3.2189.242
........1.....2.3.....4.5.6..1.5.6....5.6.1.7.8.....9...641.....9.......2....9... #  2236 FNP C21.m/M3.2431.218
........1.....2.3.....4.5.6..1.5.6....5.6.1.7.3.....8...641.....9.......2....9... #  3484 FNP C21.m/M3.2442.217
........1.....2.3.....1.4.5..2..6....4.17....6..........6....8..5..4.1...7..5.9.4 #  1803 FNP C21.m/M3.1553.342
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...7.....8...419.....3.......8....7... #  1010 FNP C21.m/M3.1221.435
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...7.....8...419.....3.......2....8... #  1032 FNP C21.m/M3.1122.473
........1.....2.3.....1.4.5..1.5.6.4..5.4.1...2.....7...418.....7.......3....7... #   937 FNP C21.m/M3.1496.355
........1.....2.3.....1.4.5..1.4.5....6.5.1.4.7.....8...519.....3.......2....8... #   424 FNP C21.m/M3.1628.326
........1.....2.3.....1.4.5..1.4.5....6.5.1.4.7.....8...419.....3.......2....8... #   424 FNP C21.m/M3.1628.326
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....8.......3....7... #   892 FNP C21.m/M3.1133.469
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....8.......2....8... #  1021 FNP C21.m/M3.1826.291
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.7.....8...519.....2.......3....7... #  1039 FNP C21.m/M3.1936.274
........1.....2.3.....1.4.5..1.4.5....4.5.1.6.3.....7...518.....9.......2....9... #   776 FNP C21.m/M3.1771.300

C
coloin
 
Posts: 1629
Joined: 05 May 2005

Re: The hardest sudokus (new thread)

Postby ronk » Thu Jan 10, 2013 2:46 am

dobrichev wrote:What "mm" and "nn" are?

I believe gsf will not object to this quote of a private message from 2011.

gsf wrote:
ronk wrote:What do the last two numbers (the '60' and '109') below mean?
Code: Select all
..1.....2.5...3.4.6.....7......2.....8.9.6.3....5.8.....2...1...3.4...5.7.......6 # 74201 FNBP C21.m/M2.60.109
Do the meanings change for -q1, -q2, and neither of these two?

the last tuple is M(M).(M1).(M2)
you can see the descriptions for M,M1,M2 under EXPRESSIONS
M: (backdoor) The backdoor (magic cell set) size
M1: (magic) The number of backdoors (magic cell sets).
M2: (guesstimate) The estimated number of guesses before a backdoor hit.

backdoors depend on the constraints in scope, so different M,M1,M2 values for -q1 vs -q2 -qsomething-else is possible
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

M3

Postby dobrichev » Thu Jan 10, 2013 8:56 am

tarek wrote:I'm not sure who is keeping track of all posted singles M3 puzzles. They used to be quite rare in 2007 before their numbers exploded!!!

Not me.
tarek wrote:What comes next is to see what singles M3 puzzle has the least number of backdoor triplets. Could there be a puzzle with only 1 singles backdoor triplet? A search in the neighbourhood of that puzzle might bring some unexpected results

gsf wrote:
ronk wrote:What do the last two numbers (the '60' and '109') below mean?
Code: Select all
..1.....2.5...3.4.6.....7......2.....8.9.6.3....5.8.....2...1...3.4...5.7.......6 # 74201 FNBP C21.m/M2.60.109
Do the meanings change for -q1, -q2, and neither of these two?

the last tuple is M(M).(M1).(M2)
you can see the descriptions for M,M1,M2 under EXPRESSIONS
M: (backdoor) The backdoor (magic cell set) size
M1: (magic) The number of backdoors (magic cell sets).
M2: (guesstimate) The estimated number of guesses before a backdoor hit.

So "mm" or (M1) is the number of backdoor triplets in question. Thank you, ronk.

Two questions arose
1) Could the order of selection of the backdoor cells affect the backdoor size or the number of triplets?
2) Are there additional rules in estimation of "nn" such as "try bivalues first" or it is assumed that some cell is blindly guessed to some value within its pencilmarks?

The answer to the first question is likely to be "no" but I am prepared for any surprises from sudoku.

Regardless the existence or non-existence of additional rules/constrains involved in "nn" calculation, this property looks fragile.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

M3

Postby dobrichev » Fri Jan 11, 2013 9:22 am

Backdoors of size 3 in singles are not so rare. I have collected about 100K of them in 21-25 clues area.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

M3?

Postby dobrichev » Sat Jan 12, 2013 9:36 pm

These 5 puzzles are rated by my solver as backdoor of size 3 in singles.
Gsf's solver with -aFN rates them M2.1.xxx. With -q1 too.
Code: Select all
..............1.23..1.2..45..4..53...6.......7..8...1...5..3..1..6.524..2..9....6 # 95082 FNG C24.m/M2.1.308367 ED=10.5/1.2/1.2
..............1.23..2...145....6......4..53...7.8...9...3..42...8.7.....6...9..3. # 95072 FNG C22.m/M2.1.157464 ED=9.6/9.6/3.4
..............1.23..2.3.4....3.5..4..1...67..8....9.....5.7...4.6.8..5..9......7. # 95101 FNG C22.m/M2.1.295245 ED=9.8/9.8/2.6
..............1.23..4.5.6.......2..7.7.....1.8...6.9.5.37......4...8....9.84..5.. # 95103 FNG C22.m/M2.1.328050 ED=9.7/1.2/1.2
........1.......2...1..34....3..2.4..5..6....7...8.3....9..8..4.875..9..6...7.8.. # 92613 FNG C23.m/M2.1.144342 ED=9.4/1.2/1.2

Is my solver wrong?
If Gsf's solver is correct, then at least in size 2 backdoor area exist puzzles with only one backdoor option.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: M3?

Postby ronk » Sun Jan 13, 2013 12:15 pm

dobrichev wrote:These 5 puzzles are rated by my solver as backdoor of size 3 in singles.
Gsf's solver with -aFN rates them M2.1.xxx. With -q1 too.
Code: Select all
..............1.23..1.2..45..4..53...6.......7..8...1...5..3..1..6.524..2..9....6 # 95082 FNG C24.m/M2.1.308367 ED=10.5/1.2/1.2
..............1.23..2...145....6......4..53...7.8...9...3..42...8.7.....6...9..3. # 95072 FNG C22.m/M2.1.157464 ED=9.6/9.6/3.4
..............1.23..2.3.4....3.5..4..1...67..8....9.....5.7...4.6.8..5..9......7. # 95101 FNG C22.m/M2.1.295245 ED=9.8/9.8/2.6
..............1.23..4.5.6.......2..7.7.....1.8...6.9.5.37......4...8....9.84..5.. # 95103 FNG C22.m/M2.1.328050 ED=9.7/1.2/1.2
........1.......2...1..34....3..2.4..5..6....7...8.3....9..8..4.875..9..6...7.8.. # 92613 FNG C23.m/M2.1.144342 ED=9.4/1.2/1.2

Is my solver wrong?
If Gsf's solver is correct, then at least in size 2 backdoor area exist puzzles with only one backdoor option.

Can't help much with only an iPhone but, I think the gsf solver result needs to show FNP.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Re: The hardest sudokus (new thread)

Postby eleven » Sun Jan 13, 2013 5:46 pm

-qFN reports FNG, -q1 FNP.
I don't understand the output at all, because a 24 clue puzzle only has 1596 ways to place a pair of numbers (and look, if it solves with singles then). So "The estimated number of guesses before a backdoor hit" cannot be that high, however it is defined (even with all candidates left, you could not miss the backdoor with 81*1596=129276 guesses).
After all i guess, that the flaw is in gsf's program, but i don't have the tools here to verify it.
eleven
 
Posts: 1534
Joined: 10 February 2008

backdoors 3 in singles

Postby dobrichev » Thu Jan 24, 2013 1:26 pm

After 20 generations, the number of the puzzles having backdoor of size 3 in singles reached 12354974 and still grows exponentially.
This by itself makes these puzzles non-candidates for the hardest list(s).
I rated a sample of 4000 puzzles - there are 10 of SE9.5 and everything else is below. Almost all are SE=x/1.2/1.2 and few of them are SE=x/y/3.4
Puzzles are evently distributed by pattern. The most frequent pattern consists of only 139 puzzles, followed by 64, 39, etc.

There is no sign for backdoor of size 4.

Yet another fruitless survey.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: backdoors 3 in singles

Postby denis_berthier » Fri Feb 15, 2013 3:35 am

dobrichev wrote:After 20 generations, the number of the puzzles having backdoor of size 3 in singles reached 12354974 and still grows exponentially.
[...]
Yet another fruitless survey.

I wouldn't say fruitless. Years ago, it was conjectured that all the puzzles had backdoor size 2 or less. AFAIK, EasterMonster was the first with backdoor size 3. Other examples were found later, but we had no idea that there could be so many.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

backdoors 4 in singles

Postby dobrichev » Thu Apr 11, 2013 11:44 am

dobrichev wrote:...There is no sign for backdoor of size 4.


Here they are
Code: Select all
..............1.23.45.2..6............17....852..9.3.1....4.......2.9.5.976.5..3. ED=6.6/1.2/1.2
..............1.23.45.2..6............17....852..96..1....4.......2.9.5.9.6.58.3. ED=6.6/1.2/1.2
..............1.23.45.2..6............17....852..96..1....4.......2.9.5.976.5..3. ED=6.6/1.2/1.2
..............1.23.45.2..6.......6....17....852..9...1....4.......2.9.5.9.6.58.3. ED=6.6/1.2/1.2
..............1.23.45.2..6.......6....17....852..9...1....4.......2.9.5.976.5..3. ED=6.6/1.2/1.2

Please somebody confirm that these puzzles have backdoor of size 4 in singles.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Next

Return to General