The New Sudoku Players' Forum

[blue]

Waiting now for Blue's first shot

The code doesn't actually run a single grid at a time, due to the "divide and conquer" approach.

I can run a crippled version, that does to that, but I still need to run two passes.
One pass catches 17's where one band (or stack) has 7 or more clues.
The other catches 17's that are 6+6+5 in both directions.

The outputs for the 100 grids, are below.
Adding the averages, it's ~1.57 seconds per grid.

The normal code, runs in two passes over 983,959,110 (ED) band 1&2 fills, and takes ~1.04s total, per "input".
Multiplying by (983,959,110 inputs)/(5,472,730,538 canonical grids), gives ~0.19s per grid.

N+x+y,N>=7:

Hidden Text: Show

grid 1: 0.25s, avg = 0.249602s
grid 2: 0.11s, avg = 0.179401s
grid 3: 0.23s, avg = 0.197601s
grid 4: 0.09s, avg = 0.171601s
grid 5: 0.45s, avg = 0.227761s
grid 6: 0.06s, avg = 0.200201s
grid 7: 0.16s, avg = 0.193887s
grid 8: 0.08s, avg = 0.179401s
grid 9: 0.45s, avg = 0.209735s
grid 10: 0.06s, avg = 0.195001s
grid 11: 0.44s, avg = 0.216983s
grid 12: 0.11s, avg = 0.208001s
grid 13: 0.73s, avg = 0.248402s
grid 14: 0.11s, avg = 0.238459s
grid 15: 0.33s, avg = 0.244402s
grid 16: 0.14s, avg = 0.237902s
grid 17: 0.80s, avg = 0.270708s
grid 18: 0.22s, avg = 0.267802s
grid 19: 0.09s, avg = 0.258633s
grid 20: 0.47s, avg = 0.269102s
grid 21: 0.11s, avg = 0.261487s
grid 22: 0.16s, avg = 0.256693s
grid 23: 0.05s, avg = 0.247567s
grid 24: 0.66s, avg = 0.264552s
grid 25: 0.12s, avg = 0.258962s
grid 26: 0.19s, avg = 0.256202s
grid 27: 0.31s, avg = 0.258268s
grid 28: 0.17s, avg = 0.255173s
grid 29: 0.09s, avg = 0.249602s
grid 30: 0.30s, avg = 0.251162s
grid 31: 0.17s, avg = 0.248595s
grid 32: 0.08s, avg = 0.243264s
grid 33: 0.76s, avg = 0.259056s
grid 34: 0.09s, avg = 0.254190s
grid 35: 0.14s, avg = 0.250939s
grid 36: 0.19s, avg = 0.249168s
grid 37: 0.06s, avg = 0.244120s
grid 38: 0.58s, avg = 0.252886s
grid 39: 0.12s, avg = 0.249602s
grid 40: 0.64s, avg = 0.259352s
grid 41: 0.11s, avg = 0.255689s
grid 42: 0.08s, avg = 0.251459s
grid 43: 0.14s, avg = 0.248876s
grid 44: 0.08s, avg = 0.244992s
grid 45: 0.06s, avg = 0.240935s
grid 46: 0.06s, avg = 0.237054s
grid 47: 0.42s, avg = 0.240972s
grid 48: 0.47s, avg = 0.245702s
grid 49: 0.25s, avg = 0.245781s
grid 50: 0.06s, avg = 0.242114s
grid 51: 0.12s, avg = 0.239813s
grid 52: 0.17s, avg = 0.238502s
grid 53: 0.42s, avg = 0.241949s
grid 54: 0.20s, avg = 0.241224s
grid 55: 0.27s, avg = 0.241660s
grid 56: 1.44s, avg = 0.262973s
grid 57: 0.05s, avg = 0.259181s
grid 58: 0.12s, avg = 0.256864s
grid 59: 0.14s, avg = 0.254890s
grid 60: 1.15s, avg = 0.269882s
grid 61: 0.37s, avg = 0.271595s
grid 62: 0.05s, avg = 0.267969s
grid 63: 0.17s, avg = 0.266440s
grid 64: 0.34s, avg = 0.267639s
grid 65: 0.03s, avg = 0.264002s
grid 66: 0.20s, avg = 0.263074s
grid 67: 1.19s, avg = 0.276844s
grid 68: 0.12s, avg = 0.274608s
grid 69: 0.31s, avg = 0.275150s
grid 70: 0.28s, avg = 0.275230s
grid 71: 0.08s, avg = 0.272452s
grid 72: 0.16s, avg = 0.270835s
grid 73: 0.42s, avg = 0.272895s
grid 74: 0.09s, avg = 0.270472s
grid 75: 0.09s, avg = 0.268114s
grid 76: 0.42s, avg = 0.270128s
grid 77: 0.06s, avg = 0.267430s
grid 78: 0.33s, avg = 0.268202s
grid 79: 0.22s, avg = 0.267571s
grid 80: 0.08s, avg = 0.265202s
grid 81: 0.20s, avg = 0.264431s
grid 82: 0.08s, avg = 0.262158s
grid 83: 0.50s, avg = 0.265014s
grid 84: 0.19s, avg = 0.264087s
grid 85: 0.95s, avg = 0.272176s
grid 86: 0.19s, avg = 0.271188s
grid 87: 0.05s, avg = 0.268609s
grid 88: 0.34s, avg = 0.269456s
grid 89: 0.55s, avg = 0.272564s
grid 90: 0.20s, avg = 0.271788s
grid 91: 0.12s, avg = 0.270173s
grid 92: 0.05s, avg = 0.267745s
grid 93: 0.14s, avg = 0.266376s
grid 94: 0.28s, avg = 0.266529s
grid 95: 0.06s, avg = 0.264381s
grid 96: 0.41s, avg = 0.265852s
grid 97: 0.30s, avg = 0.266167s
grid 98: 0.47s, avg = 0.268226s
grid 99: 0.03s, avg = 0.265832s
grid 100: 0.42s, avg = 0.267386s

2x(6+6+5):

Hidden Text: Show

grid 1: 1.06s, avg = 1.060807s
grid 2: 1.01s, avg = 1.037407s
grid 3: 0.89s, avg = 0.988006s
grid 4: 0.47s, avg = 0.858006s
grid 5: 1.50s, avg = 0.985926s
grid 6: 0.16s, avg = 0.847605s
grid 7: 1.15s, avg = 0.891434s
grid 8: 0.80s, avg = 0.879456s
grid 9: 2.20s, avg = 1.026140s
grid 10: 0.08s, avg = 0.931326s
grid 11: 1.84s, avg = 1.014006s
grid 12: 0.94s, avg = 1.007506s
grid 13: 2.56s, avg = 1.126807s
grid 14: 1.09s, avg = 1.124321s
grid 15: 2.90s, avg = 1.242808s
grid 16: 0.69s, avg = 1.208033s
grid 17: 5.29s, avg = 1.448056s
grid 18: 0.89s, avg = 1.417009s
grid 19: 0.92s, avg = 1.390872s
grid 20: 2.65s, avg = 1.453929s
grid 21: 1.17s, avg = 1.440409s
grid 22: 0.33s, avg = 1.389827s
grid 23: 0.11s, avg = 1.334148s
grid 24: 3.53s, avg = 1.425459s
grid 25: 1.22s, avg = 1.417113s
grid 26: 1.11s, avg = 1.405209s
grid 27: 1.36s, avg = 1.403431s
grid 28: 1.08s, avg = 1.391752s
grid 29: 1.08s, avg = 1.380878s
grid 30: 1.25s, avg = 1.376449s
grid 31: 1.05s, avg = 1.365764s
grid 32: 0.37s, avg = 1.334784s
grid 33: 1.15s, avg = 1.329318s
grid 34: 0.41s, avg = 1.302150s
grid 35: 0.97s, avg = 1.292580s
grid 36: 0.87s, avg = 1.280942s
grid 37: 0.12s, avg = 1.249694s
grid 38: 0.80s, avg = 1.237745s
grid 39: 0.33s, avg = 1.214408s
grid 40: 2.68s, avg = 1.251128s
grid 41: 0.44s, avg = 1.231266s
grid 42: 0.25s, avg = 1.207893s
grid 43: 0.70s, avg = 1.196129s
grid 44: 0.09s, avg = 1.171071s
grid 45: 0.31s, avg = 1.151981s
grid 46: 0.28s, avg = 1.133042s
grid 47: 1.19s, avg = 1.134160s
grid 48: 1.79s, avg = 1.147907s
grid 49: 1.70s, avg = 1.159183s
grid 50: 0.14s, avg = 1.138807s
grid 51: 0.33s, avg = 1.122901s
grid 52: 1.64s, avg = 1.132807s
grid 53: 1.36s, avg = 1.137041s
grid 54: 0.81s, avg = 1.131007s
grid 55: 1.22s, avg = 1.132567s
grid 56: 3.70s, avg = 1.178365s
grid 57: 0.19s, avg = 1.160976s
grid 58: 1.00s, avg = 1.158173s
grid 59: 0.95s, avg = 1.154672s
grid 60: 11.76s, avg = 1.331469s
grid 61: 1.29s, avg = 1.330868s
grid 62: 0.33s, avg = 1.314686s
grid 63: 0.81s, avg = 1.306694s
grid 64: 0.76s, avg = 1.298221s
grid 65: 0.14s, avg = 1.280408s
grid 66: 0.47s, avg = 1.268099s
grid 67: 3.24s, avg = 1.297602s
grid 68: 0.27s, avg = 1.282420s
grid 69: 2.03s, avg = 1.293226s
grid 70: 1.00s, avg = 1.289014s
grid 71: 0.70s, avg = 1.280746s
grid 72: 0.33s, avg = 1.267508s
grid 73: 2.85s, avg = 1.289252s
grid 74: 0.98s, avg = 1.285111s
grid 75: 0.58s, avg = 1.275672s
grid 76: 1.97s, avg = 1.284750s
grid 77: 0.33s, avg = 1.272320s
grid 78: 1.68s, avg = 1.277608s
grid 79: 0.30s, avg = 1.265188s
grid 80: 0.16s, avg = 1.251323s
grid 81: 1.05s, avg = 1.248778s
grid 82: 0.30s, avg = 1.237164s
grid 83: 4.98s, avg = 1.282215s
grid 84: 0.73s, avg = 1.275680s
grid 85: 3.82s, avg = 1.305637s
grid 86: 1.23s, avg = 1.304785s
grid 87: 0.39s, avg = 1.294270s
grid 88: 4.21s, avg = 1.327427s
grid 89: 3.28s, avg = 1.349321s
grid 90: 0.34s, avg = 1.338142s
grid 91: 0.45s, avg = 1.328409s
grid 92: 0.19s, avg = 1.316004s
grid 93: 0.83s, avg = 1.310744s
grid 94: 1.26s, avg = 1.310242s
grid 95: 0.67s, avg = 1.303512s
grid 96: 1.54s, avg = 1.306021s
grid 97: 1.87s, avg = 1.311856s
grid 98: 0.89s, avg = 1.307543s
grid 99: 0.11s, avg = 1.295439s
grid 100: 2.25s, avg = 1.304948s

[champagne]

hoops, waiting for more
congratulations, this is in the range expected to check if we have all 17s

[champagne]

Hi Blue,

After your exciting results, one question before I leave home for my trip.

When you say that you have a pass testing one band >=7 clues, does it mean that you have a major loop testing the 6 bands/stacks (which would make sense to me).

[blue]

Hi champagne,

When you say that you have a pass testing one band >=7 clues, does it mean that you have a major loop testing the 6 bands/stacks (which would make sense to me).

Yes.

[dobrichev]

Blue, that is impressive! Finally you got it! Congratulations!

May I guess that you use UA projections over the row/column axes?

[blue]

May I guess that you use UA projections over the row/column axes?

I'm not sure what you mean.
It sounds interesting. Would you explain ?

It does something like that (maybe?) with UA2's, that allows/"helps with the idea of" sharing the work across the various ways of filling band 3.

A "UA2": For a valid x+y+27 puzzle (and its solution), is two cells in the same mini-row in band 3, where if both band 3 clues were removed, the x+y+25 puzzle would have multiple solutions. For that to be true there must be a UA for the solution grid, that uses only the two cells from band 3, and then additional cells from bands 1&2, that don't include cells from the "x+y" part of the puzzle.

The code keeps 81 lists/queues that have information about the band 1&2 parts of the larger UA's (like that), that have been found in earlier testing. The number 81, comes from 9 ways to choose columns A and B, with A < B and A & B in the same stack, 3 ways to choose a digit from column A, and 3 ways to choose a digit from column B.

That's the closest I come to the idea of a "projection".

[ Edit: corrected/augmented the wording in the "It does something like that ..." sentence. ]

[dobrichev]

You explained it better.

Nevertheless I will try to explain it in my words. Below is an example of my understanding.

Gangs (of 44) for band 1,2 and 3 are fixed, the 2-digit UA cells are marked with "x".

Code: Select all

  |  . . .   . . .   . . .   Case A, U8
  |  . . .   . . .   . . .   
  |  . . .   . . .   . . .   
  |
 R|  x . .   . . .   . . x   
 R|  . . x   . . .   . . x   
  |  . . .   . . .   . . .   
  |  U   U               U   Projection of the Up partition
  |-----------------------------cutting line
  |  D   D       D           Projection of the Down partition
 R|  . . x   . . x   . . .   
  |  . . .   . . .   . . .   
 R|  x . .   . . x   . . .   
================================
     I   I                   Intersection of U and D are the transition positions between the partitions


Code: Select all

  |  . . .   . . .   . . .   Case B, U4
  |  . . .   . . .   . . .   
  |  . . .   . . .   . . .   
  |
 R|  x . x   . . .   . . .   
  |  . . .   . . .   . . .   
  |  . . .   . . .   . . .   
  |  U   U                   Projection of the Up partition
  |-----------------------------cutting line
  |  D   D                   Projection of the Down partition
 R|  x . x   . . .   . . .   
  |  . . .   . . .   . . .   
  |  . . .   . . .   . . .   
================================
     I   I                   Intersection of U and D are the transition positions between the partitions


So, the bands 1,2 "export" partial UA set trough the crossing line to band 3. The columns marked with "I".
This export (or bridge?) depends on gang 1 and 2, and once created in one of the partitions, it must have its counterpart - gang 3.

The projection marked with R, as well as U and D, depend on band (of 416), and could be either ignored, or used for eventual gang-to-band expansion and/or row permutations.
Projections U and D, could be either ignored, or used for stack/column permutations in eventual "expansion" phase.

In the following example it is more complicated since the UA8 can degenerate to 2xUA4, and this depends on intra-partition permutations. Of course the bridge isn't in a single minirow.

Code: Select all

  |  . . .   . . .   . . .   Case C, U8 that isn't trivial to cover
  |  . . .   . . .   . . .   
  |  . . .   . . .   . . .   
  |
 R|  x . x   . . .   . . .   
 R|  . . .   . . .   x . x   
  |  . . .   . . .   . . .   
  |  U   U           U   U   Projection of the Up partition
  |-----------------------------cutting line
  |  D   D           D   D   Projection of the Down partition
 R|  . . x   . . .   x . .   
  |  . . .   . . .   . . .   
 R|  x . .   . . .   . . x   
================================
     I   I           I   I   Intersection of U and D are the transition positions between the partitions


Since the most closer to per-band/gang partitioning is the per-template/rookery partitioning, I tried to find analog there. It should be keeping a track whether particular UA lies entirely within a chosen partition (say digits 1,2,3, analog to a UA located entirely in band 3 when partitioning by bands), or it forms bridge to other partition (say digits 4,5,6,7,8,9, analog to bands 1,2).

I am waiting with interest for more details on your solution, when you are ready.

[dobrichev]

BTW your 81 queues/lists are close to a possible signature of gang 3, which could be used also as a start point (most outer loop).
Note that a UA with your AB columns is possible to expand to other columns in band 3 w/o interference with bands 1,2. This is seen when comparing band 3 between Case A and Case B in my example. For the same reason large and complicated (and therefore not used in the search) UA can exist in one of the partitions but the bridge can remain simple 2 columns in the same minirow.

[eleven]

blue,

i'm looking forward to raise my glass to your health, when you will publish your code.
Incredible improvement compared to McGuire's work.

[Serg]

Hi, blue!
I am far from this thread's discussion. It looks like you've found very efficient algorithm for finding all possible 17-clue puzzles, right? If it is so - what are practical perspectives of doing exhaustive search for 17-clue puzzles?

Serg

[champagne]

It does something like that (maybe?) with UA2's, that allows/"helps with the idea of" sharing the work across the various ways of filling band 3.
...
The code keeps 81 lists/queues that have information about the band 1&2 parts of the larger UA's (like that), that have been found in earlier testing. The number 81, comes from 9 ways to choose columns A and B, with A < B and A & B in the same stack, 3 ways to choose a digit from column A, and 3 ways to choose a digit from column B.

Hi Blue,

As you know, such UA's play a key role in my attempt to find something.

In the process, I replace the 2 cells by the complementary cell in the minirow. This gives a very efficient way to combine all such active UAs and to process them if necessary. I have nothing similar to your 81 lists/queues

I am still impressed by the very simple idea you had. ASAP, (end of this week), I'll try to use it in my code to see where I am at the end.

BTW, what would be the performance for a 16 search compared to the McGuire's code?

[blue]

You explained it better.

Nevertheless I will try to explain it in my words. Below is an example of my understanding.

I see. It's definitely related. Thank you.

Note that a UA with your AB columns is possible to expand to other columns in band 3 w/o interference with bands 1,2. This is seen when comparing band 3 between Case A and Case B in my example.

Nice observation ! That might be just what I'm looking for, at a certain point in the code.
I'll definitely look into it. Thanks again.

As you know, such UA's play a key role in my attempt to find something.

In the process, I replace the 2 cells by the complementary cell in the minirow. This gives a very efficient way to combine all such active UAs and to process them if necessary.

I do something like that too ... a 3-bit "mini-row type", with a bit for each valid UA2.

BTW, what would be the performance for a 16 search compared to the McGuire's code?

On my machine it takes ~7.8ms per grid, versus 2.8s for McGuire's code. It's ~350 times as fast.

Hi, blue!
I am far from this thread's discussion. It looks like you've found very efficient algorithm for finding all possible 17-clue puzzles, right? If it is so - what are practical perspectives of doing exhaustive search for 17-clue puzzles?

Yes, right. I'm not sure what you mean by "practical perspectives".
On my 4-core 'i7' (@3.4Ghz), the current code would take ~8 years to complete the search.
I'm a little worried that running on a 16+ core machine, would expose a bottleneck with RAM.
I don't have any experience in that area.
I'm hoping that dobrichev and champagne will be interested in running the full search, at some point.

[champagne]

Hi Blue,

BTW, what would be the performance for a 16 search compared to the McGuire's code?

On my machine it takes ~7.8ms per grid, versus 2.8s for McGuire's code. It's ~350 times as fast.

7.8ms per grid does not give that much time for UA collection, it will be very very interesting to analyse your code. With the UAs search done in my process, This would not be possible.

On my 4-core 'i7' (@3.4Ghz), the current code would take ~8 years to complete the search.
I'm a little worried that running on a 16+ core machine, would expose a bottleneck with RAM.
I don't have any experience in that area.
I'm hoping that dobrichev and champagne will be interested in running the full search, at some point.

[/quote][/quote]

Surely, my available limited power would be free for that, say 10/15 cores spread on 3 PCs, but I'll have no access to them before the first week of April, (just enough time to understand what you are doing and to prepare the appropriate executable (windows 10 on my side) )

I am sure that other players have free cycles and the task is easy to share.

[blue]

Hi champagne,

7.8ms per grid does not give that much time for UA collection, it will be very very interesting to analyse your code.

Are you remembering that it isn't really 7.8ms each, for 5.47 billion full grids ?
It's 43ms each, for 984 million inputs.

The search for UA's only looks for size 14 or less UA's in bands 1 & 2.
It takes ~2.7 ms, but it only finds 114 UA's, on average.

[champagne]

Hi again blue,

you are likely referring to that

The normal code, runs in two passes over 983,959,110 (ED) band 1&2 fills, and takes ~1.04s total, per "input".
Multiplying by (983,959,110 inputs)/(5,472,730,538 canonical grids), gives ~0.19s per grid.

I skipped the sentence in the first reading, So I assume now that you have a preprocessing of the catalog to extract the ED bands 1&2 and sort the catalog on that key, likely remorphing the solution. I failed earlier in an attempt to share the work between several solution grids.

Combining that ED bands 1&2 with the pass >=7 clues in band 3 and with the final 6+6+5 clues was another challenge.