The New Sudoku Players' Forum

[blue]

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)

[champagne]

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

[blue]

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 152380
5+6+27 604868
6+5+27 320825
7+4+27   5865

[champagne]

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]

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

Code: Select all

214378695867295341935641872348962517591837264672514938123456789456789123789123456  morph of entry
2..........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    93
5  7842
4 38127
3   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+2

still 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=2
1............................................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=10

A 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=2
1............................................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.

[dobrichev]

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 --unav4
Loading UA sets from file b6b.unav.txt
Saving 11163 UA sets to file b6b.unav.txt

MCN=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

maxPositionLimitsByUA
04 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 --unav12
Digits (1,2), 18+12= 2226, minimals=0
Digits (1,3), 18+11=    4, minimals=0
Digits (1,4), 18+12= 2183, minimals=0
Digits (1,5), 18+11=   34, minimals=0
Digits (1,6), 18+11=   22, minimals=0
Digits (1,7), 18+12= 1537, minimals=0
Digits (1,8), 18+12= 5070, minimals=0
Digits (1,9), 18+11=   21, minimals=0
Digits (2,3), 18+11=   19, minimals=0
Digits (2,4), 18+11=    1, minimals=0
Digits (2,5), 18+12= 1106, minimals=0
Digits (2,6), 18+11=    2, minimals=0
Digits (2,7), 18+11=   12, minimals=0
Digits (2,8), 18+11=    1, minimals=0
Digits (2,9), 18+11=   46, minimals=0
Digits (3,4), 18+11=   21, minimals=0
Digits (3,5), 18+12= 2253, minimals=0
Digits (3,6), 18+11=    1, minimals=0
Digits (3,7), 18+11=    1, minimals=0
Digits (3,8), 18+11=    2, minimals=0
Digits (3,9), 18+11=   28, minimals=1
Digits (4,5), 18+12= 1172, minimals=1
Digits (4,6), 18+12= 1518, minimals=1
Digits (4,7), 18+12= 2366, minimals=1
Digits (4,8), 18+11=    3, minimals=1
Digits (4,9), 18+11=    1, minimals=1
Digits (5,6), 18+11=    1, minimals=1
Digits (5,7), 18+11=    1, minimals=1
Digits (5,8), 18+11=    3, minimals=1
Digits (5,9), 18+12= 1338, minimals=1
Digits (6,7), 18+12= 1779, minimals=1
Digits (6,8), 18+11=    1, minimals=1
Digits (6,9), 18+12= 1139, minimals=1
Digits (7,8), 18+12= 1350, minimals=1
Digits (7,9), 18+11=    1, minimals=1
Digits (8,9), 18+12= 2292, minimals=1
1 17-s found.
000000700000000023089100000200000000007900000030000064008000910000034000000000000

Total time 102.900 seconds.

#very fast search, would find 87% of the known 17s
$ ./gridchecker --scan --gridfile b6b --veryfast17 --unav12
Digits (1,2), 18+11=    0, minimals=0
Digits (1,3), 18+11=    4, minimals=0
Digits (1,4), 18+11=    0, minimals=0
Digits (1,5), 18+11=   34, minimals=0
Digits (1,6), 18+11=   22, minimals=0
Digits (1,7), 18+11=    0, minimals=0
Digits (1,8), 18+11=    0, minimals=0
Digits (1,9), 18+11=   21, minimals=0
Digits (2,3), 18+11=   19, minimals=0
Digits (2,4), 18+11=    1, minimals=0
Digits (2,5), 18+11=    0, minimals=0
Digits (2,6), 18+11=    2, minimals=0
Digits (2,7), 18+11=   12, minimals=0
Digits (2,8), 18+11=    1, minimals=0
Digits (2,9), 18+11=   46, minimals=0
Digits (3,4), 18+11=   21, minimals=0
Digits (3,5), 18+11=    0, minimals=0
Digits (3,6), 18+11=    1, minimals=0
Digits (3,7), 18+11=    1, minimals=0
Digits (3,8), 18+11=    2, minimals=0
Digits (3,9), 18+11=   28, minimals=1
Digits (4,5), 18+11=    0, minimals=1
Digits (4,6), 18+11=    0, minimals=1
Digits (4,7), 18+11=    0, minimals=1
Digits (4,8), 18+11=    3, minimals=1
Digits (4,9), 18+11=    1, minimals=1
Digits (5,6), 18+11=    1, minimals=1
Digits (5,7), 18+11=    1, minimals=1
Digits (5,8), 18+11=    3, minimals=1
Digits (5,9), 18+11=    0, minimals=1
Digits (6,7), 18+11=    0, minimals=1
Digits (6,8), 18+11=    1, minimals=1
Digits (6,9), 18+11=    0, minimals=1
Digits (7,8), 18+11=    0, minimals=1
Digits (7,9), 18+11=    1, minimals=1
Digits (8,9), 18+11=    0, minimals=1
1 17-s found.
000000700000000023089100000200000000007900000030000064008000910000034000000000000

Total time 19.479 seconds.


Hidden Text: Show

Code: Select all

214378695867295341935641872348962517591837264672514938123456789456789123789123456

#full scan
$ gridchecker --verbose --scan --gridfile b6 --unav12 --unav4
Loading UA sets from file b6.unav.txt
0 UA sets loaded.
Saving 9593 UA sets to file b6.unav.txt

MCN=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

maxPositionLimitsByUA
04 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.013h

Searched 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 --unav12
Digits (1,2), 18+12=  942, minimals=0
Digits (1,3), 18+11=    1, minimals=0
Digits (1,4), 18+12=  353, minimals=0
Digits (1,5), 18+12=  600, minimals=0
Digits (1,6), 18+12=  804, minimals=0
Digits (1,7), 18+12= 6517, minimals=0
Digits (1,8), 18+12= 3110, minimals=0
Digits (1,9), 18+11=    1, minimals=0
Digits (2,3), 18+11=    5, minimals=0
Digits (2,4), 18+11=    3, minimals=0
Digits (2,5), 18+12=    9, minimals=0
Digits (2,6), 18+12=  317, minimals=1
Digits (2,7), 18+11=    2, minimals=1
Digits (2,8), 18+12=  732, minimals=1
Digits (2,9), 18+12=  665, minimals=1
Digits (3,4), 18+11=    3, minimals=1
Digits (3,5), 18+12= 1131, minimals=1
Digits (3,6), 18+12=  165, minimals=1
Digits (3,7), 18+11=   10, minimals=1
Digits (3,8), 18+12= 1352, minimals=1
Digits (3,9), 18+11=    4, minimals=1
Digits (4,5), 18+12=  205, minimals=1
Digits (4,6), 18+12= 1401, minimals=1
Digits (4,7), 18+12=  298, minimals=1
Digits (4,8), 18+11=    2, minimals=1
Digits (4,9), 18+12=  388, minimals=1
Digits (5,6), 18+12=  124, minimals=1
Digits (5,7), 18+11=    1, minimals=1
Digits (5,8), 18+12=  293, minimals=1
Digits (5,9), 18+12=  233, minimals=1
Digits (6,7), 18+11=    1, minimals=1
Digits (6,8), 18+12= 2312, minimals=1
Digits (6,9), 18+12=  980, minimals=1
Digits (7,8), 18+12=  472, minimals=1
Digits (7,9), 18+12= 1855, minimals=1
Digits (8,9), 18+12=  612, minimals=1
1 17-s found.
200000000007000000000640800040002000000037000600000900000000700000000023089100000

Total time 108.178 seconds.

#very fast 87%
$ ./gridchecker --scan --gridfile b6a --veryfast17 --unav12
Digits (1,2), 18+11=    0, minimals=0
Digits (1,3), 18+11=    1, minimals=0
Digits (1,4), 18+11=    0, minimals=0
Digits (1,5), 18+11=    0, minimals=0
Digits (1,6), 18+11=    0, minimals=0
Digits (1,7), 18+11=    0, minimals=0
Digits (1,8), 18+11=    0, minimals=0
Digits (1,9), 18+11=    1, minimals=0
Digits (2,3), 18+11=    5, minimals=0
Digits (2,4), 18+11=    3, minimals=0
Digits (2,5), 18+11=    0, minimals=0
Digits (2,6), 18+11=    0, minimals=0
Digits (2,7), 18+11=    2, minimals=1
Digits (2,8), 18+11=    0, minimals=1
Digits (2,9), 18+11=    0, minimals=1
Digits (3,4), 18+11=    3, minimals=1
Digits (3,5), 18+11=    0, minimals=1
Digits (3,6), 18+11=    0, minimals=1
Digits (3,7), 18+11=   10, minimals=1
Digits (3,8), 18+11=    0, minimals=1
Digits (3,9), 18+11=    4, minimals=1
Digits (4,5), 18+11=    0, minimals=1
Digits (4,6), 18+11=    0, minimals=1
Digits (4,7), 18+11=    0, minimals=1
Digits (4,8), 18+11=    2, minimals=1
Digits (4,9), 18+11=    0, minimals=1
Digits (5,6), 18+11=    0, minimals=1
Digits (5,7), 18+11=    1, minimals=1
Digits (5,8), 18+11=    0, minimals=1
Digits (5,9), 18+11=    0, minimals=1
Digits (6,7), 18+11=    1, minimals=1
Digits (6,8), 18+11=    0, minimals=1
Digits (6,9), 18+11=    0, minimals=1
Digits (7,8), 18+11=    0, minimals=1
Digits (7,9), 18+11=    0, minimals=1
Digits (8,9), 18+11=    0, minimals=1
1 17-s found.
200000000007000000000640800040002000000037000600000900000000700000000023089100000

Total 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.

[champagne]

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

Hi mladen,

I jump to the conclusion with a side question: what about "hard grids"

Collecting key figures, I see

Code: Select all

Grid 1
full       393 s  73683 puzzles checked
fast       103 s
very fast   19 s
 

Code: Select all

Grid 2
full      1499 s  10309 puzzles checked
fast       108 s
very 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.

[dobrichev]

I jump to the conclusion with a side question: what about "hard grids"

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.

[champagne]

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.

[coloin]

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 ...

[champagne]

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.

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]

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

214378695867295341935641872348962517591837264672514938123456789456789123789123456
Inspecting 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 n447

214365897378941256695872431531297648867534912942618375123456789456789123789123564  morph of entry
....6....3.8..1.....5...4.....2.7..8.6........4........2.4..7......8...3..9......  37m 39s 629ms n457

395248617671935842842671395214367958567894231938512476123456789456789123789123564  morph of entry
3..2........9..8...4......521...........94.3..................9......12.78...3...  16m 13s 933ms n459

214367958695814372837592416123456789456789123789123564362975841548231697971648235  morph of entry
...3...5..9.8...7........161...56.............89.........9..8..5....1.........2..  24m 41s 133ms n460

214537698678914352935268471361895247597342816842671935123456789456789123789123564  morph of entry
...5...9..78..............13.1..........428......7.....2....7......8...3..91.....  19m 50s 513ms n464

123456789456789123789123564214538697675291348938647215342915876597862431861374952  morph of entry
..3...7.......9.2..8.1.....2...............489....7....4....8......62....6.....5.  10m 59s 014ms n465

214597836367248915895631472123456789456789123789123564531864297648972351972315648  morph of entry
....9...636......58........1......8....7....3..9.2......1...29.............3.5...  16m 2s 329ms n469

214597836368214975975368412531842697647931258892675341123456789456789123789123564  morph of entry
2...9........14..5.7....4...3....6.....9..........53..1.......9.......2..8...3...  31m 57s 837ms n470

347961258561842397892375641214597836638214975975638412123456789456789123789123564  morph of entry
...9......6....3.......56..2...9........14..5.7....4..1.......9.......2..8...3...  18m 17s 309ms n471

123456789456789123789123564214637958635891472897542316372965841568314297941278635  morph of entry
............7...23.89.......1....9.8........2...54....3.2.6..4.5.............8...  10m 2s 339ms n474

214695378375841692968237415123456789456789123789123564597312846642578931831964257  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 n492

214867395867395412935241678342678951578914236691532847123456789456789123789123564  morph of entry
21...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 entry
n 457   37m 39s 629ms
4         band 3 minimum clues number of
2 885 290 025      solutions generated for bands 1+2
5.34         composed average number of cells per step


Code: Select all

214638975597241638638975241341597862862314597975862314123456789456789123789123456  morph of entry
n=7   0s 976ms
6         band 3 minimum clues number of
350 769         solutions generated for bands 1+2
3.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

[dobrichev]

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

123456789456789231789231564234968175867125493915374826348617952592843617671592348
123456789456789132789213645275941368638527914941638257394175826517862493862394571
123456789456789231789231564234968175867125493915374826348617952592843617671592348


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

275961348348572916691834572564297831837615294912348657123456789456789123789123465
4=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.

[champagne]

Hi mladen,

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.

Here are the results for the topmost grid in your post.

Code: Select all

275961348348572916691834572564297831837615294912348657123456789456789123789123465
time 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.

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]

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

123456789456789231789231564234968175867125493915374826348617952592843617671592348
123456789456789132789213645275941368638527914941638257394175826517862493862394571
123456789456789231789231564234968175867125493915374826348617952592843617671592348


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

Hi mladen,

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.