Search of 17 clues puzzles in a solution grid

I Creating an entry file for the search of 17 clues puzzles


To scan the solution grids searching 17 clues puzzles in this process, we need 3 different feed, 2 of them being variant of the catalogue of solution grids.


Each feed send to the main process an “Entry” made of an ED bands 1+2 plus the relevant band 3.


The code released here is the feed to search 17 clues puzzles having 6 clues in band3 with  5;6 clues in bands 1;2 or 6;5 clues in bands 1+2 . Band1 band2 and band 3 are ordered in such a way that the number of valid bands with 6 clues is increasing.


The main constant tables in the program used for that task are :


The list of the 416 bands in lexical minimal form  (out of the common 11 first cells “12345678945”)

A table giving the rank of a 416 band toward the criteria “number of valid bands with 6 clues”

And the reverse table, 0_415 id for a given band of rank n.


I1 Specifications of the file to create


The most common canonical form for the catalogue is the lexically minimal form. The corresponding catalogue has been produced years ago (as far as I know by Glenn Fowler posting as “gsf” in the forum)


To search the 17 clues puzzles having no band/stack with more than 6 clues, It appeared quickly that to have an acceptable run time


The band 3 must have 6 clues

The band 3 must be, among the 2 bands having 6 clues the band with the highest number of valid solutions.


And the catalogue must be sorted in such a way that all bands 3 having the same ED band 1+2 can be seen in sequence (or generated to be loaded in a table)


This is possible changing the canonical form of the catalogue, but requires 2 different generation process.


The first canonical form is the following :


Band 1 has the lowest number of valid solutions with 6 clues (lowest lexical form if 2 bands have equal number of solutions with 6 clues) and is morphed to be lexically minimal;


Band 2 has less or equal number of valid bands with 6 clues than band 3


Within these 2 conditions, the first column has the lexically minimal status.



I2 process applied


The process applied is not very different of the process used to produce a catalogue lexically minimal, although the canonical form is harder to check.


The program creates all possible grids using as first band one of the 416 possible starts.

Band 2 is rejected if the band order is higher than the band order for band 1 (band order is the rank of the band toward the number of valid bands with 6 clues)


All valid bands 3 are then analyzed toward the canonical criteria and the diagonal morph is checked as well. The band is not accepted if a “lower canonical” form appears.


I3 Checkpoint and parameters


As this is the outer loop of the 566 scan, a checkpoint is printed on a regular basis, to be used as restart point in case of failure.


As batches are supposed to last hours, and as we are not in risk if a 17 is produced twice, the checkpoint is designed to come every 64 bands 1+2.


To have a full control on the batch but also to have a debugging potential in that code, a limit is given for the last band to process in the batch


In the current code, a checkpoint is printed every 64 ED bands 1+2, but this could easily be set as command line parameter.


Both values (restart point and last bands to process) are given has multiples of 64, the checkpoint interval, defining a kind of “slice” of process;



The command line has 6 parameters plus the “cout” redirection. The command line is analyzed using my own standard  in the main routine, but this can be skipped analyzing  the code


skcat  -c10 -v0-0 -v1-9 -v2-0    -v3-100 -ofout.txt  > cout.txt


Where skcat is the .exe name


-c10 The process command calling the appropriate process (process number 10)

-v0-0 First band start value 0-415  here band 0

-v1-9 First band end here band 9

-v2-0 Value of the checkpoint to restart a batch here 0, no skip

-v3-100 Value of the checkpoint to restart a batch here 100 to process 100*64 entries in that batch.

-ofout.txt Output file for valid 17 here fout.txt

> cout.txt Cout redirection


Here we want to generate all “entries” from the band 1 of rank 0 to the band 1 of rank 9 in the limit of 64000 bands 1+2 with no restart point.

The valid 17 will be loaded in the file fout.txt

And the comments/notes will be printed (cout) in cout.txt


Note : Without the parameter -v3-100 this would give a batch of  24 357 534 entries with 435 188 953 bands3. Using the -v3– parameter, the batch can be cut in chunks. But in this case, the logic would be to have only one band defined in the parameters –v0- -v1-

Note 2: Here the parameter –v3- (last slice of bands 1+2) has no default value. This can be easily change


I4 content of the code files


The code used in this release has been cleaned (in principle) from all the stuff not directly linked to the overall project. In the code corresponding to the catalogue creation, the debugging code has been erased.


Are still there all files related to the brute force (zh...). These files are not called in the catalogue generation.


For historical reasons, most of the code used to produce the catalogue is located in the file tab1 where was the  table of the 416 bands in lexically  minimal  form.


The file tab1 contains also the code used to create the catalogue in the more common minimally lexical mode. So we have several very similar functions.


The class holding the data for the generation is in go_17_gen_b12 and the class holding a band are in go_17_band, but the code itself is in the main file for the 17 search go_17sol_bs


The tables creating the link between the 416 bands table in lexical mode and the desired order for this process are in the file go_17sol_tables where the main table, in use in the next step, is the list of UAs per band. In the same file are also located all tables used in the UAs collection.


The main routine and my standard handling of the  command line is in the file skcat.


All the code for the generation (main tree) is located in go_17sol_bs with as start function M10_S17.


I5 miscellaneous comments


The search of 17 for a 566 656 pass is called for each ED band 1+2 with the relevant table of bands 3 at the bottom of the routine M10Find_band3B()


The band 1 preprocessing is called during the entries generation





I suggest to skip these calls  waiting for the next topic, the preliminary tasks for a new entry.


Generally speaking, I use the old rowminlex code released years ago by Glenn Fowler to produce a lexically minimal solution grid. Here, it’s more a band oriented canonical form, and special functions have been developed in the tab1 file.


J Compilation and Compatibility constraints



My code is has been created using Microsoft Visual Studio  Express C++


The code is designed for a 64 bits processor and must be compiled in 64 bits mode.


If most of the code is standard C++, 2 specific features are in use


J1 Intrinsic functions


The program does not contain assembly pieces, but intensively uses functions translated in the compilation in basic instructions not belonging to the standard set of instructions of C++..


These are called “intrinsic functions” in the documentation.


The corresponding option must be set on for the compilation.


The main intrinsic functions used are


Popcount giving the number of bit on in the corresponding field

Bitscan forward/reverse giving the firs/last bit on in a field

All repetitive copy or initial settlements as__stosd  __stosq __movsd __movsq


J2 128 bits code


Inherited from mladen Dobrichev, I use some 128 bits registers (also used in the Gary McGuire proof that no 16 clues puzzle exist). The corresponding option must be on. In this part of the project, 128 bits registers are not used.


J3 Compatibility problems


From past experience, compiling the code on another platform can create problems. Some of them have been identified in the past by Mladen Dobrichev and the file tab0.h contains some old code added by him to create some compatibility.


Likely, more code should be added, but I have no way to test the code on other platforms, so this will be done upon request.


J4 multi threads issue


The code has not been written to be run in a multi-thread environment. I see no advantage to go in that direction instead of running several batches in parallel.


From past experience on Sudoku Fast Rating where the code has been adjusted to be run in multi-thread, it would be a total mess to try the experience here.