The New Sudoku Players' Forum

[ChPicard]

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.

[tarek]

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

[JPF]

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

JPF

[tarek]

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

[coloin]

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

[tarek]

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

[tarek]

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

[coloin]

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

[tarek]

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

[coloin]

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]

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

[tarek]

very interesting ...

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

I will be PMing ChPicard.

tarek

[coloin]

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