## Bands and low-clue puzzles

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

### Re: Bands and low-clue puzzles

Hi champagne,

Is it the search of a 17 clues or is it still the search of a 16 clues?

It's for 17-clues. One 17 was found for each grid.

Is it correct to say that the call {on or off} is to check whether the "solution" hitting all sets has a unique solution

Exactly. (The "puzzle count" numbers, are the hitting set counts)
blue

Posts: 894
Joined: 11 March 2013

### Re: Bands and low-clue puzzles

blue wrote:
Code: Select all
`Inspecting grid no. 2 ...found 407854 hitting sets (32.8382 seconds, average = 64.8574 sec/grid)`

This is with the code's original solver ... Brian Turner's "BBSolver".

To finish my draft, I concentrate on the second grid requiring less time to investigate. Missing to-day is the process after shortages in UAs before the end, but I'll test also the use of valid minimum puzzles for the band 3.

In my process, the count of hitting sets will not come in that way, but anyway, the count is (slightly) influenced by the collection of UAs used.
Having a check of the validity of a bands 1+2 sub puzzle, I have currently the following count (subject to...)

3 518 811 Sub puzzles bands 1+2 to check
966 164 valid sub puzzles
315 745 final puzzles to test

and one valid 17, (known)

I can skip the control of the validity for bands 1+2, but this gave me worse results when I made the test. I'll do it to compare the final count to the reference
champagne
2017 Supporter

Posts: 7002
Joined: 02 August 2007
Location: France Brittany

### Re: Bands and low-clue puzzles

champagne wrote: 966 164 valid sub puzzles

I hate to be the bearer of bad news, but there are 1,083,938 valid "11+27" puzzles for that grid.

Code: Select all
`4+7+27 1523805+6+27 6048686+5+27 320825 7+4+27   5865`
blue

Posts: 894
Joined: 11 March 2013

### Re: Bands and low-clue puzzles

blue wrote:
champagne wrote: 966 164 valid sub puzzles

I hate to be the bearer of bad news, but there are 1,083,938 valid "11+27" puzzles for that grid.

Hi blue,

Don't worry, checking the validity of the code is a difficult task your count will help.

In fact, the processing of the shortages of UAs below 11 clues is not yet covered. I just hope to find there the missing valid sub puzzles. If the count is still bad, I'll have to understand why and fix the bug(s).

Trying many options, I'll have at the end to revise seriously the code before the final debugging.

Just to stay on the positive side, It could be that I have one easy way to benefit from the valid band 3 having the minimum count (here six clues)
champagne
2017 Supporter

Posts: 7002
Joined: 02 August 2007
Location: France Brittany

### Re: Bands and low-clue puzzles

Some partial results to share
I am still concentrating on the second example

Code: Select all
`214378695867295341935641872348962517591837264672514938123456789456789123789123456  morph of entry2..........7.........64.8...4...2.......37...6.....9........7.........23.891.....  known 17`

No change so far for bands 1+2

Code: Select all
`966164     valid   sub puzzles 11         (1,083,938  in blue count)  5235     valid sub puzzles 10 clues     4    valid sub puzzles  9 clues `

Let keep for later the count of valid 11 clues puzzles generated by the 5235+4 sub puzzles of lower size.
I introduced in the main road (valid sub
puzzles size 11) a filter based on the known valid band 3 possible sub puzzles
( 729 possibilities as of mladen's table in the first post).
The filter does not use directly that table, but a direct access to a three dimensions table of still valid cells after one, two or three cells have been assigned in band 3.

The main road run time falls to 10.5 seconds, always in parallel to 5 others batches (heavy processor consumption).
I had 371 039 puzzles to check (407 854 in the Gary McGuire' program, given by blue)

The next step will be to see how to handle the (5235 + 4) sub puzzles , with a possible bad surprise, but I show here after that we have room for optimism.

Other important steps will be

to optimize the start lot of UAs
to see what happens with a lower minimum of clues in band 3.
The expected distribution for solution grids having one or more 17 is for me the following

Code: Select all
`6    935  78424 381273   238  46300`

so the band3 with 6 clues is by far not the main case.

Regarding the processing of the (5235 + 4) sub puzzles, I am expecting things similar to that first case

Code: Select all
`.1.3.......7..........4...234.9............6.........8  valid 10 clues sub grid for bands 1+2still active UAs excluding pure band 3 UAs(2 blank have been added to show the band 3                                                             ...............1.1....................................  ...............1.1......... i=0........................11............................  ......11................... i=1.....1.................................1.1............  ............11............. i=21............................................1.1......  .........1.1............... i=3.........11..................................11.......  ..................11....... i=4......1.1.......................11.1.....11.1.........  ........................1.1 i=5........1..........11.................................  ..1.....1.1......1..1....1. i=6.............11....11.................................  ..1.1...1.1...1..1......... i=7......1.1......11..................................11.  ........................111 i=8..........1...1.....11..........................1.1...  ...1.1....11............... i=9............1.1.................1...............11....  ....11...............11.... i=10A quick look to the band 3 in that table show a potential UA of degree 7...............1.1....................................  ...............1.1......... i=0........................11............................  ......11................... i=1.....1.................................1.1............  ............11............. i=21............................................1.1......  .........1.1............... i=3.........11..................................11.......  ..................11....... i=4......1.1.......................11.1.....11.1.........  ........................1.1 i=5............1.1.................1...............11....  ....11...............11.... i=10`

So either we can solve band 3 with that small list of UAas,with no more cell in bands 1+2
or we take one clue in the left part of the table and finish as in the main road, 6 clues in band3

This is something that blue and I already used with success in the X+Y+27 post processing.
champagne
2017 Supporter

Posts: 7002
Joined: 02 August 2007
Location: France Brittany

### Re: Bands and low-clue puzzles

Below are the timings from the ancient gridchecker for these example 2 grids.

Hidden Text: Show
Code: Select all
`123456789456789123789123456214368597867945231935217864348672915591834672672591348#full search\$ ./gridchecker --verbose --scan --gridfile b6b --unav12 --unav4Loading UA sets from file b6b.unav.txtSaving 11163 UA sets to file b6b.unav.txtMCN=11, Maximal Cliques found=6.Clique 000{11,12,41,42} (4){34,35,64,65} (4){53,56,63,66} (4){13,16,23,26,33,36} (6){14,15,54,55,94,95} (6){27,28,29,57,58,59} (6){31,32,51,52,91,92} (6){21,22,72,76,79,81,86,89} (8){24,25,73,75,78,83,84,88} (8){44,45,61,62,71,74,77,82,85,87} (10){17,18,19,37,38,39,47,48,49,67,68,69} (12)637009920 combinations.....Iterator to grid map:41 12 11 42 53 56 63 66 69 59 55 65 68 62 52 58 67 64 61 57 54 51 31 27 34 37 24 21 38 28 25 15 18 35 39 36 29 23 13 16 49 47 19 17 79 77 97 91 87 85 74 71 45 44 96 93 86 83 82 76 73 72 33 32 14 22 26 43 46 48 75 78 81 84 88 89 92 94 95 98 99 Grid to iterator map:13 12 53 82 45 54 58 46 57 41 83 52 39 44 84 36 43 51 35 81 79 37 47 49 38 42 48 11 14 85 69 68 86 56 87 55 34 26 15 33 22 16 32 27 21 31 25 17 29 23 18 28 24 19 67 78 77 66 88 76 61 89 59 91 75 74 92 65 73 64 93 94 63 95 72 96 97 71 62 98 99 maxPositionLimitsByUA04 08 12 16 22 28 34 40 46 54 64 81 81 81 81 81 81 Using 2000 UA, 1471 of size up to 19, and leftmost 529 regardless of the size.Starting enumeration of all valid puzzles of size up to 17.Generating chunks... 342 chunks generated.12.1053% at 0.017h,Checked=11765,Found=0,ETTF=0.123h...Searched for 17, generated 73683 puzzles, found 1 valid.Enumeration done in 378.488 seconds.Total time 393.136 seconds.#fast search, would find 99% of the known 17s\$ ./gridchecker --scan --gridfile b6b --fast17 --unav12Digits (1,2), 18+12= 2226, minimals=0Digits (1,3), 18+11=    4, minimals=0Digits (1,4), 18+12= 2183, minimals=0Digits (1,5), 18+11=   34, minimals=0Digits (1,6), 18+11=   22, minimals=0Digits (1,7), 18+12= 1537, minimals=0Digits (1,8), 18+12= 5070, minimals=0Digits (1,9), 18+11=   21, minimals=0Digits (2,3), 18+11=   19, minimals=0Digits (2,4), 18+11=    1, minimals=0Digits (2,5), 18+12= 1106, minimals=0Digits (2,6), 18+11=    2, minimals=0Digits (2,7), 18+11=   12, minimals=0Digits (2,8), 18+11=    1, minimals=0Digits (2,9), 18+11=   46, minimals=0Digits (3,4), 18+11=   21, minimals=0Digits (3,5), 18+12= 2253, minimals=0Digits (3,6), 18+11=    1, minimals=0Digits (3,7), 18+11=    1, minimals=0Digits (3,8), 18+11=    2, minimals=0Digits (3,9), 18+11=   28, minimals=1Digits (4,5), 18+12= 1172, minimals=1Digits (4,6), 18+12= 1518, minimals=1Digits (4,7), 18+12= 2366, minimals=1Digits (4,8), 18+11=    3, minimals=1Digits (4,9), 18+11=    1, minimals=1Digits (5,6), 18+11=    1, minimals=1Digits (5,7), 18+11=    1, minimals=1Digits (5,8), 18+11=    3, minimals=1Digits (5,9), 18+12= 1338, minimals=1Digits (6,7), 18+12= 1779, minimals=1Digits (6,8), 18+11=    1, minimals=1Digits (6,9), 18+12= 1139, minimals=1Digits (7,8), 18+12= 1350, minimals=1Digits (7,9), 18+11=    1, minimals=1Digits (8,9), 18+12= 2292, minimals=11 17-s found.000000700000000023089100000200000000007900000030000064008000910000034000000000000Total time 102.900 seconds.#very fast search, would find 87% of the known 17s\$ ./gridchecker --scan --gridfile b6b --veryfast17 --unav12Digits (1,2), 18+11=    0, minimals=0Digits (1,3), 18+11=    4, minimals=0Digits (1,4), 18+11=    0, minimals=0Digits (1,5), 18+11=   34, minimals=0Digits (1,6), 18+11=   22, minimals=0Digits (1,7), 18+11=    0, minimals=0Digits (1,8), 18+11=    0, minimals=0Digits (1,9), 18+11=   21, minimals=0Digits (2,3), 18+11=   19, minimals=0Digits (2,4), 18+11=    1, minimals=0Digits (2,5), 18+11=    0, minimals=0Digits (2,6), 18+11=    2, minimals=0Digits (2,7), 18+11=   12, minimals=0Digits (2,8), 18+11=    1, minimals=0Digits (2,9), 18+11=   46, minimals=0Digits (3,4), 18+11=   21, minimals=0Digits (3,5), 18+11=    0, minimals=0Digits (3,6), 18+11=    1, minimals=0Digits (3,7), 18+11=    1, minimals=0Digits (3,8), 18+11=    2, minimals=0Digits (3,9), 18+11=   28, minimals=1Digits (4,5), 18+11=    0, minimals=1Digits (4,6), 18+11=    0, minimals=1Digits (4,7), 18+11=    0, minimals=1Digits (4,8), 18+11=    3, minimals=1Digits (4,9), 18+11=    1, minimals=1Digits (5,6), 18+11=    1, minimals=1Digits (5,7), 18+11=    1, minimals=1Digits (5,8), 18+11=    3, minimals=1Digits (5,9), 18+11=    0, minimals=1Digits (6,7), 18+11=    0, minimals=1Digits (6,8), 18+11=    1, minimals=1Digits (6,9), 18+11=    0, minimals=1Digits (7,8), 18+11=    0, minimals=1Digits (7,9), 18+11=    1, minimals=1Digits (8,9), 18+11=    0, minimals=11 17-s found.000000700000000023089100000200000000007900000030000064008000910000034000000000000Total time 19.479 seconds.`

Hidden Text: Show
Code: Select all
`214378695867295341935641872348962517591837264672514938123456789456789123789123456#full scan\$ gridchecker --verbose --scan --gridfile b6 --unav12 --unav4Loading UA sets from file b6.unav.txt0 UA sets loaded.Saving 9593 UA sets to file b6.unav.txtMCN=11, Maximal Cliques found=22.Clique 000{11,12,71,72} (4){27,29,87,89} (4){44,47,64,67} (4){13,15,18,23,25,28} (6){21,22,61,62,91,92} (6){45,48,55,58,65,68} (6){75,78,85,88,95,98} (6){76,79,83,86,93,99} (6){14,16,17,34,36,37,94,96} (8){31,32,41,42,51,52,81,82} (8){43,46,49,56,59,63,66,69} (8)254803968 combinations....Iterator to grid map:64 47 67 44 38 77 37 78 35 36 65 66 34 17 32 14 22 27 98 75 95 82 88 72 85 56 54 16 15 84 68 58 55 45 41 61 97 94 87 81 74 71 89 86 83 79 76 73 92 91 69 62 49 43 23 21 59 53 48 42 29 28 13 12 11 18 19 24 25 26 31 33 39 46 51 52 57 63 93 96 99 Grid to iterator map:82 81 79 27 42 41 25 83 84 72 28 71 85 86 87 29 78 77 88 26 89 24 19 21 17 15 91 48 76 69 14 47 92 12 75 68 93 94 74 39 46 38 95 45 73 49 67 96 11 22 23 13 44 66 56 36 63 55 32 62 16 18 61 54 34 59 43 37 58 53 35 57 65 64 97 52 33 98 51 31 99 maxPositionLimitsByUA04 08 12 18 24 30 36 42 48 56 64 81 81 81 81 81 81 Using 2000 UA, 1438 of size up to 19, and leftmost 562 regardless of the size.Starting enumeration of all valid puzzles of size up to 17.Generating chunks... 364 chunks generated.04.7237% at 0.017h,Checked=153,Found=0,ETTF=0.339h...96.9003% at 0.400h,Checked=10271,Found=1,ETTF=0.013hSearched for 17, generated 10309 puzzles, found 1 valid.Enumeration done in 1443.003 seconds.Total time 1499.240 seconds.#fast 99%\$ ./gridchecker --scan --gridfile b6a --fast17 --unav12Digits (1,2), 18+12=  942, minimals=0Digits (1,3), 18+11=    1, minimals=0Digits (1,4), 18+12=  353, minimals=0Digits (1,5), 18+12=  600, minimals=0Digits (1,6), 18+12=  804, minimals=0Digits (1,7), 18+12= 6517, minimals=0Digits (1,8), 18+12= 3110, minimals=0Digits (1,9), 18+11=    1, minimals=0Digits (2,3), 18+11=    5, minimals=0Digits (2,4), 18+11=    3, minimals=0Digits (2,5), 18+12=    9, minimals=0Digits (2,6), 18+12=  317, minimals=1Digits (2,7), 18+11=    2, minimals=1Digits (2,8), 18+12=  732, minimals=1Digits (2,9), 18+12=  665, minimals=1Digits (3,4), 18+11=    3, minimals=1Digits (3,5), 18+12= 1131, minimals=1Digits (3,6), 18+12=  165, minimals=1Digits (3,7), 18+11=   10, minimals=1Digits (3,8), 18+12= 1352, minimals=1Digits (3,9), 18+11=    4, minimals=1Digits (4,5), 18+12=  205, minimals=1Digits (4,6), 18+12= 1401, minimals=1Digits (4,7), 18+12=  298, minimals=1Digits (4,8), 18+11=    2, minimals=1Digits (4,9), 18+12=  388, minimals=1Digits (5,6), 18+12=  124, minimals=1Digits (5,7), 18+11=    1, minimals=1Digits (5,8), 18+12=  293, minimals=1Digits (5,9), 18+12=  233, minimals=1Digits (6,7), 18+11=    1, minimals=1Digits (6,8), 18+12= 2312, minimals=1Digits (6,9), 18+12=  980, minimals=1Digits (7,8), 18+12=  472, minimals=1Digits (7,9), 18+12= 1855, minimals=1Digits (8,9), 18+12=  612, minimals=11 17-s found.200000000007000000000640800040002000000037000600000900000000700000000023089100000Total time 108.178 seconds.#very fast 87%\$ ./gridchecker --scan --gridfile b6a --veryfast17 --unav12Digits (1,2), 18+11=    0, minimals=0Digits (1,3), 18+11=    1, minimals=0Digits (1,4), 18+11=    0, minimals=0Digits (1,5), 18+11=    0, minimals=0Digits (1,6), 18+11=    0, minimals=0Digits (1,7), 18+11=    0, minimals=0Digits (1,8), 18+11=    0, minimals=0Digits (1,9), 18+11=    1, minimals=0Digits (2,3), 18+11=    5, minimals=0Digits (2,4), 18+11=    3, minimals=0Digits (2,5), 18+11=    0, minimals=0Digits (2,6), 18+11=    0, minimals=0Digits (2,7), 18+11=    2, minimals=1Digits (2,8), 18+11=    0, minimals=1Digits (2,9), 18+11=    0, minimals=1Digits (3,4), 18+11=    3, minimals=1Digits (3,5), 18+11=    0, minimals=1Digits (3,6), 18+11=    0, minimals=1Digits (3,7), 18+11=   10, minimals=1Digits (3,8), 18+11=    0, minimals=1Digits (3,9), 18+11=    4, minimals=1Digits (4,5), 18+11=    0, minimals=1Digits (4,6), 18+11=    0, minimals=1Digits (4,7), 18+11=    0, minimals=1Digits (4,8), 18+11=    2, minimals=1Digits (4,9), 18+11=    0, minimals=1Digits (5,6), 18+11=    0, minimals=1Digits (5,7), 18+11=    1, minimals=1Digits (5,8), 18+11=    0, minimals=1Digits (5,9), 18+11=    0, minimals=1Digits (6,7), 18+11=    1, minimals=1Digits (6,8), 18+11=    0, minimals=1Digits (6,9), 18+11=    0, minimals=1Digits (7,8), 18+11=    0, minimals=1Digits (7,9), 18+11=    0, minimals=1Digits (8,9), 18+11=    0, minimals=11 17-s found.200000000007000000000640800040002000000037000600000900000000700000000023089100000Total time 17.039 seconds.`

Both grids have clique of 11. This is rare, usual clique size is 7 to 9.
The "fast" and "very fast" modes exploit distribution assumptions. The idea came from Coloin in this or the former forums, but I can't find this discussion now.
For the "full" mode the solver is called < 100K times, but from memory the UA/solver balance was optimized for ~3M solver calls. Easy grids.
dobrichev
2016 Supporter

Posts: 1762
Joined: 24 May 2010

### Re: Bands and low-clue puzzles

dobrichev wrote:Below are the timings from the ancient gridchecker for these example 2 grids.
Easy grids.

Collecting key figures, I see

Code: Select all
`Grid 1full       393 s  73683 puzzles checkedfast       103 svery fast   19 s `

Code: Select all
`Grid 2full      1499 s  10309 puzzles checkedfast       108 svery fast   17 s `

The gap between full and fast,very fast is huge, unhappily, in our exercise, we are looking for an exhaustive search.

Compared to the count in the Gary McGuire's process (and somehow in the current code that I have in test), the number of puzzles checked is very low. IMO, this shows that with more UAs, it is possible to reduce that count.

On my side, after a quick step in the processing of early shortages in the UAs list, I saw that it is better to change the internal representation of UAs (3 bands of 27 bits against a 81 bits field) and that more UAs of a specific kind should be collected. I am preparing the corresponding changes.
champagne
2017 Supporter

Posts: 7002
Joined: 02 August 2007
Location: France Brittany

### Re: Bands and low-clue puzzles

In general the grids having 17s are hard. Considering scan of all grids this can have less effect. My observations on maximal cliques size are on less than one hundred "random" grids. The thousands of grids with existing 17s trend to have smaller clique, but not so much smaller. But it is quite possible that I am wrong in conclusions of "average" grid clique size.

The first grid is probably a very special case where no 10+27 valid puzzles exist and the grid must be partitioned on exactly 11+27 givens plus 54+6 givens = 11+6 = 17. Even that 11+27 can be done in 3194 different ways, a simplified algorithm can process this special case fairly fast.
dobrichev
2016 Supporter

Posts: 1762
Joined: 24 May 2010

### Re: Bands and low-clue puzzles

Still going very slow, but some news about the second sample

214378695867295341935641872348962517591837264672514938123456789456789123789123456 morph of entry
2..........7.........64.8...4...2.......37...6.....9........7.........23.891..... morph of target

I have now a draft covering all seen shortages in UAs, requiring one or 2 redundant clues after a valid solution for bands 1+2.

The run time is now significantly below 10 seconds mainly due to the positive effect of Uas having only 2 cells in band 3.

The starting UAs are the following

Code: Select all
`- all bands/stacks UAs (see the first post in that thread)- in bands 1+2  all UAs of size <=12 (as of Gary McGuire process)  all UAs with 2_3 digits  a selection of UAs size <= 20/22 (both tested) with 4-6 digits- as "others" (UAs having cells in band 1+2 and in band 3) only UAs limited to a minirow in band 3  so far, all 4 digits and 5 digits UAs are searched.`

I see still some room for optimization in 2 directions

- starting lot of UAs
- processing of the shortage of UAs in bands 1+2

I tested both limits in the UA size for bands 1+2 and "others" 20 and 22. I see small variations in the results, but nothing clear.
With a limit in size of 22, I hit the ceiling of the size I entered for the UAs tables : 1280 for the UAs in bands 1+2, 1536 for the table of "others"

But optimization will come later, next steps will be to apply the draft to others solution grids and to see if all 17 are produced.
champagne
2017 Supporter

Posts: 7002
Joined: 02 August 2007
Location: France Brittany

### Re: Bands and low-clue puzzles

dobrichev wrote:The "fast" and "very fast" modes exploit distribution assumptions. The idea came from Coloin in this or the former forums, but I can't find this discussion now.

Indeed ... and thanks for persuing with the idea...
and top marks for champagne continuing with the difficult exercise - which is a long running and so far not yet completed project of finding every 17-puzzle..

It may not be apparent what we did ... and maybe some will find this interesting... and maybe some can add

By fixing the 2-clue template [18 of them in a solution grid] what that meant was that we were dealing with a much reduced number of UAs
and also a much reduced number of clues to hit the remaining 7-rookery [63 cells - 7 per box].

The fast mode specifically finds 12 clues which then solve the remaining 7-rookery
The very fast mode specifically finds 11 clues which then solve the remaining 7-rookery
[a very very fast mode would find 10 clues which solve the remaining 7-rookery]
Code: Select all
`+---+---+---+     +---+---+---+     +---+---+---+                        |2..|.7.|...|     |2..|.7.|...|     |2..|...|...|                        |..7|2..|...|     |..7|2..|...|     |..7|...|...|                        |...|...|.72|     |...|64.|872|     |...|64.|8..|                        +---+---+---+     +---+---+---+     +---+---+---+                        |...|..2|..7|     |.4.|..2|..7|     |.4.|..2|...|                        |...|..7|2..|     |...|.37|2..|     |...|.37|...|                        |.72|...|...|     |672|...|9..|     |6..|...|9..|                        +---+---+---+     +---+---+---+     +---+---+---+                        |.2.|...|7..|     |.2.|...|7..|     |...|...|7..|                        |...|7..|.2.|     |...|7..|.23|     |...|...|.23|                        |7..|.2.|...|     |789|12.|...|     |.89|1..|...|                        +---+---+---+     +---+---+---+     +---+---+---+    clue freq  332222210  `

so starting from a solution grid..... fixing all the 2s and 7s we find 11 clues which solve the rest.
Removing 12 clues from the {2,7} 2-rookery gives us 6 clues , which gives us 17 clues which solve the puzzle.

So the fast mode will only find 17s with clue distributions of at least 32xxxxxxxx but not 22xxxxxxx
So the very fast mode will only find 17s with clue distributions of at least 33xxxxxxxx but not 32xxxxxxxor 22xxxxxxx
[A very very fast mode will only find 17s with clue distributions of at least 43xxxxxxx]

Unfortunately without optimization of whatever sort - we cant scan all grids in any reasonable time.

There is a trade off between the number of fixed clues and the number of ways this is represented in a grid, [18 in the 2-rookery case]
the number of added clues, and the number of solutions - with resultant attempt to reduce to 17.

Fixing one box [9 ways], one row [18] one row/col [81] one row and box [54] ... don't seem to provide any advantages ...
coloin

Posts: 1839
Joined: 05 May 2005

### Re: Bands and low-clue puzzles

Hi Coloin,

On my side, I continue to explore the same idea.

Analyzing the first results, it appeared that keeping only "other" UAs limited to 2 cells in band 3 could be costly in the final steps after a shortage of UAs in bands 1+2

So, I changed slightly the lay-out and I am revising the code to handle the new situation.

champagne wrote: The starting UAs are the following

Code: Select all
`- all bands/stacks UAs (see the first post in that thread)- in bands 1+2  all UAs of size <=12 (as of Gary McGuire process)  all UAs with 2_3 digits  a selection of UAs size <= 20/22 (both tested) with 4-6 digits- as "others" (UAs having cells in band 1+2 and in band 3) only UAs limited to a minirow in band 3  so far, all 4 digits and 5 digits UAs are searched.`

The main change here is that "others" having more than 2 cells in band 3 are not lost, but kept in a separate table (limited to-day to 256 UAs, which does not seems enough).

That table is just shrunk till the final steps and used when the table of UAs limited to 2 cells in band 3 is exhausted.

I hope to have tests done by Christmas.
champagne
2017 Supporter

Posts: 7002
Joined: 02 August 2007
Location: France Brittany

### Good and bad news in the search of 17s

The new lay-out for a search of 17s in the catalog is now translated in a draft of code, always in pure C++ (using intrinsic and 128 bits code extensions).

The code can produce all the known 17 out of the corresponding solution grids with a filter to go only in the right branches and was run successfully without filters for the first 500 known 17.

The final run time for the second sample grid was 3.3 seconds to be compared to blue's run of the Gary McGuire' program

Code: Select all
`214378695867295341935641872348962517591837264672514938123456789456789123789123456Inspecting grid no. 2 ...found 407854 hitting sets (32.8382 seconds, average = 64.8574 sec/grid)`

The "relative" bad new is in the average run time for the full lot of solution grids having 17s.The current code is far from optimum but generally speaking, the process is better when one band (or more) has a high minimum number of clues. Our example has a band 3 with a minimum of 6 clues.

For the first 500 solution grids, (in fact 494) the average time/grid is 126 seconds, with a minimum below one second and a maximum of 37 minutes.

The distribution of time/grid seems very erratic, but it grows when the minimum number of clues in band 3 goes down.

Here below is a sample of "bad cases" in a part of the file where we had a higher density of such cases. Each case is split in 2 lines

The solution grid searched
One known 17 (usually only 1) followed by the run time for that solution grid.

(the run time is "as of the current code" subject to...) After 500 valid runs, most of the bugs should be fixed, but ...

Hidden Text: Show
Code: Select all
`275961348348572916691834572564297831837615294912348657123456789456789123789123465  morph of entry.........3......16...8.4....64...8......1..9...2......1...56..........23......4..  10m 27s 615ms n447214365897378941256695872431531297648867534912942618375123456789456789123789123564  morph of entry....6....3.8..1.....5...4.....2.7..8.6........4........2.4..7......8...3..9......  37m 39s 629ms n457395248617671935842842671395214367958567894231938512476123456789456789123789123564  morph of entry3..2........9..8...4......521...........94.3..................9......12.78...3...  16m 13s 933ms n459214367958695814372837592416123456789456789123789123564362975841548231697971648235  morph of entry...3...5..9.8...7........161...56.............89.........9..8..5....1.........2..  24m 41s 133ms n460214537698678914352935268471361895247597342816842671935123456789456789123789123564  morph of entry...5...9..78..............13.1..........428......7.....2....7......8...3..91.....  19m 50s 513ms n464123456789456789123789123564214538697675291348938647215342915876597862431861374952  morph of entry..3...7.......9.2..8.1.....2...............489....7....4....8......62....6.....5.  10m 59s 014ms n465214597836367248915895631472123456789456789123789123564531864297648972351972315648  morph of entry....9...636......58........1......8....7....3..9.2......1...29.............3.5...  16m 2s 329ms n469214597836368214975975368412531842697647931258892675341123456789456789123789123564  morph of entry2...9........14..5.7....4...3....6.....9..........53..1.......9.......2..8...3...  31m 57s 837ms n470347961258561842397892375641214597836638214975975638412123456789456789123789123564  morph of entry...9......6....3.......56..2...9........14..5.7....4..1.......9.......2..8...3...  18m 17s 309ms n471123456789456789123789123564214637958635891472897542316372965841568314297941278635  morph of entry............7...23.89.......1....9.8........2...54....3.2.6..4.5.............8...  10m 2s 339ms n474214695378375841692968237415123456789456789123789123564597312846642578931831964257  morph of entry.1..........84..9..6......5....56...4......2....1.3...........6.......318..9.....  17m 34s 895ms n479 (2x17)214695378375841692968372415123456789456789123789123564547218936692537841831964257  morph of entry.1..........84..9..6......5....56...4......2....1.3...........6......8.18..9.....  16m 48s 486ms n481 (2x17)214867395675394812938512476123456789456789123789123564367241958591638247842975631  morph of entry.....7..5.....48...3.......1...56......7...23........4..72.........3....8.....6..  16m 20s 120ms n492214867395867395412935241678342678951578914236691532847123456789456789123789123564  morph of entry21...7....6...........4..783..........8.....6.....2....2...........8.1.37.9......  23m 37s 783ms n493`

I start investigations to clarify the source of the high run time, but it is already clear that the UAs structure is the main reason as we can see in the next table.

Code: Select all
`214365897378941256695872431531297648867534912942618375123456789456789123789123564  morph of entryn 457   37m 39s 629ms4         band 3 minimum clues number of 2 885 290 025      solutions generated for bands 1+25.34         composed average number of cells per step`

Code: Select all
`214638975597241638638975241341597862862314597975862314123456789456789123789123456  morph of entryn=7   0s 976ms6         band 3 minimum clues number of350 769         solutions generated for bands 1+23.19         composed average number of cells per step`

The next step will be to study "worse cases" and to optimize the process towards such cases, avoiding penalties for the other ones. I have in mind a simpler and more efficient way to have benefit of the UAs with 2 cells in band 3.

Note to blue

Reference times for all or part the list of worse cases in the Gary McGuire process would be helpful
champagne
2017 Supporter

Posts: 7002
Joined: 02 August 2007
Location: France Brittany

### Re: Bands and low-clue puzzles

Hi Champagne,

If you are looking for worst cases in McGuire's process, see these 3 grids that are known to have least UA4 + UA6
Code: Select all
`123456789456789231789231564234968175867125493915374826348617952592843617671592348123456789456789132789213645275941368638527914941638257394175826517862493862394571123456789456789231789231564234968175867125493915374826348617952592843617671592348`

The were discussed years ago. All of them have no 17-clue puzzles.

BTW I spent several days in reproducing (not on 100%) the McGuire's algorithm. At the moment I hope I have a working process capable for further experimenting.
The source is in gridchecker available at github. Latest commits are incremental updates of what I did in the last weeks. Today's commit is this. Previous intermediate commits are more readable and have almost the same performance.

Here are the results for the topmost grid in your post.
Code: Select all
`2759613483485729166918345725642978318376152949123486571234567894567891237891234654=0   6=24   8=14   9=6   10=64   11=70   12=207   13=98   14=281   15=273   16=519   17=530   18=935   19=839   ua =768   ua2=12800   ua3=32768   ua4=65536   ua5=40960   ua6=32768.........3......16...8.4....64...8......1..9...2......1...56..........23......4..4516115(0%)   4043M(8%)   10623M(32%)   6749M(85%)   1644M(95%)   358M(99%)   time 1309.200 seconds.`

The rows are grid; number of UA per size; num of composite UA generated at startup; the puzzles found; the number of times the algorithm passes the UA checks for ordinary and composite UA, the percentage of the successful passes; time.
I am sure that this time can be at least halved by adjusting some parameters, but it would make other grids processing worse.
I fully agree that the timing considerably varies from grid to grid. My early attempts in evaluating each grid (by analyzing UA distribution or even make a forecast run over the first 10 clues), and then processing it with most appropriate parameters (UA reordering, composite UA thresholds, buffer sizes) were unsuccessful.

For your 2 test grids with 6-clue band 3 the best time is 30.8 and 35.8 seconds, but optimizing to mainstream grids the time varies between 44 and 51 seconds.
Injecting an artificial UA of order 6 covering band 3 doesn't improve the processing. McGuire's process favors short UA.
dobrichev
2016 Supporter

Posts: 1762
Joined: 24 May 2010

### Re: Bands and low-clue puzzles

dobrichev wrote:If you are looking for worst cases in McGuire's process, see these 3 grids that are known to have least UA4 + UA6

It's good to have them, I'll make preliminary test on them very soon. However, to have more debugging possibilities, I'am currently working with a code assuming that at least one known 17 exists. I prefer to do most of the tests on the lot of known 17 and then only, to start the work on a sample of the catalog. Anyway, as you write the process has to be optimized on a wide sample of solution grids, not on the worst cases.

dobrichev wrote:Here are the results for the topmost grid in your post.
Code: Select all
`275961348348572916691834572564297831837615294912348657123456789456789123789123465time 1309.200 seconds.`

As my run lasted 600 seconds, this is in line with my expectation. In that solution grid (5 clues as minimum in band 3) the program generated 661 millions sub grids with 12 clues in band 1+2 plus 44 million shortages in UAs (sub grids bands 1+2 with less than 12 clues). The current code is far from optimum to handle such situations, (my next task on the to do list) but producing the bands 1+2 and nothing more takes already one and half minute and this is a part of the program that I don't think to change in the near future.

dobrichev wrote:Hi Champagne,
For your 2 test grids with 6-clue band 3 the best time is 30.8 and 35.8 seconds, but optimizing to mainstream grids the time varies between 44 and 51 seconds.
McGuire's process favors short UA.

As in the McGuire's process, my code takes in priority short UAs (and nothing more, I made several alternative tests, without any clear success).
For the 2 first grids, the response came in respectively 8 and 3.3 seconds, Again, we see that the performance ratio is very dependent on the grid

8/30.8 for the first
3.3/35.8 for the second

It will not be easy to make any forecast. The main parameters, IMO, are the following

- What is the proportion of short UAs belonging to the bands 1+2,
- What is the average count of mini rows still active in band 3 when a solution is produced

Note for other readers: where we are, precise bench marking is premature, time comparisons are just giving indications.
champagne
2017 Supporter

Posts: 7002
Joined: 02 August 2007
Location: France Brittany

### Re: Bands and low-clue puzzles

dobrichev wrote:Hi Champagne,

If you are looking for worst cases in McGuire's process, see these 3 grids that are known to have least UA4 + UA6
Code: Select all
`123456789456789231789231564234968175867125493915374826348617952592843617671592348123456789456789132789213645275941368638527914941638257394175826517862493862394571123456789456789231789231564234968175867125493915374826348617952592843617671592348`

The were discussed years ago. All of them have no 17-clue puzzles.

I had a look at them and I am sure that they will be "very bad cases" in my process as well.
2 of them have a minimum number of clues in band 3 of three, already a bad case for me and the third one has a minimum band 3 of four clues.

But, again, the key point is that the number of bands 1+2 generated is huge (billions), what I could expect after your remark on the small number of UA4 UA6.

The run time could be 3/4 times more than for my current worst case.
champagne
2017 Supporter

Posts: 7002
Joined: 02 August 2007
Location: France Brittany

PreviousNext