The New Sudoku Players' Forum

[champagne]

The list of the 416 min lexical bands is well known.
Looking for the min lexical morph of a solution grid, but also in other cases, we must find the min lexical morph of a band.

Mapping to the minimal can be required, but not always, and sometimes, it is enough to know that the band rank is below a given number. This is what happens in the catalog handler.

For example, if we have a potential minimal solution grid with the first band of rank n, any stack having a rank < n is a basis for a lower solution grid. It’s only if we find a stack of rank n that more investigations starting with the mapping are needed.

In the virtual catalog explained in this thread here part of the catalog is still produced using the catalog builder. In this process, after all improvements already done, the search of the rank for a given band falls in the critical area of the code.

Here is an attempt to find a better (the best possible) code to reach the target.

The band to search can appear in any morph in the catalog builder.
As written above, the priority here is to get the rank or to see if the rank is below the rank of the first band of the builder.

I have my own draft of a code expected to perform well, but the game is open to find a better process.
I lock the first posts to describe my process.

My current code is not bad, as good as the new one without the shunt possible as soon as the expected id is below the given limit, at least in the following test:

Code: Select all

Try the 416 band in the same morphing using one of the stored auto morphs
Run 100 000 times the search.


Both processes have an average global run time slightly over 4.16 seconds on my desk, giving

0.1 microseconds to identify the band index and supply the mapping tables.


Both implementations are currently in the repository
https://github.com/GPenet/sk_minlexsol

[champagne]

Here is the known table of the min lexical bands shown in a way to focus on a quick identification of a given band

Code: Select all

416 bands index 0-415
9 mini rows
band index
number of  mini columns (patterns)
number of patterns appearing 3 times
number of patterns appearing 2 times

Hidden Text: Show

Code: Select all

123 456 789 _ 456 789 123 _ 789 123 456 _   0       3 3 0
123 456 789 _ 456 789 123 _ 789 123 465 _   1       5 1 2
123 456 789 _ 456 789 123 _ 789 123 564 _   2       6 0 3
123 456 789 _ 456 789 123 _ 789 132 465 _   3       7 1 0
123 456 789 _ 456 789 123 _ 789 132 546 _   4       7 0 2
123 456 789 _ 456 789 123 _ 789 132 564 _   5       8 0 1
123 456 789 _ 456 789 123 _ 789 231 564 _   6       9 0 0
123 456 789 _ 456 789 123 _ 789 231 645 _   7       9 0 0
123 456 789 _ 456 789 123 _ 798 132 465 _   8       7 1 0
123 456 789 _ 456 789 123 _ 798 132 546 _   9       8 0 1
123 456 789 _ 456 789 123 _ 798 132 564 _   10       8 0 1
123 456 789 _ 456 789 123 _ 798 213 564 _   11       9 0 0
123 456 789 _ 456 789 123 _ 798 213 654 _   12       9 0 0
123 456 789 _ 456 789 123 _ 798 231 564 _   13       9 0 0
123 456 789 _ 456 789 123 _ 798 231 645 _   14       9 0 0
123 456 789 _ 456 789 123 _ 897 231 564 _   15       9 0 0
123 456 789 _ 456 789 123 _ 897 231 645 _   16       9 0 0
123 456 789 _ 456 789 132 _ 789 123 546 _   17       6 0 3
123 456 789 _ 456 789 132 _ 789 132 546 _   18       7 0 2
123 456 789 _ 456 789 132 _ 789 132 564 _   19       8 0 1
123 456 789 _ 456 789 132 _ 789 213 456 _   20       7 0 2
123 456 789 _ 456 789 132 _ 789 213 645 _   21       8 0 1
123 456 789 _ 456 789 132 _ 789 213 654 _   22       8 0 1
123 456 789 _ 456 789 132 _ 789 231 546 _   23       9 0 0
123 456 789 _ 456 789 132 _ 789 231 564 _   24       9 0 0
123 456 789 _ 456 789 132 _ 879 231 564 _   25       9 0 0
123 456 789 _ 456 789 231 _ 789 123 645 _   26       6 0 3
123 456 789 _ 456 789 231 _ 789 132 546 _   27       8 0 1
123 456 789 _ 456 789 231 _ 789 231 564 _   28       9 0 0
123 456 789 _ 456 789 231 _ 789 312 456 _   29       9 0 0
123 456 789 _ 456 789 231 _ 798 213 645 _   30       9 0 0


123 456 789 _ 457 189 236 _ 689 237 145 _   31       9 0 0
123 456 789 _ 457 189 236 _ 689 237 154 _   32       8 0 1
123 456 789 _ 457 189 236 _ 689 237 415 _   33       9 0 0
123 456 789 _ 457 189 236 _ 689 237 451 _   34       8 0 1
123 456 789 _ 457 189 236 _ 689 237 514 _   35       9 0 0
123 456 789 _ 457 189 236 _ 689 237 541 _   36       9 0 0
123 456 789 _ 457 189 236 _ 689 273 145 _   37       9 0 0
123 456 789 _ 457 189 236 _ 689 273 154 _   38       9 0 0
123 456 789 _ 457 189 236 _ 689 273 415 _   39       9 0 0
123 456 789 _ 457 189 236 _ 689 273 451 _   40       9 0 0
123 456 789 _ 457 189 236 _ 689 273 514 _   41       9 0 0
123 456 789 _ 457 189 236 _ 689 273 541 _   42       9 0 0
123 456 789 _ 457 189 236 _ 689 327 145 _   43       8 0 1
123 456 789 _ 457 189 236 _ 689 327 154 _   44       8 0 1
123 456 789 _ 457 189 236 _ 689 327 415 _   45       8 0 1
123 456 789 _ 457 189 236 _ 689 327 451 _   46       8 0 1
123 456 789 _ 457 189 236 _ 689 327 514 _   47       8 0 1
123 456 789 _ 457 189 236 _ 689 327 541 _   48       8 0 1
123 456 789 _ 457 189 236 _ 689 372 145 _   49       9 0 0
123 456 789 _ 457 189 236 _ 689 372 154 _   50       9 0 0
123 456 789 _ 457 189 236 _ 689 372 415 _   51       9 0 0
123 456 789 _ 457 189 236 _ 689 372 451 _   52       9 0 0
123 456 789 _ 457 189 236 _ 689 372 514 _   53       9 0 0
123 456 789 _ 457 189 236 _ 689 372 541 _   54       9 0 0
123 456 789 _ 457 189 236 _ 689 723 145 _   55       8 0 1
123 456 789 _ 457 189 236 _ 689 723 154 _   56       8 0 1
123 456 789 _ 457 189 236 _ 689 723 415 _   57       8 0 1
123 456 789 _ 457 189 236 _ 689 723 514 _   58       8 0 1
123 456 789 _ 457 189 236 _ 689 723 541 _   59       8 0 1
123 456 789 _ 457 189 236 _ 689 732 145 _   60       9 0 0
123 456 789 _ 457 189 236 _ 689 732 154 _   61       8 0 1
123 456 789 _ 457 189 236 _ 689 732 415 _   62       9 0 0
123 456 789 _ 457 189 236 _ 689 732 514 _   63       9 0 0
123 456 789 _ 457 189 236 _ 689 732 541 _   64       9 0 0
123 456 789 _ 457 189 236 _ 698 237 145 _   65       9 0 0
123 456 789 _ 457 189 236 _ 698 237 154 _   66       8 0 1
123 456 789 _ 457 189 236 _ 698 237 415 _   67       9 0 0
123 456 789 _ 457 189 236 _ 698 237 514 _   68       9 0 0
123 456 789 _ 457 189 236 _ 698 237 541 _   69       9 0 0
123 456 789 _ 457 189 236 _ 698 273 145 _   70       9 0 0
123 456 789 _ 457 189 236 _ 698 273 154 _   71       9 0 0
123 456 789 _ 457 189 236 _ 698 273 415 _   72       9 0 0
123 456 789 _ 457 189 236 _ 698 273 514 _   73       9 0 0
123 456 789 _ 457 189 236 _ 698 273 541 _   74       9 0 0
123 456 789 _ 457 189 236 _ 698 327 145 _   75       9 0 0
123 456 789 _ 457 189 236 _ 698 327 154 _   76       9 0 0
123 456 789 _ 457 189 236 _ 698 327 415 _   77       9 0 0
123 456 789 _ 457 189 236 _ 698 327 541 _   78       9 0 0
123 456 789 _ 457 189 236 _ 698 372 145 _   79       9 0 0
123 456 789 _ 457 189 236 _ 698 372 154 _   80       9 0 0
123 456 789 _ 457 189 236 _ 698 372 415 _   81       9 0 0
123 456 789 _ 457 189 236 _ 698 372 514 _   82       9 0 0
123 456 789 _ 457 189 236 _ 698 372 541 _   83       9 0 0
123 456 789 _ 457 189 236 _ 698 723 145 _   84       9 0 0
123 456 789 _ 457 189 236 _ 698 723 154 _   85       9 0 0
123 456 789 _ 457 189 236 _ 698 723 415 _   86       9 0 0
123 456 789 _ 457 189 236 _ 698 723 514 _   87       9 0 0
123 456 789 _ 457 189 236 _ 698 732 145 _   88       9 0 0
123 456 789 _ 457 189 236 _ 698 732 154 _   89       8 0 1
123 456 789 _ 457 189 236 _ 698 732 415 _   90       9 0 0
123 456 789 _ 457 189 236 _ 698 732 514 _   91       9 0 0
123 456 789 _ 457 189 236 _ 869 237 145 _   92       9 0 0
123 456 789 _ 457 189 236 _ 869 237 514 _   93       9 0 0
123 456 789 _ 457 189 236 _ 869 273 145 _   94       9 0 0
123 456 789 _ 457 189 236 _ 869 273 154 _   95       9 0 0
123 456 789 _ 457 189 236 _ 869 273 415 _   96       9 0 0
123 456 789 _ 457 189 236 _ 869 273 514 _   97       9 0 0
123 456 789 _ 457 189 236 _ 869 327 154 _   98       9 0 0
123 456 789 _ 457 189 236 _ 869 327 415 _   99       9 0 0
123 456 789 _ 457 189 236 _ 869 327 514 _   100       9 0 0
123 456 789 _ 457 189 236 _ 869 372 145 _   101       9 0 0
123 456 789 _ 457 189 236 _ 869 372 154 _   102       9 0 0
123 456 789 _ 457 189 236 _ 869 372 415 _   103       9 0 0
123 456 789 _ 457 189 236 _ 869 372 514 _   104       9 0 0
123 456 789 _ 457 189 236 _ 869 723 145 _   105       9 0 0
123 456 789 _ 457 189 236 _ 869 723 154 _   106       9 0 0
123 456 789 _ 457 189 236 _ 869 723 514 _   107       9 0 0
123 456 789 _ 457 189 236 _ 869 732 145 _   108       9 0 0
123 456 789 _ 457 189 236 _ 869 732 154 _   109       8 0 1
123 456 789 _ 457 189 236 _ 896 237 145 _   110       9 0 0
123 456 789 _ 457 189 236 _ 896 237 154 _   111       8 0 1
123 456 789 _ 457 189 236 _ 896 237 514 _   112       9 0 0
123 456 789 _ 457 189 236 _ 896 273 145 _   113       9 0 0
123 456 789 _ 457 189 236 _ 896 273 154 _   114       9 0 0
123 456 789 _ 457 189 236 _ 896 273 514 _   115       9 0 0
123 456 789 _ 457 189 236 _ 896 327 145 _   116       9 0 0
123 456 789 _ 457 189 236 _ 896 327 154 _   117       9 0 0
123 456 789 _ 457 189 236 _ 896 327 514 _   118       9 0 0
123 456 789 _ 457 189 236 _ 896 372 145 _   119       9 0 0
123 456 789 _ 457 189 236 _ 896 372 154 _   120       9 0 0
123 456 789 _ 457 189 236 _ 896 372 514 _   121       9 0 0
123 456 789 _ 457 189 236 _ 896 723 154 _   122       9 0 0
123 456 789 _ 457 189 236 _ 896 723 514 _   123       9 0 0
123 456 789 _ 457 189 236 _ 896 732 154 _   124       8 0 1
123 456 789 _ 457 189 236 _ 896 732 514 _   125       9 0 0
123 456 789 _ 457 189 236 _ 968 237 154 _   126       8 0 1
123 456 789 _ 457 189 236 _ 968 237 514 _   127       9 0 0
123 456 789 _ 457 189 236 _ 968 273 514 _   128       9 0 0
123 456 789 _ 457 189 236 _ 968 327 154 _   129       9 0 0
123 456 789 _ 457 189 236 _ 968 327 514 _   130       9 0 0
123 456 789 _ 457 189 236 _ 968 372 154 _   131       9 0 0
123 456 789 _ 457 189 236 _ 968 372 514 _   132       9 0 0
123 456 789 _ 457 189 236 _ 968 723 154 _   133       9 0 0
123 456 789 _ 457 189 236 _ 968 732 154 _   134       8 0 1
123 456 789 _ 457 189 236 _ 986 237 154 _   135       8 0 1
123 456 789 _ 457 189 236 _ 986 273 154 _   136       9 0 0
123 456 789 _ 457 189 236 _ 986 327 154 _   137       8 0 1
123 456 789 _ 457 189 236 _ 986 372 154 _   138       9 0 0
123 456 789 _ 457 189 263 _ 689 237 145 _   139       9 0 0
123 456 789 _ 457 189 263 _ 689 237 415 _   140       9 0 0
123 456 789 _ 457 189 263 _ 689 237 451 _   141       9 0 0
123 456 789 _ 457 189 263 _ 689 237 514 _   142       9 0 0
123 456 789 _ 457 189 263 _ 689 273 154 _   143       9 0 0
123 456 789 _ 457 189 263 _ 689 273 415 _   144       9 0 0
123 456 789 _ 457 189 263 _ 689 273 451 _   145       9 0 0
123 456 789 _ 457 189 263 _ 689 273 514 _   146       9 0 0
123 456 789 _ 457 189 263 _ 689 273 541 _   147       9 0 0
123 456 789 _ 457 189 263 _ 689 327 154 _   148       8 0 1
123 456 789 _ 457 189 263 _ 689 327 415 _   149       8 0 1
123 456 789 _ 457 189 263 _ 689 327 514 _   150       8 0 1
123 456 789 _ 457 189 263 _ 689 327 541 _   151       8 0 1
123 456 789 _ 457 189 263 _ 689 372 145 _   152       9 0 0
123 456 789 _ 457 189 263 _ 689 372 154 _   153       9 0 0
123 456 789 _ 457 189 263 _ 689 372 415 _   154       9 0 0
123 456 789 _ 457 189 263 _ 689 372 451 _   155       9 0 0
123 456 789 _ 457 189 263 _ 689 372 514 _   156       9 0 0
123 456 789 _ 457 189 263 _ 689 723 145 _   157       8 0 1
123 456 789 _ 457 189 263 _ 689 723 154 _   158       8 0 1
123 456 789 _ 457 189 263 _ 689 723 451 _   159       8 0 1
123 456 789 _ 457 189 263 _ 689 732 145 _   160       9 0 0
123 456 789 _ 457 189 263 _ 689 732 154 _   161       9 0 0
123 456 789 _ 457 189 263 _ 689 732 415 _   162       9 0 0
123 456 789 _ 457 189 263 _ 689 732 451 _   163       9 0 0
123 456 789 _ 457 189 263 _ 689 732 514 _   164       9 0 0
123 456 789 _ 457 189 263 _ 689 732 541 _   165       9 0 0
123 456 789 _ 457 189 263 _ 698 237 154 _   166       9 0 0
123 456 789 _ 457 189 263 _ 698 237 415 _   167       9 0 0
123 456 789 _ 457 189 263 _ 698 237 451 _   168       9 0 0
123 456 789 _ 457 189 263 _ 698 237 514 _   169       9 0 0
123 456 789 _ 457 189 263 _ 698 273 145 _   170       9 0 0
123 456 789 _ 457 189 263 _ 698 273 415 _   171       9 0 0
123 456 789 _ 457 189 263 _ 698 273 451 _   172       9 0 0
123 456 789 _ 457 189 263 _ 698 273 514 _   173       9 0 0
123 456 789 _ 457 189 263 _ 698 327 145 _   174       9 0 0
123 456 789 _ 457 189 263 _ 698 327 154 _   175       9 0 0
123 456 789 _ 457 189 263 _ 698 327 415 _   176       9 0 0
123 456 789 _ 457 189 263 _ 698 327 451 _   177       9 0 0
123 456 789 _ 457 189 263 _ 698 327 514 _   178       9 0 0
123 456 789 _ 457 189 263 _ 698 372 154 _   179       9 0 0
123 456 789 _ 457 189 263 _ 698 372 415 _   180       9 0 0
123 456 789 _ 457 189 263 _ 698 372 514 _   181       9 0 0
123 456 789 _ 457 189 263 _ 698 372 541 _   182       9 0 0
123 456 789 _ 457 189 263 _ 698 732 145 _   183       9 0 0
123 456 789 _ 457 189 263 _ 698 732 154 _   184       9 0 0
123 456 789 _ 457 189 263 _ 698 732 451 _   185       9 0 0
123 456 789 _ 457 189 263 _ 869 237 154 _   186       9 0 0
123 456 789 _ 457 189 263 _ 869 237 415 _   187       9 0 0
123 456 789 _ 457 189 263 _ 869 237 514 _   188       9 0 0
123 456 789 _ 457 189 263 _ 869 273 451 _   189       9 0 0
123 456 789 _ 457 189 263 _ 869 327 415 _   190       9 0 0
123 456 789 _ 457 189 263 _ 869 327 451 _   191       9 0 0
123 456 789 _ 457 189 263 _ 869 327 514 _   192       9 0 0
123 456 789 _ 457 189 263 _ 869 372 145 _   193       9 0 0
123 456 789 _ 457 189 263 _ 869 372 154 _   194       9 0 0
123 456 789 _ 457 189 263 _ 869 372 514 _   195       9 0 0
123 456 789 _ 457 189 263 _ 896 237 145 _   196       9 0 0
123 456 789 _ 457 189 263 _ 896 237 154 _   197       9 0 0
123 456 789 _ 457 189 263 _ 896 237 451 _   198       9 0 0
123 456 789 _ 457 189 263 _ 896 327 145 _   199       9 0 0
123 456 789 _ 457 189 263 _ 896 327 154 _   200       9 0 0
123 456 789 _ 457 189 263 _ 896 327 415 _   201       9 0 0
123 456 789 _ 457 189 263 _ 896 327 451 _   202       9 0 0
123 456 789 _ 457 189 263 _ 896 327 514 _   203       9 0 0
123 456 789 _ 457 189 263 _ 896 327 541 _   204       9 0 0
123 456 789 _ 457 189 263 _ 896 372 145 _   205       9 0 0
123 456 789 _ 457 189 263 _ 896 372 154 _   206       9 0 0
123 456 789 _ 457 189 263 _ 896 372 451 _   207       9 0 0
123 456 789 _ 457 189 263 _ 968 327 145 _   208       9 0 0
123 456 789 _ 457 189 263 _ 968 327 154 _   209       9 0 0
123 456 789 _ 457 189 263 _ 968 327 415 _   210       9 0 0
123 456 789 _ 457 189 263 _ 968 327 514 _   211       9 0 0
123 456 789 _ 457 189 263 _ 968 327 541 _   212       9 0 0
123 456 789 _ 457 189 263 _ 968 372 145 _   213       9 0 0
123 456 789 _ 457 189 263 _ 986 327 145 _   214       8 0 1
123 456 789 _ 457 189 263 _ 986 327 154 _   215       8 0 1
123 456 789 _ 457 189 263 _ 986 327 451 _   216       8 0 1
123 456 789 _ 457 189 326 _ 689 237 451 _   217       8 0 1
123 456 789 _ 457 189 326 _ 689 237 514 _   218       9 0 0
123 456 789 _ 457 189 326 _ 689 237 541 _   219       9 0 0
123 456 789 _ 457 189 326 _ 689 273 145 _   220       9 0 0
123 456 789 _ 457 189 326 _ 689 273 451 _   221       8 0 1
123 456 789 _ 457 189 326 _ 689 273 541 _   222       9 0 0
123 456 789 _ 457 189 326 _ 689 327 154 _   223       7 1 0
123 456 789 _ 457 189 326 _ 689 327 451 _   224       7 1 0
123 456 789 _ 457 189 326 _ 689 327 541 _   225       8 0 1
123 456 789 _ 457 189 326 _ 689 372 415 _   226       9 0 0
123 456 789 _ 457 189 326 _ 689 372 541 _   227       9 0 0
123 456 789 _ 457 189 326 _ 689 723 145 _   228       8 0 1
123 456 789 _ 457 189 326 _ 689 723 415 _   229       8 0 1
123 456 789 _ 457 189 326 _ 689 732 145 _   230       9 0 0
123 456 789 _ 457 189 326 _ 689 732 415 _   231       9 0 0
123 456 789 _ 457 189 326 _ 689 732 514 _   232       9 0 0
123 456 789 _ 457 189 326 _ 689 732 541 _   233       9 0 0
123 456 789 _ 457 189 326 _ 698 237 145 _   234       9 0 0
123 456 789 _ 457 189 326 _ 698 237 541 _   235       9 0 0
123 456 789 _ 457 189 326 _ 698 273 514 _   236       9 0 0
123 456 789 _ 457 189 326 _ 698 273 541 _   237       9 0 0
123 456 789 _ 457 189 326 _ 698 732 415 _   238       9 0 0
123 456 789 _ 457 189 326 _ 869 372 514 _   239       9 0 0
123 456 789 _ 457 189 623 _ 689 237 145 _   240       9 0 0
123 456 789 _ 457 189 623 _ 689 237 154 _   241       8 0 1
123 456 789 _ 457 189 623 _ 689 273 145 _   242       9 0 0
123 456 789 _ 457 189 623 _ 689 273 154 _   243       8 0 1
123 456 789 _ 457 189 623 _ 689 273 541 _   244       9 0 0
123 456 789 _ 457 189 623 _ 689 327 145 _   245       8 0 1
123 456 789 _ 457 189 623 _ 689 327 154 _   246       7 1 0
123 456 789 _ 457 189 623 _ 689 372 145 _   247       9 0 0
123 456 789 _ 457 189 623 _ 689 372 154 _   248       8 0 1
123 456 789 _ 457 189 623 _ 689 372 514 _   249       9 0 0
123 456 789 _ 457 189 623 _ 689 723 145 _   250       8 0 1
123 456 789 _ 457 189 623 _ 689 723 154 _   251       7 1 0
123 456 789 _ 457 189 623 _ 689 723 415 _   252       8 0 1
123 456 789 _ 457 189 623 _ 689 723 451 _   253       7 1 0
123 456 789 _ 457 189 623 _ 689 723 514 _   254       8 0 1
123 456 789 _ 457 189 623 _ 689 723 541 _   255       8 0 1
123 456 789 _ 457 189 623 _ 689 732 145 _   256       9 0 0
123 456 789 _ 457 189 623 _ 689 732 154 _   257       8 0 1
123 456 789 _ 457 189 623 _ 689 732 415 _   258       9 0 0
123 456 789 _ 457 189 623 _ 689 732 451 _   259       8 0 1
123 456 789 _ 457 189 623 _ 689 732 514 _   260       9 0 0
123 456 789 _ 457 189 623 _ 689 732 541 _   261       9 0 0
123 456 789 _ 457 189 623 _ 698 237 145 _   262       9 0 0
123 456 789 _ 457 189 623 _ 698 237 154 _   263       9 0 0
123 456 789 _ 457 189 623 _ 698 237 541 _   264       9 0 0
123 456 789 _ 457 189 623 _ 698 273 145 _   265       9 0 0
123 456 789 _ 457 189 623 _ 698 273 154 _   266       9 0 0
123 456 789 _ 457 189 623 _ 698 327 145 _   267       9 0 0
123 456 789 _ 457 189 623 _ 698 327 154 _   268       8 0 1
123 456 789 _ 457 189 623 _ 698 327 514 _   269       9 0 0
123 456 789 _ 457 189 623 _ 698 372 145 _   270       9 0 0
123 456 789 _ 457 189 623 _ 698 372 154 _   271       9 0 0
123 456 789 _ 457 189 623 _ 698 732 145 _   272       9 0 0
123 456 789 _ 457 189 623 _ 698 732 154 _   273       9 0 0
123 456 789 _ 457 189 623 _ 698 732 415 _   274       9 0 0
123 456 789 _ 457 189 623 _ 698 732 514 _   275       9 0 0
123 456 789 _ 457 189 623 _ 698 732 541 _   276       9 0 0
123 456 789 _ 457 189 623 _ 869 237 145 _   277       9 0 0
123 456 789 _ 457 189 623 _ 869 273 145 _   278       9 0 0
123 456 789 _ 457 189 623 _ 869 273 154 _   279       9 0 0
123 456 789 _ 457 189 623 _ 869 273 451 _   280       9 0 0
123 456 789 _ 457 189 623 _ 869 327 154 _   281       8 0 1
123 456 789 _ 457 189 623 _ 869 372 145 _   282       9 0 0
123 456 789 _ 457 189 623 _ 869 372 154 _   283       9 0 0
123 456 789 _ 457 189 623 _ 896 237 145 _   284       9 0 0
123 456 789 _ 457 189 623 _ 896 237 154 _   285       9 0 0
123 456 789 _ 457 189 623 _ 896 237 415 _   286       9 0 0
123 456 789 _ 457 189 623 _ 896 237 451 _   287       9 0 0
123 456 789 _ 457 189 623 _ 896 237 514 _   288       9 0 0
123 456 789 _ 457 189 623 _ 896 237 541 _   289       9 0 0
123 456 789 _ 457 189 623 _ 896 327 145 _   290       9 0 0
123 456 789 _ 457 189 623 _ 896 327 154 _   291       8 0 1
123 456 789 _ 457 189 623 _ 896 327 415 _   292       9 0 0
123 456 789 _ 457 189 623 _ 896 327 451 _   293       8 0 1
123 456 789 _ 457 189 623 _ 896 327 514 _   294       9 0 0
123 456 789 _ 457 189 623 _ 896 372 145 _   295       9 0 0
123 456 789 _ 457 189 623 _ 896 372 154 _   296       9 0 0
123 456 789 _ 457 189 623 _ 896 372 451 _   297       9 0 0
123 456 789 _ 457 189 623 _ 968 327 145 _   298       9 0 0
123 456 789 _ 457 189 623 _ 968 327 154 _   299       8 0 1
123 456 789 _ 457 189 623 _ 968 327 415 _   300       9 0 0
123 456 789 _ 457 189 623 _ 968 372 145 _   301       9 0 0
123 456 789 _ 457 189 623 _ 968 372 154 _   302       9 0 0
123 456 789 _ 457 189 623 _ 986 327 145 _   303       8 0 1
123 456 789 _ 457 189 623 _ 986 327 154 _   304       7 1 0
123 456 789 _ 457 189 623 _ 986 327 415 _   305       8 0 1
123 456 789 _ 457 189 623 _ 986 327 451 _   306       7 1 0
123 456 789 _ 457 189 623 _ 986 327 514 _   307       8 0 1
123 456 789 _ 457 189 623 _ 986 327 541 _   308       8 0 1
123 456 789 _ 457 189 632 _ 689 237 145 _   309       9 0 0
123 456 789 _ 457 189 632 _ 689 273 145 _   310       9 0 0
123 456 789 _ 457 189 632 _ 689 273 154 _   311       9 0 0
123 456 789 _ 457 189 632 _ 689 273 514 _   312       9 0 0
123 456 789 _ 457 189 632 _ 689 327 154 _   313       8 0 1
123 456 789 _ 457 189 632 _ 689 372 145 _   314       9 0 0
123 456 789 _ 457 189 632 _ 689 372 154 _   315       9 0 0
123 456 789 _ 457 189 632 _ 689 723 145 _   316       8 0 1
123 456 789 _ 457 189 632 _ 689 723 514 _   317       8 0 1
123 456 789 _ 457 189 632 _ 689 732 145 _   318       9 0 0
123 456 789 _ 457 189 632 _ 689 732 154 _   319       8 0 1
123 456 789 _ 457 189 632 _ 689 732 514 _   320       9 0 0
123 456 789 _ 457 189 632 _ 689 732 541 _   321       9 0 0
123 456 789 _ 457 189 632 _ 698 237 145 _   322       8 0 1
123 456 789 _ 457 189 632 _ 698 237 154 _   323       8 0 1
123 456 789 _ 457 189 632 _ 698 237 514 _   324       9 0 0
123 456 789 _ 457 189 632 _ 698 273 145 _   325       8 0 1
123 456 789 _ 457 189 632 _ 698 327 145 _   326       8 0 1
123 456 789 _ 457 189 632 _ 698 327 154 _   327       9 0 0
123 456 789 _ 457 189 632 _ 698 327 541 _   328       9 0 0
123 456 789 _ 457 189 632 _ 698 372 154 _   329       9 0 0
123 456 789 _ 457 189 632 _ 698 732 145 _   330       8 0 1
123 456 789 _ 457 189 632 _ 698 732 514 _   331       9 0 0
123 456 789 _ 457 189 632 _ 869 273 145 _   332       9 0 0
123 456 789 _ 457 189 632 _ 869 372 145 _   333       9 0 0
123 456 789 _ 457 189 632 _ 896 237 145 _   334       8 0 1
123 456 789 _ 457 189 632 _ 896 237 415 _   335       8 0 1
123 456 789 _ 457 189 632 _ 896 327 145 _   336       8 0 1
123 456 789 _ 457 189 632 _ 896 327 154 _   337       9 0 0
123 456 789 _ 457 189 632 _ 896 327 451 _   338       9 0 0
123 456 789 _ 457 189 632 _ 896 327 541 _   339       9 0 0
123 456 789 _ 457 189 632 _ 896 372 145 _   340       8 0 1
123 456 789 _ 457 189 632 _ 896 372 154 _   341       9 0 0
123 456 789 _ 457 189 632 _ 896 372 451 _   342       9 0 0
123 456 789 _ 457 189 632 _ 968 327 145 _   343       9 0 0
123 456 789 _ 457 189 632 _ 968 327 154 _   344       9 0 0
123 456 789 _ 457 189 632 _ 968 327 451 _   345       9 0 0
123 456 789 _ 457 189 632 _ 986 327 145 _   346       8 0 1

123 456 789 _ 457 289 163 _ 689 173 452 _   347       9 0 0
123 456 789 _ 457 289 163 _ 689 713 254 _   348       9 0 0
123 456 789 _ 457 289 163 _ 698 137 425 _   349       9 0 0
123 456 789 _ 457 289 163 _ 698 137 524 _   350       9 0 0
123 456 789 _ 457 289 163 _ 698 317 254 _   351       9 0 0
123 456 789 _ 457 289 163 _ 698 317 524 _   352       9 0 0
123 456 789 _ 457 289 163 _ 698 713 254 _   353       9 0 0
123 456 789 _ 457 289 163 _ 869 713 245 _   354       9 0 0
123 456 789 _ 457 289 163 _ 869 731 245 _   355       9 0 0
123 456 789 _ 457 289 163 _ 869 731 524 _   356       9 0 0
123 456 789 _ 457 289 163 _ 896 317 245 _   357       9 0 0
123 456 789 _ 457 289 163 _ 896 731 524 _   358       9 0 0
123 456 789 _ 457 289 613 _ 689 173 245 _   359       9 0 0
123 456 789 _ 457 289 613 _ 689 713 245 _   360       9 0 0
123 456 789 _ 457 289 613 _ 689 713 254 _   361       8 0 1
123 456 789 _ 457 289 613 _ 698 137 254 _   362       9 0 0
123 456 789 _ 457 289 613 _ 698 317 245 _   363       9 0 0
123 456 789 _ 457 289 613 _ 698 317 254 _   364       8 0 1
123 456 789 _ 457 289 613 _ 698 713 245 _   365       9 0 0
123 456 789 _ 457 289 613 _ 869 713 245 _   366       8 0 1
123 456 789 _ 457 289 613 _ 869 731 245 _   367       8 0 1
123 456 789 _ 457 289 613 _ 869 731 254 _   368       9 0 0
123 456 789 _ 457 289 613 _ 896 137 245 _   369       8 0 1
123 456 789 _ 457 289 613 _ 896 137 254 _   370       9 0 0
123 456 789 _ 457 289 613 _ 896 317 245 _   371       8 0 1
123 456 789 _ 457 289 613 _ 896 317 425 _   372       9 0 0
123 456 789 _ 457 289 613 _ 896 731 245 _   373       8 0 1
123 456 789 _ 457 289 613 _ 896 731 254 _   374       9 0 0
123 456 789 _ 457 289 613 _ 968 137 245 _   375       9 0 0
123 456 789 _ 457 289 613 _ 968 137 254 _   376       9 0 0
123 456 789 _ 457 289 613 _ 968 731 245 _   377       9 0 0
123 456 789 _ 457 289 613 _ 986 137 245 _   378       9 0 0
123 456 789 _ 457 289 631 _ 689 173 245 _   379       9 0 0
123 456 789 _ 457 289 631 _ 689 713 254 _   380       9 0 0
123 456 789 _ 457 289 631 _ 698 317 254 _   381       9 0 0
123 456 789 _ 457 289 631 _ 869 713 245 _   382       9 0 0
123 456 789 _ 457 289 631 _ 869 713 254 _   383       9 0 0
123 456 789 _ 457 289 631 _ 869 731 245 _   384       9 0 0
123 456 789 _ 457 289 631 _ 869 731 254 _   385       8 0 1
123 456 789 _ 457 289 631 _ 896 137 245 _   386       9 0 0
123 456 789 _ 457 289 631 _ 896 137 254 _   387       8 0 1
123 456 789 _ 457 289 631 _ 896 137 425 _   388       9 0 0
123 456 789 _ 457 289 631 _ 896 317 245 _   389       9 0 0
123 456 789 _ 457 289 631 _ 896 317 254 _   390       9 0 0
123 456 789 _ 457 289 631 _ 896 731 245 _   391       9 0 0
123 456 789 _ 457 289 631 _ 968 137 254 _   392       7 0 2
123 456 789 _ 457 289 631 _ 968 731 245 _   393       9 0 0
123 456 789 _ 457 289 631 _ 968 731 254 _   394       7 0 2
123 456 789 _ 457 289 631 _ 986 137 245 _   395       9 0 0
123 456 789 _ 457 289 631 _ 986 137 254 _   396       7 0 2

123 456 789 _ 457 389 612 _ 896 127 345 _   397       6 0 3
123 456 789 _ 457 389 612 _ 896 127 354 _   398       8 0 1
123 456 789 _ 457 389 612 _ 896 172 345 _   399       6 0 3
123 456 789 _ 457 389 612 _ 896 172 354 _   400       8 0 1
123 456 789 _ 457 389 612 _ 896 217 345 _   401       6 0 3
123 456 789 _ 457 389 612 _ 896 217 354 _   402       7 0 2
123 456 789 _ 457 389 612 _ 896 271 345 _   403       6 0 3
123 456 789 _ 457 389 612 _ 896 271 354 _   404       8 0 1
123 456 789 _ 457 389 612 _ 896 712 354 _   405       7 0 2
123 456 789 _ 457 389 612 _ 896 721 354 _   406       8 0 1
123 456 789 _ 457 389 612 _ 986 172 354 _   407       8 0 1
123 456 789 _ 457 389 612 _ 986 217 354 _   408       7 0 2
123 456 789 _ 457 389 621 _ 896 127 345 _   409       8 0 1
123 456 789 _ 457 389 621 _ 896 217 354 _   410       8 0 1
123 456 789 _ 457 389 621 _ 986 127 354 _   411       5 1 2

123 456 789 _ 457 893 612 _ 896 127 345 _   412       3 3 0
123 456 789 _ 457 893 612 _ 896 127 354 _   413       5 1 2
123 456 789 _ 457 893 612 _ 896 217 354 _   414       7 1 0
123 456 789 _ 457 893 612 _ 986 217 354 _   415       7 1 0


The blank lines show the first big blocks

the first 31 bands having repetitive mini rows (without the order), with the same start for 15 cells,
the second block, with the start 123456789 457, where the fifth mini row is x89, except for the last four items

giving the four sub groups with the fifth mini row

189
289
389
893

[champagne]

Box and band view using digits, mini rows mini columns patterns.

This is an important topic for the code written in my 2 variants.

Let’s call digit pattern a 9 bits field where the bit “n” is set to 1 giving

Code: Select all

1 1.........
2 .1........
...

8 ........1.
9 .........1

A mini row as a mini column will be a bit field with three digits sets to 1 eg :

Code: Select all

147 1..4..7..

A box is entirely defined by the six bit fields 3 mini rows + 6 mini columns.

Each of the 3 mini rows and mini columns contain the 9 digits patterns
For each cell the digit pattern is defined using the right mini row and the right mini columns eg

Code: Select all

Box   mini rows   mini columns
123   111......   1..1..1..
456   ...111...   .1..1..1.
789   ......111   ..1..1..1

Code: Select all

Cell r2c2 mini row 2 mini column 2
...111... &
.1..1..1. =
....1.... pattern for digit 5

This view on a box is of high interest:

It can be extended to a band, a stack and the 9 boxes of a grid
Nearly all required operations are done with one native instruction in the x86 set of instructions.
Eg
compare 2 mini rows ignoring the order of the digits
find the common digits in 2 mini rows/mini columns
count such common digits
switch form the digit pattern to the digit 1-9 and reverse ...

Mini rows and mini columns are just exchanged in the valid permutations of a box (6x6 permutations).

In the former post is a table of the 416 min lexical bands 1. At the end is attached the count of different mini columns patterns and the count of mini columns seen three or two times, one example of a property easy to check.

Mini patterns and min lexical bands.

Just considering the mini rows patterns, many permutations can be discarded and some results can appear quickly.

The top part of the list of bands is made of three repetitive mini rows patterns “123” “456 “789”.

The rest has two common digits in the mini row 2 and the mini row 4, so having the first box and the rows defined, only one stack perm is possible for the 2 other stacks. The 2 common digits leave only one place for columns 3,6 and 7.


Selecting and optimizing the use of such properties is the way used here to find quickly the band index;

In a very small number of cases, relying on properties invariant in the permutations, we get immediately the band index:
. Band 1 (index 0) is the only one having 3 repetitive mini rows and 3 repetitive columns.
. band index 412 has also 3 repetitive mini columns, but no repetitive mini row
.....

But in most cases, these invariant properties will create subgroups of possible band indexes, so the analysis of permutations is unavoidable. Even if the index can be given, the mapping, if needed, will require the use of several permutations.

In the search of min lexical solution grids and in the virtual catalog, using partly this process, each band/stack must be studied, but the main point is to know if a given band/stack has an index lower equal or higher than the index of the first band.

. if the index if lower, the solution grid studied { partial (band2 or band 3) or filled (stacks) } is not lexically minimal
. if the index is higher, in most cases, nothing is expected
. if the index is equal, then the new band/stack is a potential start for a lower permutation and the mapping to the min lexical morph is needed


Relying on the list of min lexical solution grids, we have many ways to cut in the classical process requiring doing all permutations and comparing the entire solution grid. Most of them are not yet implemented in the old code and in the first draft of the second variant.

Here are some of the properties to use.

Minimum and maximum possible index of the band

This is easy to understand using mini rows and mini columns properties.

Repetitive mini row

If we find 2 repetitive mini rows, as already seen, the band has 3 repetitive mini rows and the final index is in the range 0-30. Any solution grid with a first band having an index >30 and another band or any stack with an index <=30 is not minimal.

Similar exclusions can come from the mini columns analysis.

Six mini columns

In the list given in the second post, we can extract these 4 min lexical bands 1.

Code: Select all

123 456 789 _ 457 389 612 _ 896 127 345 _   397       6 0 3
123 456 789 _ 457 389 612 _ 896 172 345 _   399       6 0 3
123 456 789 _ 457 389 612 _ 896 217 345 _   401       6 0 3
123 456 789 _ 457 389 612 _ 896 271 345 _   403       6 0 3


If we get a solution grid with no repetitive mini row and a count of 6 different mini columns, the minimal morph of this solution grid is one of the four.

So the solution grid will have an index in the range 397 – 403, ignored in most cases , cancelling the expansion if the band1 has an index > 403.

But we can make other remarks about this family:

No permutation can come with a start 123456789_ 457_ 1 or 2. Our list of min lexical bands is exhaustive.
The start 123456789_ 457_ 893 can not be excluded, but can be skipped, it would not be a minimal morph.


First hit

The first hit on a member of the list is the index searched. No permutation will produce a lower index.

Degressive value in r2c4 and maximum possible index.

We consider now the subgroup of solution grids having 8 different mini columns. Here below 3 solution grids taken in the list of the post 2, with different values in r2c4.

Code: Select all

123 456 789 _ 457 189 236 _ 689 237 154 _    32       8 0 1
123 456 789 _ 457 289 613 _ 869 713 245 _   366       8 0 1
123 456 789 _ 457 389 612 _ 896 172 354 _   400       8 0 1


For each value in r2 c4, we have a lower and a higher possible index

Code: Select all

1     32 346
2    361 387
3    398 410

As in the previous example, we can ignore permutations 1234567899_457_>3, They would not be minimal.
If we see a permutation with 2r2c4, we are sure to have a min lexical solution with 2 r2c4 or 1 r2c4. Having one permutation with 2r2c4, a permutation with 3 r2c cannot be minimal. This limits the highest index to 387, but the lowest can still be 32.

If we get a permutation with 1 r2c4, the min lexical must have 1 r2c4 and be one of the reduced list of known bands 1. Then the index will be in the range 32 346.

More reductions of the range

Just considering r2c4 and the mini columns count, we still have a wide range of possible indexes with 1r2c4;2r2c4 and 8/9 different mini columns.
All these minimal bands have 89 in r2c5,r2c6. A similar reduction of the range is possible using the next cells r2c7,r2c8 ...

[champagne]

Basically, as explained in the previous posts, what is expected is a process receiving

a valid band in any form
the index of the “reference band” (index of the first band in the virtual catalog)

and sending back first something as

-1 If the band index is lower than the index of the “reference band”
0 If the band index is equal to the index of the “reference band”
1 If the band index is higher than the index of the “reference band”

And, if the first answer is “equal”, the mapping from the given morph to the minimal.

If we agree that the answer “equal” has a probability close to 1/416, it is obvious that the critical code is not in the mapping needed.

As far as I could see, the critical code is in the first steps,

The very first step is to split the search into the 2 main branches, “456” or “457” as mini row 4, but also to count the different mini columns.

Branch “457”

The main branch is the case “457”. Only 31 of the 416 bands have the “456” mini row 4.

If we consider the 36 permutations: 6 rows permutations x 6 stack permutations
Only 18 of them have 2 common digits (needed) in the mini rows 2 and 4.
And the final status can be entirely defined except for the last four bands where the mini row 5 is “893”:

456 mini row 2 and 457 mini row 4 defines “6” “7” then the mini columns “3” “6” and “7”
Having 1;2 or 3 in r2c4, “4” and mini column “4” are defined.
With 45 in r2c12 and 89 in r2c56, all “digits” and “columns” can be solved.

At the end, a maximum of 18 permutations must be studied here.

Last four bands

If we don’t have 1,2,3 in r2c4 (the last four bands), the mini columns count gives a direct assignment for 2 bands. For the bands index 414 415, starting from one of the 18 row/stack valid permutations, we still have to define which column is the first. In the code, it is assumed that any of the 2 possible choices is correct.

Branch “456”

For the first 31 bands, we have a common start

123 456 789
456 789

Again, in a double loop rows/ stacks, this leaves us with 18 valid permutations out of the 36.
A match of the columns will be done but studying the 6 permutations of the columns in box 1 is unavoidable.
Here we have some direct assignments based on the repetitive mini columns (bands index 0,1). The double loop can be simplified to do the mapping. For band 1 for example, any of the 18x permutations would give the min lexical morph, so we have just to match the columns and relabel.

Note: the mapping after a direct assignment is not yet implemented.

End of a branch in the case 457

The double loop sends in a special branch the case of the last four bands (893 in the mini row 5),
Then, if no early go back appeared, we have one of the three possible values 1,2,3 in r2c4.

Based on the mini columns count, the relevant process is called. If we have nothing to call, this just means that the corresponding permutation is not minimal.

Something similar is done in the triple loop of the area 0-30.

Each of these processes has a potential sub list of min lexical bands to consider. The number of items in the sub list can be very small (less than 5) but most of the bands(more than 350) have r2c4= 1 or 2 and a mini count of 8 or 9 different mini columns.

In all cases, if we can map the entry to one item of the list, we have the hit, if not, this permutation is not minimal.

Finding the index exploring a list of items

The first 5 mini rows are known when we enter these functions. 4 mini rows are left, fully defined by 2 of the 3 digits in each mini row.

As example, the small list of possible bands with 7 different mini columns

Code: Select all

123 456 789 _ 457 289    631 _ 968 137 254 _   392       
123 456 789 _ 457 289    631 _ 968 731 254 _   394       
123 456 789 _ 457 289    631 _ 986 137 254 _   396
      
123 456 789 _ 457 389    612 _ 896 217 354 _   402       
123 456 789 _ 457 389    612 _ 896 712 354 _   405       
123 456 789 _ 457 389    612 _ 986 217 354 _   408     
                  x      xx    xx  xx  xx   

The “known part” is on the left. The rest can be reduced to the columns marked “x”. In fact, we have here 2 different values for r2c4, so this is equivalent to 2 different functions in the program.

In small tables like this one, several columns marked “x” have the same content. Testing these cells can give a quick “not minimal”, but for the big tables, this will not happen, and a morphing of the permutation is needed.

The final step is more or less a sequential lookup of the list of items. If the table is a big one, the four digits in mini rows 6,7 are used as primary index. In this case, the same function has been used for both branches, using these tables

Code: Select all

uint32_t tmin_c70v[6] = { 263961325,263967325,263981325,361892135,361897135,361982135 };
uint32_t tmin_c70i[6] = { 392,394,396,402,405,408 };

To do the lookup, the 9 digits of the permutation are first mapped to an uint32t. The mapping is done separately for mini rows 6,7 and 8,9 to let open the use of an index table

Using a primary index

If the list of items is a big one, It seems interesting to limit the number of items to scan using a primary index. This is done when the number of different mini columns is 8 or 9.
The items table is the same as before, one table is added giving for each value of the mini rows 6,7 the area of the main table to scan.

Code: Select all

uint32_t tmin_c8v[87] = {
123682315,123682345,...,123687214,123687215,//9
...
163983214,261687125.... 263867325,263891325,//79...
};

uint32_t tmin_c8i[87] = {
   32,34,43,44,45,46,47,48,55,56,//9 ......};

uint32_t tmin_c8_i4_toi6[31][2] = {{2368,0}, {2369,14...};

Each lookup gives an opportunity to get a lower maximum of the index, but this is not implemented.

[champagne]

Nearly 3 weeks later, nobody seems to be willing to challenge the proposed code.
Not exactly a surprise, so I continue slowly the implementation of a better solution.

The job is not over, but after a very bad third version, I implemented a fourth attempt to produce a better code open to a quick detection of a “non-equal” answer.
Bingo, despite many tests to get a quick go back, the code shows a 30% improvement compared to the first 2 versions.

The expected test in the “best conditions “ is with a first band index 0; Then, the answer is in average 12 times faster than in a classical call.

Is still missing the implementation of the final mapping when needed , and the use of this code in the virtual catalog.

I wrote in the first four posts comments to help anybody willing to dig in the process or in the code.
For several reasons, including my poor skills in the English language, the text should be improved. Remarks are welcome, public or in PM;

Next step is to revise the virtual catalog and to see what the “final” performance is.

[coloin]

My comments , hopefully describes part of your method and hopefully clarifies some of the terminology.

1
I can certainly follow that for Band 1
[ band 0-31] r2c123 = 456 [repeating minirow or braid pattern]
vv
[band 32-415] r2c123 = 457 [travelling pair or rope pattern]

I can also follow that a given band 1 will have row 4 fillings as per previous posts ....
If r2c123 in band 1 is 457 then r4 c456 cant have a repeating minirow is an observation.... and this prevents a repeating minirow in r4c789 and also in r5 and r6 .

2
When Box 1 is 457 in r2c123

Code: Select all

123
457
xyz

The options for column 1 r456 also cant be a vertical repeating minirow

Code: Select all

2
5
y   cannot be

and indeed c1 has only a few options as they have to be ascending and some combinations dont happen

3
When completing band 2 with r5 and r6...- horizontal band produced need to be a higher or ? equal compared to band 1

4
When completing band 2 with r5 and r6
If 457 in r2c123 then there should not be a vertical repeating minirow in c4r456 or c7r456. [eg c4r456 shound not be the same tuple as c5r123]

5
In band 3
Column 1 r789 minirow is pre-determined ... and you have found a way to even more quickly complete this band 3 filling with a lookup table using the gangster analogy .
If there is no vertical repeating minirow in c4r456 or c7r456 then there will be not be a repeating minirow in c4 r789 or c7 r789 that is probably trivial as point 4 covers this.
Making sure that the 3 vertical bands thus produced are furthur down the order than band 1 I guess has to be a requirement which you have found a solution for and is not trivial !
However if one of the bands is identical to band 1 then band 2 comes into play.

Hope this helps....I will test the code when its ready of course

I appreciate the need for optimization....
With Mladens help we have already been able to identify the band 1 and identify all the possible row 4 fillings
Computing the solution count and subsequent removing higher order solutions by minlexing will enable identification of the particular grid - but this is probably not efficient enough

[champagne]

Hi Coloin

Thanks for your comments, some of them could be more relevant in the “virtual catalog thread”.

Regarding the repetitive mini row in a band or repetitive mini column in a stack, the split
123 456 789 456 bands index 0-30
123 456 789 457 bands index 31-415
Is not just an observation, the proof is quite simple:

Code: Select all

As soon as you see a repetitive mini xx, you can morph the band/ stack to
abc def ghi
def
 then, in row 2, mini row 5 you must have ghi; nothing else is possible and the rest is forced to 3 repetitive mini rows / mini columns


Corollary: if you don’t have repetitive mini rows, abc as mini row in row 1 will be split as
ab + c in the one row (stacks 2/3)
c + ab in the other row

and the possibility to morph such a band to
123 456 789
456(x89) where x is 1,2 or 3
Is trivial.

Not so easy to prove, but easy to check in the list
123 456 789
457 89x
Then x=3 and we have a repetitive mini column 369


Now, small remarks on your post

If r2c123 in band 1 is 457 then r4 c456 cant have a repeating minirow is an observation.... and this prevents a repeating minirow in r4c789 and also in r5 and r6 .

Not only an observation as written above, but as follow, also true in stacks and this is not implemented.

When Box 1 is 457 in r2c123
The options for column 1 r456 also cant be a vertical repeating minirow

When completing band 2 with r5 and r6
If 457 in r2c123 then there should not be a vertical repeating minirow in c4r456 or c7r456. [eg c4r456 shound not be the same tuple as c5r123]

All this sounds good and some of these constraints should be implemented

Making sure that the 3 vertical bands thus produced are furthur down the order than band 1 I guess has to be a requirement which you have found a solution for and is not trivial !
However if one of the bands is identical to band 1 then band 2 comes into play.

Currently, when the solution grid if fully filled, each stack is analyzed to get it’s index and the mapping to the minimal.
If one index is below the band1 index, the solution grid is discarded.
If needed the diagonal solution grid is morphed to the band having the same index. The direct result plus all auto morphs is compared to the solution grid to discard it if we find a lower morph, and as you noticed, more has to be done if in bands and in stacks, several bands/stacks have the same lowest index.

Hope this helps....I will test the code when its ready of course

Surely it helps; here, The priority is to finish this, but your remarks on the mini columns constraints open the door for more "early go back".

Trying to apply what has been done in the “virtual catalog”, I noticed a fresh bug in the gangsters identification, likely introduced by a wrong action when I coded the band index search, but also a meaningless piece of code (assumed meaning less,.... to check)

I have to fix the bug and to check that this piece of code can be erased to get the full effect of the quick identification proposed here.

Computing the solution count and subsequent removing higher order solutions by minlexing will enable identification of the particular grid - but this is probably not efficient enough

What would be the average/maximum response expected for you??

The worst case will be with rows 4 having a big number of valid solution grids. This can be around 50K solution grids. I’ll run tests in the next days to have an idea of the worst response.

[coloin]

What would be the average/maximum response expected for you??

The worst case will be with rows 4 having a big number of valid solution grids. This can be around 50K solution grids. I’ll run tests in the next days to have an idea of the worst response.

I guess it depends on usage,
..
A - if it is to work out puzzle > solution > minlex solution > band1/row 4/xxxxx > grid number ..... then i guess 1 second is pretty good !!
B - If it is to analyse a file of puzzles then much faster would be needed ...

for A the hold up in my crude attempt was the generation of the solutions to the 4row ... although I did split it down into the possible minlex fillings of column 1 which wasnt in anyway automated
All other steps were fast

Your timings were several leagues better and if you are able to generate the row4 solutions without the need to minlex then timings will be improved furthur ...

It maybe the case that grids with band 1 larger than 299 could be treated differently [ as gsf did] as the band 300 plus row4 solution generation will generate higher proportions of smaller order solutions ...but maybe your process dismisses this potential problem !!!

[champagne]

Hi Coloin,

2 clues giving an idea of what can be expected here.

To make it simple, I make a guess that the final full generation of the catalog will take 10 core*hours on my old i7.
This is 36000 seconds for 652408 rows 4, about 55 milliseconds per row 4.

I also made a run of the current code for a chunk of 1000 rows 4 for band 2 (index 1), an area where bad results are expected.

I got 24 737 638 solution grids in 172 seconds, so, with an average 24700 solution grids per row 4 (the highest value is around 50000)
This is an average of 172 milliseconds per row 4.

From these results, the worst response for a single call should be around 400 ms, and the average around 80 ms if we carefully consider that most calls will take place in a bad area.

Note: the solution grid morphing to the min lexical, if needed, will not change significantly the response.

As we are not in a hurry, having seen a bug, I revise carefully the gangster mapping, so the next step in the implementation could take one more week.

[champagne]

After a long shutdown of my phone and net link, I am back with a slow progress in the DLL supply.

The final step here is to deliver a DLL for the virtual catalog, but I started with the Band analysis and Band Services.

The band DLL is stored in a new repository
https://github.com/GPenet/Virtual-calatog
open to receive at the end all DLL used in the Virtual catalog and the dll of the virtual catalog

The DLL skbminlex.dll contains the code to find the index 0-415 of a given band and the mapping from the given to the band.
The dll contains also all auto morphisms of a band (in min lexical morph),
and the dll contains the minimal exhaustive list of uas of the band.

here is the user file proposed to use it

Hidden Text: Show

Code: Select all

//skbminlex_user.h - band mapping and UAs list
#pragma once

#include "C:\_cinc\skb_permband.h"
/*
// ======  morphing a band
void SkbGetMappingChar(   const char * a, BANDPERM *  b);
 const char * a  the given band (char b[27])
 BANDPERM *  b pointer to the return values
   1+3+9+9 int values (see the BANDPERM struct)
_____________
void SkbGetMappingInt(   int* a, &BANDPERM * b);
 same as above, the given is int a[27] filled withe the appropriate integers 0 to 9

 //============ getting from the table auto morphs  of a band
int SkbGetAutoMorphs(int bandid, BANDPERM* tpermret);
 send back the pointer to the appropriate sub table of auto morphs
 return value is the number of automorphs
 return =0 with a pointer to the top part of the table if no response
 
int bandid index 0-415 of the band
 BANDPERM** tpermret where the pointer to the first automorph must be sent

// ======== Getting a band and  UAs of a band
extern "C" __declspec(dllexport) void SkbGetBandChar(int bandid, char* bchar27);
 extract in a char b [27] the band correspondding to the index 0-415 bandid
 return 12345678945 if id is not valid
______________________
extern "C" __declspec(dllexport) int SkbGetUas(int bandid, int** tuas_ret);
   send back the pointer to the appropriate sub table of uas
   return value is the number of uas of the band
    return =0 with a pointer to the top part of the table if no response

   int bandid index 0-415 of the band
    int ** tuas_ret where the pointer to the first ua must be sent
*/
// ======  morphing a band
extern "C" __declspec(dllimport) void SkbGetMappingChar(   const char * a, BANDPERM *  b);
extern "C" __declspec(dllimport) void SkbGetMappingInt(   int* a, BANDPERM * b);

// ======= getting auto morphs
extern "C" __declspec(dllimport) int SkbGetAutoMorphs(int bandid, BANDPERM** tpermret);

// ======== Getting a band and  UAs of a band
extern "C" __declspec(dllimport) void SkbGetBandChar(int bandid, char* bchar27);
extern "C" __declspec(dllimport) int SkbGetUas(int bandid, int** tuas_ret);



Note: using the known list of min lexical bands, the mapping is done in some microseconds

[champagne]

"blue" kindly warned me that errors occurred in tests done by him for the band index 0 and several bands index over 410.
I made the debugging using the variant used in the virtual catalog, and I think that I covered all seen bugs.

I have now to duplicate the changes in the DLL code and to rebuild it after more tests. This should be done by the end of this week.
In this update the BANDPERM file will also be modified
a bug in the debugging sequence CheckValid() has been fixed
a new function proposed by "nazaz" to speed up the process, not yet used on my side, has been added.

[champagne]

The new DLL is available in the repository.
Sources and the BANDPERM file have been updated as well.

1 million permutations for each band have been tested, so I hope to have now a code bug free...
The average response on my old I7 is below 5 micro seconds.
Next step will be the delivery of the variant used in the virtual catalog.

[champagne]

Thanks again to "blue", my fix for the band 0 was not correct.
Partly, the reason was that in BANDPERM the function Morph() did not take care of the rows mapping (not used in the virtual catalog)

And now, the DLL for the variant used in the virtuel catalog is ready and loaded in the repository.

Here is the user file available in the repository

Hidden Text: Show

Code: Select all

//skbvcminlex_user.h - band mapping for the virtual catalog
#pragma once

#include "skb_permband.h"

/*
// ======  morphing a band
int GcatGetBandIndex(int* b0, int band1_index);

This is the special morphing of a band used in the virtual catalog;

The band index is of interest only if it is the same as the current band 1 index.
If it is lower, the branch is dead, all fills to come would not be minimal
If it is higher, all fills to come must be checked, but the mapping is not needed.

The band 1 index is the parameter "band1_index"
The return code is -1;0;+1
-1 he band index is lower than "band1_index"
0 the band index is equal to "band1_inde". 
               The mapping is available in the BMINLEX structure
1 the band index is higher than "band1_index"

Note : a dummy "band1_inde" equal to the expected band index
   is used in tests to force the mapping

//===== getting the mapping and using it
If the mapping is done (band index equal to "band1_inde",
  it is available in a permanent BANPERM struct.
The BANDPERM pointer is given (usually called once) through

BANDPERM * GcatGetMappingPointer(); 

The user must use the file Banperm.h or any equvalent code to map the band is necessary.

*/

// ======  morphing a band
extern "C" __declspec(dllimport) int GcatGetBandIndex(int* b0, int band1_index);
// Get mapping pointer
extern "C" __declspec(dllimport) BANDPERM* GcatGetMappingPointer();


The variant do the mapping only when the band index is equal to the current first band of the virtual catalog.
Both DLL and .lib files and the relevant souce files have been loaded or updated

This closes what I had to do for one band.
Next to come in a separate thread is the quick "grid mapping" using the band "quick mapping". This function is necessary to enter the virtual catalog with a given grid not in min lexical morph; To keep the virtual catalog in the minimal size, this function could be kept outside the virtual catalog DLL. I'll see to add the count of automorphisms of the band in the grid min lexical mapping DLL