The New Sudoku Players' Forum

[Mathimagics]

Some recent LCT-18 developments:

• I now have an SSD drive for JILL (i7700K, 4-core x 2-threads PC), so the old problem of slow access to the catalog is eliminated. In fact, it turns out that JILL now has even faster access times than JACK (the 16x2 AMD Ryzen PC).

• I have a new "random morph walker" 18C search function, that employs colin's "subpuzzle solution counts" idea to find 18C puzzles. This can find new 18C's much faster than any previous method, and is not restricted to puzzles in the immediate {+2,-2} vicinity.

• Much of the grunt work involves canonicalising grids/puzzles, and I have found Michael Deverin (holdout)'s Minlex Form via Chaining method is 8x faster than the existing function. If I can get it to transform a puzzle alongside the solution grid, then all things related to LCT-18 will be faster.

[coloin]

Very good again..presumably you are adding 3 clues .... what inspired it was this .. from What is most solved cells with "n" clues?

Code: Select all

+---+---+---+
|...|3.1|...|
|2.4|...|...|
|...|...|...|
+---+---+---+
|8..|52.|...|
|...|...|9.1|
|...|...|3..|
+---+---+---+
|...|.4.|.5.|
|91.|...|...|
|.3.|...|...|
+---+---+---+   this 15C found by G Royle has only 576 sol 

solves to

+---+---+---+
|5.9|3.1|...|
|2.4|.95|13.|
|1.3|...|59.|
+---+---+---+
|891|523|...|
|35.|...|9.1|
|.4.|91.|3.5|
+---+---+---+
|.2.|149|.53|
|915|.3.|...|
|43.|.5.|.19|
+---+---+---+    which has 29 more solved clues !  [still 576 sol]

Adding 2 clues does not give a 17C
Adding 3 clues gives us 1093 minimal 18C - although many from the same grid solution

1093.txt

(87.53 KiB) Downloaded 241 times

and this 15 clue [one clue different] has 2715 grid solutions

Code: Select all

+---+---+---+
|...|3.1|...|
|2.4|...|...|
|...|...|...|
+---+---+---+
|8..|52.|...|
|...|...|9.1|
|...|...|3..|
+---+---+---+
|...|.4.|.5.|
|71.|...|...|
|.3.|...|...|
+---+---+---+


Adding 2 clues gives one 17C [ thats how Gordon found it, I suppose]
Adding 3 clues gives us 1150 minimal 18C - which are different but again probably many from the same grid solution

I admit that it is highly likely that all these solution grids are known, and presumably remote 18C wont necessarily have a 15C subpuzzle with a low sol count / extra solved clues ....

[Mathimagics]

Ok, the search for new grids with 18C puzzles is now resumed, albeit with only 4 cores (JILL), as JACK is busy helping champagne with the 17C search.

I have rewritten the Gen18C process completely, and it is much simpler, and more efficient, I think. It looks to be achieving an NPH of ~3000 (new grids found per core-hour), which is quite good.

The current 18C grid count is 635,256,482.

Cheers
MM

[coloin]

Jus wondering what progress if any has been made !
Generating ever reducing yields with random search [it seems it needs to be better than a +2 to find some 18C] has made it difficult to see how it could ever be completed.

However... ... been reading through this thread and maybe some /many solution grids can be excluded from the search

On page 4

There are 983,959,110 ED double bands.
The 44 classes that you have in mind, can be partitioned into 913,393 smaller classes too

The proposal that I have ... is that we have this very incomplete table
Double bands have got 54 clues and they have been shown to be only 4 which complete in 7 clues ....

Code: Select all

Clues to complete     number
7                       4   
8                       ?1000
9                       ?   
10                      ?   
11                      ?   
12                      ?   
13                     any ?
--------------------------------
                  983,959,110

I am not aware of any DB been shown to need 13 clues and I guess it might be a big if ... ... but I suspect our 4 grids which need 21 clues would be highly likely to have a contribution there.,..
Now the point is if we exclude all DBs which complete in 12 and below, we would be left with the remaining DB which could be presumably tested quickly for their minimum no of clues for a completion. We have a very large supply of puzzles with 12 clues in their DB ---- so progress could be made quickly !!
If we get DB which cant be solved in 12, ie need 13, we would have grids which could be tested individually [or by gangster] to see whether the third band[s] cannot be completed by adding 4 then 5 clues, then this would exclude a 17 and 18 clues in the full grid[s].
I guess it all depends on the absolute numbers of DB needing 13 clues as to how much this will contribute.

On a side note - I have been experimenting generating 18C keeping the clues in box pattern [ in particular patterns with max 6 clues in a band]...... and this seems to be a fast way of generating them .. more on this...
Perhaps is relevant ...Generating 18C with 6 clues per band both ways will give us 6 DB per puzzle which will all have 12 clues in the 6 DBs ...

[coloin]

Taking the first grid of the 4 without a 21...,
here is 13 clues completing the DB .... and a 12 clue wasnt found at (-3+2) within the grid...

Code: Select all

......789       
.........       
.8.1.3.5.       
.1.8.....       
..5......       
....6.2.4       
541632978       
632978541       
978541632

Taking a few ED DB from the 4 grids without a 20C .... probably these are representatives of 6 of the 44 classes ....

Code: Select all

...........................123456789456789123789123456214897365365214897897365214   - none are solvable with 5
...........................123456789456789123789132465218967534564213978937548216   - some are solved in 4     
...........................123456789457189326689327154214965873375814962968273415   - some are solved in 4     
...........................123456789457189326689327154216534897745891632938672541   - some are solved in 4     
...........................123456789457189326689327154216573948574918263938264517   - some are solved in 4     
...........................123456789457189326689327154218634597745891632936572841   - some are solved in 4     


I have checked this several times ..... and the first DB here cant be completed with 5 clues, and this applies to
- all the grid solutions of the DB
- all the DB which have that class of gangster in band 3

Aside from this fortunate revelation...
We also know all the single bands which need 6 clues per se - so we actually do know which DB combined with whichever SB need 6 clues [for that SB] at a stroke

[champagne]

Jus wondering what progress if any has been made !
Generating ever reducing yields with random search [it seems it needs to be better than a +2 to find some 18C] has made it difficult to see how it could ever be completed.

However... ... been reading through this thread and maybe some /many solution grids can be excluded from the search

On page 4

There are 983,959,110 ED double bands.
The 44 classes that you have in mind, can be partitioned into 913,393 smaller classes too

The proposal that I have ... is that we have this very incomplete table
Double bands have got 54 clues and they have been shown to be only 4 which complete in 7 clues ....[code]

Hi coloin,

Just in case this could help

In the 17 search, we are considering ED bands 12 "minimal against the diagonal view"

This reduce the number of minimal in my case to 610 163 364 but using the 983,959,110 ED double bands would not be a problem

It happens that trying to produce an efficient code for the 18 search for the "mathimagics" project, I have somehow to produce all low count double band valid puzzles.

If this is very important for you, this code can easily (as soon as the validation tests will be done) be modified to answer to your point.

My rough estimate is that the process would take less than one second per double band (may be around 10 double bands per second in the best case).

[coloin]

Thanks ...... hopefully if we get that far that could be employed....if we get the majority by random methods ...
however I have to show first that grids with DB not completable in 12 clues exist !
[although there may be some merit in identifying those bands which are not completable in 11 [which there will be many]].
Those that don't have a plus 5 [so potentially have to have at least a 12plus6 ] dont have a 17C].

The first grid without a 21 [blue1]

Code: Select all

123456789456789123789123456214897365365214897897365214541632978632978541978541632


I have been generating random small puzzles from this blue1...... and there are no 12 completions so far...

blue did find a 12C in the MCgrid ... so indeed he has the methods !!

The MC grid has 6+6+27's:

Code: Select all

12...6......7....3.......5....5...9..64......8....1...312645978645978312978312645

which was a shame !

Edit: Grid1# renamed to blue1

[champagne]

blue did find a 12C in the MCgrid ... so indeed he has the methods !!

The MC grid has 6+6+27's:

Code: Select all

12...6......7....3.......5....5...9..64......8....1...312645978645978312978312645

which was a shame !

As I follow blues findings, I can see this one among a long list of potential 12 hitting all stored uas(and in a quick overview of the list 12 seems to be the minimum)
I did not make the final check of the validity of these 12. I can do it if you are interested and put them in the appropriate format (sub puzzle 54 cells)

EDIT here the first of a long list
..3.5....4....9.2....1.........6...7...8......9...15..312645978645978312978312645

[coloin]

This is the one to look at I think

Code: Select all

The first grid without a 21 [blue1]
123456789456789123789123456214897365365214897897365214541632978632978541978541632

Has it got a DB in 12 ?

[champagne]

This is the one to look at I think

Code: Select all

The first grid without a 21 [Grid#1]
123456789456789123789123456214897365365214897897365214541632978632978541978541632

Has it got a DB in 12 ?

As the MC grid, this one has 3 times band 1 (in 1-416)
I get similar result with the first in my list

....5...9..67...2.......4..2.......5....148...9.......541632978632978541978541632 (typo edit)

some more
...45......6....2.7....3...2....7.6...5.1.8...........541632978632978541978541632
....56.........1237........2....7.6...5.1.8...........541632978632978541978541632

[coloin]

Thanks for doing that ! ....
But it has scuppered it somewhat
Actually ........ you need to test all 6 DB

[champagne]

Thanks for doing that ! ....
But it has scuppered it somewhat
Actually ........ you need to test all 6 DB

hi coloin,
don't forget my poor knowledge of your language.
I can misunderstand your last sentence.
If my code is correct, this is part of 1392 possible 12

[coloin]

Actually I see that this grid is highly automorphic and is referred to as blue1, so it may well be that you have shown that all the DB have a 12-completion.
Your language is pretty good ... Thanks for your help

[champagne]

Actually ........ you need to test all 6 DB

Assuming I understand your point, some comments on the process.

This is part of the 18 clue search.
the first part of the process is to produce all valid 2 bands sub puzzles.

To do this, a long list of UAs is first established, trying to select uas of value (here 294 uas for bands 1+2)
then this list of uas is expanded up to 12 clues (for a 6+6+6 18 split of clues)
in most cases, the potential sub puzzles produced here are valid.

and in this case, the entire search takes less than half a second

[champagne]

Actually I see that this grid is highly automorphic and is referred to as blue1, so it may well be that you have shown that all the DB have a 12-completion.
Your language is pretty good ... Thanks for your help

another remark

6 of the 416 bands have a minimum of 6 clues in band. (1;224;237;254;307;413)
Any pair of these bands has a minimum number of clues of 12.
the best chance to pass 12 clues as minimum for 2 bands is with such a pair.

note : the lowest number of cases to consider is with the pair 224;237 (162 x 606 possibilities). likely the best chance to pass 12