17-clue and 18-clue Sudoku update

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

Postby gfroyle » Wed May 16, 2007 9:36 am

Code: Select all
000030050200000040007050000100000700000800600030000000000600301054200000000000000


should be isomorphic to

Code: Select all
100000080000009200700030000260500000000000000000000073030608000090000000000000107
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby coloin » Wed May 16, 2007 12:46 pm

In the only published work that I know of, [here] , we [Ocean and I] searched,to extinction, 7 random grids. We only found one 18 puzzle. We thought we were very unlucky not to find another in one of the other grids [ - it had 2000 different 19s - no 18, confirmed with checker subsequently ! ]

Code: Select all
347981256582476193169523874896245317754318962213769485925137648478692531631854729
1 18
3...8.2.........9....5...748.6...3..............7.9..5....3.6...7.........1..4...



A truely random 18

How many 17s are near it ? [3-off-3-on][4-off-4-on]

What percentage are new:idea::?:

Red Ed wrote:There are 5472730538 essentially different Sudoku grids


Based on our measly sample size, the one in seven, which I suspect is a conservative estimate, means there are probably at least 780,000,000 grids with 18puzzles.

Checker is 10 times faster now so it would be fairly easy to validate these figures with a higher sample size, should there be a need !

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Ocean » Wed May 16, 2007 1:30 pm

Today's new 17:
Code: Select all
000000000000001023040005000000000000306000070005007810000030000400060000010000500
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby gsf » Wed May 16, 2007 3:14 pm

gfroyle wrote:
Code: Select all
000030050200000040007050000100000700000800600030000000000600301054200000000000000


should be isomorphic to

Code: Select all
100000080000009200700030000260500000000000000000000073030608000090000000000000107

thanks
this may have exposed a bug in my row order minlex canonicalization
just to verify, does this grid have 1 non-trivial automorphism?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Mauricio » Wed May 16, 2007 6:37 pm

gsf wrote:
gfroyle wrote:
Code: Select all
000030050200000040007050000100000700000800600030000000000600301054200000000000000


should be isomorphic to

Code: Select all
100000080000009200700030000260500000000000000000000073030608000090000000000000107

thanks
this may have exposed a bug in my row order minlex canonicalization
just to verify, does this grid have 1 non-trivial automorphism?


This grid has only the trivial automorphism, unless my program has a bug too.
Mauricio
 
Posts: 1174
Joined: 22 March 2006

Postby Ocean » Thu May 17, 2007 2:54 am

The thursday morning news (4 new 17s):
Code: Select all
000000000000010002340000500000607030002003000108000000000000007000000021050004000
000000000000012000300040005000000600700000020000020180060000000001700000000304007
000000000000012000300040005000000600700000020000020180060000000001700000000305007
000000000000012000300040005000000600700000020000020180060000000001700000000403007
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby gsf » Thu May 17, 2007 3:18 am

gsf wrote:
gfroyle wrote:
Code: Select all
000030050200000040007050000100000700000800600030000000000600301054200000000000000

should be isomorphic to
Code: Select all
100000080000009200700030000260500000000000000000000073030608000090000000000000107

thanks
this may have exposed a bug in my row order minlex canonicalization
just to verify, does this grid have 1 non-trivial automorphism?

it indeed exposed a bug in the tiebreaker part of the row-order minlex canonicalization code
the bug originated when I switched from box-order minlex to the more natural row-order minlex
and was in a part apparently not hit very often
it resulted in 1 wrong entry in the 2007-01-22 17's catalog and 2 wrong entries in the
catalog that led to its discovery

it was dumb luck that the grid I pulled out of the air yesterday hit the bug just right
and Gordon was kind/alert enough to note it
thanks also to the pm'ers who provided supporting data
bugs like this, especially in (supposedly) seasoned code, can be difficult to find

I corrected the 2007-01-22 and 2007-05-14 catalogs and reposted them
(after verifying the results with 3 different canonicalization algorithms)

I also posted a corrected solver

just to be safe, any catalogs based on my solver's canonicalization should be re-canonicalized
I'll do that for the hardest catalog when ER finishes rating it
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gfroyle » Thu May 17, 2007 3:19 am

Ocean wrote:The thursday morning news (4 new 17s):
Code: Select all
000000000000010002340000500000607030002003000108000000000000007000000021050004000
000000000000012000300040005000000600700000020000020180060000000001700000000304007
000000000000012000300040005000000600700000020000020180060000000001700000000305007
000000000000012000300040005000000600700000020000020180060000000001700000000403007


I make it 3 new ones, and one isomorphic to #10176

But 3 is good anyway...
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby gsf » Thu May 17, 2007 3:24 am

gfroyle wrote:I make it 3 new ones, and one isomorphic to #10176

are the posted sudoku17 ordinals going to be constant from this point on?
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gfroyle » Thu May 17, 2007 4:36 am

gsf wrote:are the posted sudoku17 ordinals going to be constant from this point on?


Yes...

There is no way of specifying a logical order that will remain unchanged because new ones may always fit "between" existing ones.

So from now on, I will simply add new ones to the end of the list and they will get a number.

I have a very rough prototype of an "automated checking and submission" service..

http://people.csse.uwa.edu.au/gordon/sudokuid.php

This will tell you whether a puzzle is new or which one it is equivalent to in the database (and will email me if it is new so that it can be added).

It needs considerable refinement, but I thought I would get you guys to check it out in its rough form.

(In particular, the "database" is not a proper database yet.. it is just a flat file, but when I transfer it to a proper DB, I can keep more information.)

Cheers

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby Ocean » Thu May 17, 2007 4:43 am

gfroyle wrote:
Ocean wrote:The thursday morning news (4 new 17s):
Code: Select all
000000000000010002340000500000607030002003000108000000000000007000000021050004000
000000000000012000300040005000000600700000020000020180060000000001700000000304007
000000000000012000300040005000000600700000020000020180060000000001700000000305007
000000000000012000300040005000000600700000020000020180060000000001700000000403007


I make it 3 new ones, and one isomorphic to #10176

But 3 is good anyway...


Thanks. Missing the isomorphic #10176 reveals an unstability in my programs - so it prompts me to write a proper normalizer instead of the clumsy methods I have used so far. (Seems I need help by somebody also to verify if the one '17' posted yesterday, plus the two '17s' posted two days ago, are not isomorphs to previously givens.)

Predictions: Today's three new 17s will not be rediscovered by the "2 off 2 on" algorithm (as used by Havard), since they seem to have no other puzzle in "2 off 2 on" distance. (The two given two days ago - provided they are relly new - will be discovered by the "2 off 2 on" algorithm, while the one given yesterday will not.)
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby gsf » Thu May 17, 2007 4:50 am

gfroyle wrote:
gsf wrote:are the posted sudoku17 ordinals going to be constant from this point on?


Yes...
(In particular, the "database" is not a proper database yet.. it is just a flat file, but when I transfer it to a proper DB, I can keep more information.)

thanks
and there's nothing wrong with flat file dbs
some of the largest most robust dbs are flat files
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Ocean » Thu May 17, 2007 5:01 am

gfroyle wrote:So from now on, I will simply add new ones to the end of the list and they will get a number.

I have a very rough prototype of an "automated checking and submission" service..

http://people.csse.uwa.edu.au/gordon/sudokuid.php

This will tell you whether a puzzle is new or which one it is equivalent to in the database (and will email me if it is new so that it can be added).

It needs considerable refinement, but I thought I would get you guys to check it out in its rough form.


Great! I checked the service with my posted puzzle from yesterday: seemed to already be incorporated, as #39447. Checked the two from tuesday, and it responded "This seems NEW !!" [maybe the first runs with this answer... ?]
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby gfroyle » Thu May 17, 2007 6:52 am

Ocean wrote:Great! I checked the service with my posted puzzle from yesterday: seemed to already be incorporated, as #39447. Checked the two from tuesday, and it responded "This seems NEW !!" [maybe the first runs with this answer... ?]


Yes, I added your yesterdays one to the list.

But I missed the Tuesday ones, and they were indeed new (and you were the first to use the Sudoku Identification Service to submit a new one). In fact they are very interesting to me. Puzzles #39451 and #39452 (which is the numbers they were given) are "far away" from the other 17-clue puzzles according to how I search for them...

So in particular, my techniques would probably never have found them!

Best

gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby Red Ed » Thu May 17, 2007 12:11 pm

gfroyle wrote:Puzzles #39451 and #39452 (which is the numbers they were given) are "far away" from the other 17-clue puzzles according to how I search for them...
Can you tell/remind us how your search works please?
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General