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

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

Postby RW » Sat Apr 07, 2007 2:32 pm

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

Postby udosuk » Sun Apr 08, 2007 9:01 am

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!:D
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby ronk » Sun Apr 08, 2007 11:14 am

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

Postby RW » Sun Apr 08, 2007 12:15 pm

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

Postby ravel » Sun Apr 08, 2007 1:37 pm

Congratulations, JPF !

Nice Easter present for gsf:)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby JPF » Sun Apr 08, 2007 5:46 pm

Thanks to all of you:D

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby JPF » Sun Apr 08, 2007 8:29 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby tarek » Sun Apr 08, 2007 11:42 pm

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
003050000400009000080200010070600008005004000900030000010000027000700036000000900
100000089000009102000000400007600000030040000900002005004070000500008010060300000


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
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby gsf » Mon Apr 09, 2007 4:53 am

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

Postby gsf » Mon Apr 09, 2007 5:00 am

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

Postby JPF » Mon Apr 09, 2007 9:43 am

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
003050000400009000080200010070600008005004000900030000010000027000700036000000900
100000089000009102000000400007600000030040000900002005004070000500008010060300000


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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Tue Apr 10, 2007 9:49 am

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/01
11.1 # 1.......6.2.5...4...3...7...4.8.2.......6........45.8.7.....3...5...9.2...6.....1 # coloin 04/10/02
11.1 # 1.......6.2.5...4...3...7...4.9.5.......74......2...8.7.....3...5...9.2...6.....1 # coloin 04/10/03
11.1 # 1.......6.2.5...4...3...7...4.8.........34......9.5.8...7...3...5...9.2.6.......1 # coloin 04/10/04
11.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 !

EDIT - labels added
Last edited by coloin on Thu May 10, 2007 7:03 am, edited 1 time in total.
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby ravel » Tue Apr 10, 2007 1:59 pm

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

Postby gsf » Tue Apr 10, 2007 2:11 pm

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

Postby m_b_metcalf » Tue Apr 10, 2007 2:58 pm

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


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

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8335
Joined: 15 May 2006
Location: Berlin

PreviousNext

Return to General