## How regular is to generate sudoku with difficulty 9+ SE?

Everything about Sudoku that doesn't fit in one of the other sections
JPF wrote:Here is a new 11.4 :
Code: Select all
` 1 . . | . . . | . . 2  . 9 . | 4 . . | . 5 .  . . 6 | . . . | 7 . . -------+-------+-------  . 5 . | 9 . 3 | . . .  . . . | . 7 . | . . .  . . . | 8 5 . | . 4 . -------+-------+-------  7 . . | . . . | 6 . .  . 3 . | . . 9 | . 8 .  . . 2 | . . . | . . 1 `

Congratulations JPF! I believe you just proved the backdoor conjecture wrong...

However, your puzzle does have over 500 backdoor triples. I think we can safely assume that all puzzles will have at least one singles backdoor triple.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

If RW's checking is accurate then I must congratulate JPF for the marvellous breakthrough! I wonder how many backdoor singles/twins are there if you allow locked candidates as well as singles in the propositions?

But it's a really great achievement! BTW RW I'm not so sure about the safety of the singles backdoor triple conjecture... If Bangladesh can beat South Africa in a World Cup match then anything can happen! Next thing we know an Aussie golfer would actually win the US Masters!
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote:I wonder how many backdoor singles/twins are there if you allow locked candidates as well as singles in the propositions?

I'm not sure "propositions" applies here, but in the sense I think you mean it ... there are no backdoor twins even when allowing locked candidates.

Using gsf's solver: allowing naked and hidden singles (-qFN) yields 566 triples; allowing singles and locked candidates (-qFNB) yields 862 triples.

Truly amazing
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:Using gsf's solver: allowing naked and hidden singles (-qFN) yields 566 triples; allowing singles and locked candidates (-qFNB) yields 862 triples.

Truly amazing

And allowing singles, locked candidates and subsets there's only 3 backdoor pairs ([32]8[38]3 [38]3[91]8 [67]2[91]8).

Maybe the next milestone would be to find a puzzle that doesn't have any backdoor pairs using the -qFNBT constraints. Who's up for the challenge?

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

Congratulations, JPF !

Nice Easter present for gsf
ravel

Posts: 998
Joined: 21 February 2006

Thanks to all of you

JPF
JPF
2017 Supporter

Posts: 3754
Joined: 06 December 2005
Location: Paris, France

New toughies of the day :

11.3 # 100000002030400050006000700050803000000070000000950080700000600090008030002000001 # JPF 04/08
11.1 # 100000002030400050006000700080300000000065000000809040700000100050008090002000006 # JPF 04/08
11.1 # 100000002030400050006000700080300000000019000000805040700000600050008090002000001 # JPF 04/08
11.1 # 100000002003400050060000700000080090000906000008540000020000600700000001005090030 # JPF 04/08
10.7 # 100000002030400050006000700080503000000064000000800090007000600040008030200000001 # JPF 04/08
10.7 # 100000002030400050006000700080903000000014000000500090007000600090008030200000001 # JPF 04/08

Be careful : with the first one (gsfr=99995) you will get this message
java.lang.OutOfMemoryError: Java heap space
To solve this problem see here.

The others are gsfr = 99991 or 99992.

JPF
JPF
2017 Supporter

Posts: 3754
Joined: 06 December 2005
Location: Paris, France

Congrats JPF,
very good,,,, just a quick comment,,,, while trying to find a seede pattern from the puzzles you lately submitted, I came accross these puzzles that looked quite similar (& probably already posted puzzles) that came from the same canonical grid as your puzzles...I couldn't find an isomrphic equivalent, but with all that has been going on, i might have missed something
Code: Select all
`003050000400009000080200010070600008005004000900030000010000027000700036000000900100000089000009102000000400007600000030040000900002005004070000500008010060300000`

gsf,
In a trace of related puzzles... I attempeted to rate this puzzle (which is ordinary compared to the stuff here) using the "-q hardest" option without success - Am I doing something wrong?
Code: Select all
`020407000000080000000006410005000900300000008040700060070001020008000003900000500`

tarek

tarek

Posts: 2761
Joined: 05 January 2006

ravel wrote:Congratulations, JPF !

Nice Easter present for gsf

yes
really great work
this puzzle breaks the conjecture which started with one of my first posts in the programmer's forum
I'll have to update some documentation
it has 566 singles backdoors of size 3 (for which -f%#Am exceeds the print buffer size -- another change forced by this puzzle)

the simplest constraints that produce backdoors of size 2 are FNBT2 or FNBH2
(singles + box-line + naked or hidden pairs)

this thread has also caused me to resvisit the nested proposition code (referenced a few posts back)
its really tough normalizing across isomorphic copies
this will take some non-hacking thought (i.e., thinking before coding)
there is a mathematic characterization lurking here and its name isn't ER
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

tarek wrote:gsf,
In a trace of related puzzles... I attempeted to rate this puzzle (which is ordinary compared to the stuff here) using the "-q hardest" option without success - Am I doing something wrong?
Code: Select all
`020407000000080000000006410005000900300000008040700060070001020008000003900000500`

well, this one has a lot of X/Y cycles which is the most inefficient part of my solver
it also requires more than the usual amount of propositions to solve
if you let it crank a few minutes it should rate at 100008
so much for the intended 99999 limit

next round of nexted propositions will address this
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

tarek wrote:Congrats JPF,very good,,,,I came accross these puzzles that looked quite similar (& probably already posted puzzles) that came from the same canonical grid as your puzzles...I couldn't find an isomrphic equivalent, but with all that has been going on, i might have missed something
Code: Select all
`003050000400009000080200010070600008005004000900030000010000027000700036000000900100000089000009102000000400007600000030040000900002005004070000500008010060300000`

Thanks,
The 2 puzzles are non isomorphic with any of the list.
The second one is a close cousin of JPF 04/07 -11.4 (2 digits) and is rated ER=11.3
Here are their canonical representations :

Code: Select all
`100000089000009002000000450007600000030040000900002005004070000500008010060300000 JPF 04/07 100000089000009102000000400007600000030040000900002005004070000500008010060300000 tarek 04/08`

It was on my waiting list for ER evaluation.

I didn't check the ERs of the others.
Not enough computer time.

JPF
JPF
2017 Supporter

Posts: 3754
Joined: 06 December 2005
Location: Paris, France

The 11.4 is impressive, not sure where this stops though !

Here is a few 11.0+ I generated previously
Code: Select all
`11.2 # 1.......6.2.5...4...3...7...4...2......43.......9.5.8.7.....3...5...9.2...6.....1 # coloin 04/10/0111.1 # 1.......6.2.5...4...3...7...4.8.2.......6........45.8.7.....3...5...9.2...6.....1 # coloin 04/10/0211.1 # 1.......6.2.5...4...3...7...4.9.5.......74......2...8.7.....3...5...9.2...6.....1 # coloin 04/10/0311.1 # 1.......6.2.5...4...3...7...4.8.........34......9.5.8...7...3...5...9.2.6.......1 # coloin 04/10/0411.1 # 1.......6.2.5...4...3...7...4.85........1........24.8...7...3...5...9.2.6.......1 # coloin 04/10/05`

Code: Select all
`11.2 # 100000002090400050006000700080903000000070000000850030700000600050009080002000001 # JPF 04/07  11.2 # 1.......6.2.5...4...3...7...4.8.5.......3........24.8.7.....3...5...9.2...6.....1 # isomorph ?`

I also have an SE evaluation waiting list !

Last edited by coloin on Thu May 10, 2007 7:03 am, edited 1 time in total.
coloin

Posts: 1738
Joined: 05 May 2005

Updated my top list for the puzzles in this thread.

JPF's 11.4 puzzle with backdoor size 3 also for my program turned out to be extraordinary, because it is the first puzzle, that could not be solved in the first run, where (to save time) i only try to eliminate candidates, that lead to a "progress" of at least 2 more eliminations with the implemented technics. In the second run with at least 1 more elimination it was rated 17 points. Thus it did not qualify for my current top list (min. 18 points) - as long as i do not rate long subnet steps higher.

Tareks second puzzle (ER 11.3, also found by JPF) rated 20 points, which lowered to 16 points in the second run.
ravel

Posts: 998
Joined: 21 February 2006

coloin wrote:Here is a few 11.0+ I generated previously
Code: Select all
`11.1 # 1.......6.2.5...4...3...7...4.85........1........24.8...7...3...5...9.2.6.......1 # coloin 04/10`

this one has singles backdoor size 3 (T1H1 constraints)
but T1H1B backdoor size 2 (singles + box/line)

so a taxonomy of singles backdoor size 3 puzzles is forming
the first had T1H1BT2 backdoor size 2
now this one with T1H1B backdoor size 2
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

coloin wrote:The 11.4 is impressive, not sure where this stops though !

If you were, you could open a book . What are the odds on reaching 11.5? 12.0?

Regards,

Mike Metcalf

m_b_metcalf
2017 Supporter

Posts: 9384
Joined: 15 May 2006
Location: Berlin

PreviousNext