The New Sudoku Players' Forum

[Leren]

Mathimagics,

I was always aware of the relative slowness of my platform, but nevertheless, the sorts of times you were quoting were about the same as my estimates for my process.

I think I could finish in a few months if I run my PC overnight every night, which I sometimes do. I note above that you also now have the more modest target, like me, of finding just one more 11 clue set.

Leren

[Mathimagics]

I was always aware of the relative slowness of my platform, but nevertheless, the sorts of times you were quoting were about the same as my estimates for my process.

That suggests that your search method is indeed a very good one!

My point was simply this - if your job is expected to take a few months, then we might expect a compiled VB6 version to complete in a couple of weeks at most.

If you think this is worthwhile, you could send me your VB code and I could have a play with it. PM me if you want and I'll give you an email address.

I note above that you also now have the more modest target, like me, of finding just one more 11 clue set.

Well, I'll certainly be happy if and when ANYBODY finds a new one, but our target still remains the complete enumeration.

[coloin]

Well I dont think its a new one but certainly interesting ....
I scanned a few grids using Mathimagic's program

Code: Select all

..3...........82.1.79......................7.2............3...........6..4....... #                 
123456789456798231879312456568971342914823675237564198695237814382149567741685923 #   22979593 (B3)


just a -1+1 away is this puzzle - so i cant see it being new - but it has at least 2 automorphisms

Code: Select all

                                                                                             
..3...........82.1.79......................7.2............3..............45...... #     automorphic puzzle           
......98.4.67...........5........31..............5............6.8................ #     automorphic puzzle           
                                                                                                   
123645987456798231879312564568479312914823675237156498791234856382567149645981723 #   same solution             
123645987456798231879312564568479312914823675237156498791234856382567149645981723 #   same solution             


[Mathimagics]

.
I think you missed one. Both of these are valid:

Code: Select all

                                                                                ..3...........82.1.79......................7.2............3..............45......
..3...........82.1.79......................7.2............3..............46......


And both turn out to be forms of # 53658890

[Leren]

Sorry to be a KillJoy, but those last 4 clue sets have the same solution signature as B9 and so are probably morhs. I'm sure Serg or blue can confirm this. Leren

[blue]

Sorry to be a KillJoy, but those last 4 clue sets have the same solution signature as B9 and so are probably morhs. I'm sure Serg or blue can confirm this. Leren

Confirmed.

[coloin]

the puzzle was within {-1+1} so i don't think it was ever going to be new - it was the automorphism that was interesting !

I've had a re look at our analysis thread.
ED grids are 171,677,353
reduced to 53,666,689

perhaps for each of our representative puzzles we could have the 3 or 4 ED grids -

[Mathimagics]

.
Not good news!

First a word about search organisation. I have divided the 611,502 grid pool into 32 jobs by small UA counts (nUA12 = # of UA's of size 12 or less). This is strongly correlated with grid processing time,as can be seen in the job progress table below.

• Job 10 consists of 2077 grids with nUA12 <= 10

• Jobs 11 through 40 have nUA12 = 11, 12 ... 40

• Job 41 has all grids with nUA12 > 40 (25,564 grids)

Based on our limited pool of known solutions, job 10 is the one most likely to yield results. It is also the most expensive to test.

The search program (Find11C) can run in these modes:

• Normal (full HS enumeration)

• Reduction mode B (9B + 8) - will find 11C puzzles with 3 clues in a box

• Reduction mode R (9R + 8) - will find 11C puzzles with 3 clues in a row

• Reduction mode C (9C + 8) - will find 11C puzzles with 3 clues in a column

• Reduction mode P (9P + 8) - will find 11C puzzles with 3 clues in a Pset

• The 4 reduction modes can also run in (9x + 7) mode, this will find 11C puzzles with 4 clues in a box/row etc

Again, based on our limited pool of known solutions, most likely mode to start with is (9B + 8), and that is what we are running now.

Progress report:

Code: Select all

Search mode: 9B + 8

Job10: NG  =   2077 of   2077 (100.00%), avg tm = 1734.25s
Job11: NG  =    856 of   1735  (49.34%), avg tm =  417.14s
Job23: NG  =  10055 of  34819  (28.88%), avg tm =   35.75s
Job24: NG  =  15750 of  35711  (44.10%), avg tm =   33.00s
Job25: NG  =  17639 of  35447  (49.76%), avg tm =   29.47s
Job26: NG  =   4869 of  35109  (13.87%), avg tm =   25.88s
Job27: NG  =   3253 of  33103   (9.83%), avg tm =   25.12s
Job39: NG  =   3123 of   7292  (42.83%), avg tm =   18.12s
Job40: NG  =   3224 of   6163  (52.31%), avg tm =   17.22s
Job41: NG  =  23514 of  25564  (91.98%), avg tm =   15.30s

Jobs   =       32 (completed 1, running 9)
Grids  =    84360   (13.84%)


No new 11C puzzles have been found!

[Leren]

Mathimagics wrote: No new 11C puzzles have been found!

Did you mean puzzles or clue sets ? We already know that the number of ED clue sets > the number of ED puzzles. Leren

[Mathimagics]

Did you mean puzzles or clue sets?

I mean new 11C puzzles of any sort on CF grids that we don't already know about (ie: not in the 12 grids / 18 puzzles list).

[Mathimagics]

.
coloin asked me how many grids might prove to have 9B + 8 puzzles,and just how many there might be among all CF grids (53M).

I tested small batches of CF grids, with the following results.

Code: Select all


 nsUA  Sample      NG17P   TN17P   Avg    Max
 --------------------------------------------

   11  first 20      19     564     28    184
       last  20      20    5481    274   3429

   25  first 20      12     355     12     60
       last  20      13     928     45    370

   40  first 20       8      16      1      4
       last  20       5      31      2     21


  Non-pool?
       random 50      0


• nsUA is the number of small UA's (size <= 12), which corresponds to my division of the 10C/11C candidate pool as described above. For each sample I tested the first 20 grids inn the list, and the last 20, bearing in mind that each grid list is in CF order. For the last sample I drew 50 grids at random from the rest of the grids.

• NG17P is the number of grids for which a 9B + 8 puzzle was found, TN17P the total number found

• there is a strong correlation between nsUA and existence of 9B + 8 puzzles

• there is a bias towards grids with high index numbers, a bias which persists across all the 11C search functions I've run (note also that 50% of the known 11C grids are clustered at the high end)

Based on this admittedly small, but revealing, sample, I'd say that 99% - 100% of grids with 9B + 8 puzzles are to be found in our 611,502 grid pool.

Pool grids have high probability of having 9B + 8 puzzles, maybe 30-40% of them. If the average number of 9B + 8 puzzles per grid is around 20-30, then the total number might be as high as 1M to 2M.

Sadly I neglected to report the actual number of 9B + 8 puzzles in the Find11C program which is currently running, and which generates 9B + 8 puzzles as part of the process. I've rectified that now, and all searching from here on will log these details, so we can get some idea of what the real numbers are, and how good my estimates are, as the search progresses.

Speaking of which, we've searched 18% of the pool, and still no cigar!

[Mathimagics]

.
The # of ED standard Sudoku grids with minimal (17-clue) puzzles is roughly 50,000. So roughly one in 110K grids have minimal puzzles.

If SudokuP had comparable rates, then we might expect to find among the 53M ED grids some 400 cases of 11C puzzles.

If there really are only 12, then that seems unreasonably low by comparison!

[Leren]

At the risk of sounding picky, there really are 14 ED 11 clue sets found so far, solving to 12 ED grids. If that's all there are, blue found 9 of them in 1 hour !

I just realised the other day that if there really is a 10 clue set, there should be 71 11 clue sets not yet discovered all solving to the same puzzle. Not likely I think. Leren

[Mathimagics]

.
Time for an update. Find11C (running in 3CB mode, ie 9B + 8 reduction mode), has now checked 222,458 (36% of the grid pool) and still no cigar!

All this work for so little reward!

coloin and I meanwhile have been looking at 12-clue puzzles, since they become of increasing interest, given the rarity of 11-clue puzzles. I will post a summary of our progress in a new thread. They are satisfyingly abundant but identifying them all has its own problems.

Meanwhile, we should bear in mind that the 11-clue search is certainly not over when this 3CB search is completed, since it is possible that there are more 11-clue puzzles with maximum 2-clues in a box.

So, we should really make another pass in some other mode, say 3CR. And if that fails, well it will probably be November by that stage! Urrgh ...

[blue]

Hi Mathimagics,

I see in the other thread, that you (guys) have branched out to 12 clue puzzles now, too.
What is the status of the 10-clue search ?

Cheers,
Blue.