Who wants to find a new 17 given sudoku? And maybe a 16?

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

Who wants to find a new 17 given sudoku? And maybe a 16?

Postby ChPicard » Fri Mar 06, 2009 4:10 pm

Hi everybody

Yesterday I found the number 48014 in the Gordon Royle's database, my fourth one.

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

I am not fast like Glenn Fowler or Kohei Noshita but
together : YES WE CAN.

The idea is that a new one must be "between" two known sudokus if they are all sorted in minlex form.

So I wrote an application which create a big batch of sudokus to test. I find the good ones thanks to a slightly modify version of the Bit_Based Sudoku Solver by Brian Turner:
http://www.setbb.com/phpbb/viewtopic.php?t=1668&mforum=sudoku

A file is also created to keep in memory the cursor's position between two known sudokus for next time when an another batch is created.

And finally, I verify if the good ones are in the Royle's database.

Who wants to find a new 17 given sudoku? And maybe a 16?

Send me a private message, and I will send you the tools for this quest.

My sources are available too.

Good luck everybody.

Jean-Pierre Sangin from Montreal, Canada.
ChPicard
 
Posts: 16
Joined: 02 March 2008

Re: Who wants to find a new 17 given sudoku? And maybe a 16?

Postby tarek » Fri Mar 06, 2009 5:35 pm

ChPicard wrote:The idea is that a new one must be "between" two known sudokus if they are all sorted in minlex form.
That is a very good idea ...

I'm sure that aided with gsf's sotware ... the distance between successive minlex-ordered puzzles will help in choosing the (smallest or largest) search areas ...

There are also the areas where no man has gone before (before the 1st & after the last).

Good hunting

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby JPF » Fri Mar 06, 2009 5:59 pm

See the discussions here from coloin and I, a while ago.

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

Postby tarek » Fri Mar 06, 2009 6:57 pm

Ah,

I guess because the distance and neighbourhood search are clue based, then the minlex order should be based on the subgrid minlex order rather than the solution grid milex order:!::?:

I know Ruud's SudoCue does something like that. The 17s on display are in a subgrid minlex order as well.

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby coloin » Sun Mar 08, 2009 9:29 am

Very good.........taking it logically a step furthur !

With the minlex grid puzzles we had an advantage where we could fix many of the clues. However with the puzzle minlex order the problem of the large gaps between many puzzles perhaps is reduced.

I suppose adjaecent puzzles with identical clues in the first 13 clues could be searched {+4} ?
Only adding clues to positions "after" the 13th clue in the puzzle.

These 2 adjaecent puzzles have 12 clues the same
Code: Select all
000000000000001002034000050000002601005000000047000000000050000000740080200000009
000000000000001002034000050000002601005000000047000000000058000000740000200000009


If a minlex puzzle is found "between "these two puzzles it is by definition new.
There are othe possible prerequisites to reduce the options - eg 8 clue values must be used.

Well done on finding a new puzzle.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby tarek » Sun Mar 08, 2009 12:23 pm

coloin wrote:These 2 adjaecent puzzles have 12 clues the same
Code: Select all
000000000000001002034000050000002601005000000047000000000050000000740080200000009
000000000000001002034000050000002601005000000047000000000058000000740000200000009


If a minlex puzzle is found "between "these two puzzles it is by definition new.
They share the the 1st 59 cells of the subgrid ...

so the {-4+4} search can target only the last 22 cells .... How big a task is that ????

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby tarek » Sun Mar 08, 2009 6:02 pm

After a thought, this doesnt require a -4+4 search but an exhastive iterative process that has to fall between the 2 entries (bounderies) ....

I'm sure that gsf's software can do this. The leftmost mutual cells shouldn't be in the search ... the 1st puzzle should be the 1st possible minlex puzzles that comes after our upper boundery with the last puzzle being the 1st minlex puzzle possible before the lower boundery.

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby coloin » Sun Mar 08, 2009 6:56 pm

Indeed, it is potentially a reduced search.

Confusingly my example with 12 clues, represents a {-0+5} search.

However, it is only over 22 cells, and one clue value must be an 8.

A challenging aspect, which might make more of these searches feasible would be to exclude clue values in positions which would make up a lesser minlex puzzle.

Almost certainly there will not be a 16 though.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby tarek » Sun Mar 08, 2009 11:52 pm

if you do it iteratively then you will not get any that is not in the minlex order & you will not miss anything ...

here is how the iterative process goes between the above puzzles
Code: Select all
000000000000001002034000050000002601005000000047000000000050000000740080200000009 Start
000000000000001002034000050000002601005000000047000000000050000000740080200000010
000000000000001002034000050000002601005000000047000000000050000000740080200000020
.
.
.
000000000000001002034000050000002601005000000047000000000058000000740000200000007
000000000000001002034000050000002601005000000047000000000058000000740000200000008
000000000000001002034000050000002601005000000047000000000058000000740000200000009 End
It is a huge task even for this gap but it will not miss anything. Some combinations can be avoided by using the PM grid, I'm not sure if this speeds the process though:(
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby coloin » Mon Mar 09, 2009 12:00 am

before anyone comments...i see tarek has !

I might add that the {+5} search over 22 cells -the upper limit is ever so slightly too big a search ~

However the minlex approach might reduce this

Presuming the minlex processing of a puzzle envolves a two stage process...........? correct

Ignoring the clue values initially
Minimum template processing - minimum of the 6^8*2 templates of the puzzle
Inserting the clue numbers
Minimum number processing - minimum of the 9! puzzles

In my example, the number of minimum templates that can occur by adding 5 clue loci between the two puzzles - 5 loci out of 22 loci - total 26334 - [22*21*20*19*18 /5!] will be reduced significantly

generating some of these,....6190 templates with 5 positions over these 22 loci - only 431 fell between the two puzzles

Each template will have at most ~7^5 possibilities, reduced if one clue has to be value 8.

Even if this could be implimented it still is quite a big search.

Thinking furthur............

The "gaps" between the puzzles are on average a lot bigger than this. I dont suppose the maxlex puzzle list looks any better in this respect. The gaps are an indication of how big the "puzzle space" for 17 clues is.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby coloin » Tue Mar 10, 2009 12:32 am

I have downloaded ChPicard's tools.

Essentially it is performing a version [and more] [up to +6 difference] of what tarek outlined.

Stage 1 Generate the possible puzzle by adding clues to the initial clues of selected minlex 17-puzzles.
Stage 2 Test each of these potential 17-puzzles for a unique solution - using a version of briturner's program.

Interesting if many people are doing this how many more new puzzles we can get.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby tarek » Tue Mar 10, 2009 12:41 am

very interesting ...

I'm happy to test on A gap ...

I will be PMing ChPicard.

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby coloin » Wed Mar 18, 2009 3:15 am

Well, i tried the method....and as usual, not many 17s came out, none new.

However a bit of thought on the subject

to fill 17 clues to form a possible puzzle.......there are [81!] / [17! * 64!] patterns.

of which approaching 6^8*2 will be isomorphic...this reduction in minlex patterns.

We have approx 48000 17-puzzles

So the average number of minlex patterns between each minlex 17-puzzle would be just under 800,000.

Except there will be maybe 33% ? of patterns at the beginning of the order with 18+ empty positions......[ which cant possibly solve a puzzle.]

There are several other known collections of positions which are known / proven not to have a valid puzzle, no matter how many clues you have. So all combinations of 17 clues from that collection wont have a valid puzzle.
Code: Select all
min 17-puzzle
#26875#  000000000000000001000002030000003020001040000005000060030000004070080009620007000
max 17-puzzle
#11644#  000000001000002034056000000000040500004010000070000800000600002000800900400000000

C
coloin
 
Posts: 1637
Joined: 05 May 2005


Return to General