The New Sudoku Players' Forum

[champagne]

running the test on the virtual catalog using the gangster fills, I have seen a bug.

As I was not quite happy with the first draft, I reshaped the Gangster recognition and mapping in a way closer to what I did for the bands recognition.

The new code has been located in a separate file to prepare the final cleaning.
The new run of the entire catalog is on going with no bug at half way. So this version of the code is likely now bug free.

Next step will be, in the main thread of the virtual catalog, to apply the new band recognition to lower the response

rank <=> solution grid

[Sojourner9]

Hi champagne,

This is my understanding of what you are doing, correct me if I am wrong.
You are looking at the make up of a minLex grid, trying to come up with an index 0..<5472730538 to be used as an index into your catalog of 18 clue puzzles?
And a reverse lookup table as well, maybe.

Would any Int64 work, or do you need them to be in the above range?

I can reduce any grid to less than 64 bits using what I call minRep. So the act of finding the minimum representative grid also gives you the index.
Would the minRep be good enough for the catalog index?

I have Nmin enumerated as 5472730538 Int64 minReps currently separated into about 180 files and they are in ascending order.
I could probably make this into more files for finer resolution. If you had a computer with 44Gig of ram you could load it into memory.
There is a lot of redundancy in the integer, it might be able to be made into a linked list of some usable size again with enough memery.
I guess I did use the B1B2B3B4B7 method.
Since you don't need reordering in your catalog, any puzzle can be reduced to 1 64 bit integers for the grid and 3 32 bit Integers (3x27 bits) for the puzzle, which is 5 Int32s.
Or 1 Int64 for the solution grid and a list containing 3 Int32s for each 18 clue puzzles using that grid.

[champagne]

Hi Sojourner9,

Surely, I had in mind a way to store, later, a file of 18 clues puzzles, but immediately, the cooperation to the project of our lost friend “Mathimagics” came up with another use of the min lexical catalog.

To make it simple, “Mathimagcs” tried to define, for any solution grid, the minimum number of clues of a valid puzzle.
This requires in any form a 5472730538 list of “minimal values” and links to the corresponding solutions grids.
Up to now, this has been possible using a file of the catalog 5472730538 solution grids.

Mladen gave a design for a 10 bytes per solution grid file
http://forum.enjoysudoku.com/high-density-files-for-solution-grids-and-18-clues-puzzles-t42669.html
If I get it well, you have other options to propose.

I took a completely different option. We know that we have exactly 5472730538 solution grids; Would it be possible to have a link {solution grid <=> rank} using no file.

Using the min lexical morph of the solution grids was evidence, it is the commonly agreed representation of the catalog. Then the problem as I saw it could be phrased as

Have an efficient catalog builder producing it in min lexical order,
Try to turn it to a partially direct link using indexes and any seen possible improvement.
If you reach a response far below the second, then you have a virtual catalog.

The size of the “virtual catalog “ is then the size of the “DLL” giving the dual link. Say around 2MB, far below your 44 GB of Ram.

Where we are, we can produce the entire catalog in 11 hours with my old i7 (enumeration mode), with a direct response {solution grid <=> rank} in some milliseconds in the worst case.

I am finishing the implementation of a new” Band recognition and mapping” adjusted to this process requirements , and I have still in the “to do list” some ideas of “coloin”, so the final target for the entire catalog building could be significantly below 10 hours with a parallel reduction of the average response.

At the end, this gives no room for any other definition of the rank in my work than the min lexical order.

But the best way to store a 18 clues file remains open. Using the solution grid rank plus a 81 bit field is one option among others.

[champagne]

Next step to reach a virtual catalog delivered as DLL, the gangster analysis and use of the fills per gangster is now available in a DLL form.
The DLL skgminlex.dll and the sources are stored here

https://github.com/GPenet/Virtual-calatog

Next step will be

The special band analysis used in the virtual catalog as DLL
The quick Grid minlexing using the band analysis as basis again as a DLL,
then the virtual catalog DLL using all this stuff

The user file for this DLL is

Hidden Text: Show

Code: Select all

//skgminlex_user.h - gand mapping and gang fills
#pragma once


/*
//=============== find the ganster id
int SkgGetGang(int* g27);
the gangster is defined in a 27 table of values 0-8
In fact, it is 9 triplets, one for each column, each triplet sorted in increasing value of the three digits.
eg 123 456 789 if the first box for the gangster gangster is

147
258
369

the value returned is the index 0-43 of the gangster

//================ get the table of fills for a gangster
int SkgGetFills(int igang, const char** tfill);
Once the gangster id known (0-43)
Get access to the table of fills
const char** tfill) get the pointer to the first item of the gangster
the return vamue is the number of items

// ======  select  valid fills for a given band 1, morph and sort
int SkgBuildMorphedTableSortedOver(int ib1)

designed for the virtual catalog
where fills with a band index lower than the band 1 index can be ignored,
but giving a band index <=0 delivers the full table of fills, morphed and sorted.
This must follow a call to SkgGetGang (using the results of the mapping)
The table is stored in the DLL, the return value is the numver of fills valid.
Access to the table is through Skg_GetMorphedOrdered

As all parameters have been defined in the SkgGetGang call,
the only parameter of this call is the band 1 index (0-415)


 //============ getting one item of the valid fills.
 int* Skg_GetMorphedOrdered(int i,int * bandid)

 Acess to one valid fills has 2 results:
 the pointer to the int [27] band (digits 0-8)
 the band index

 i is the item index in the DLL table
 bandid is the pointer to the band id sent back
 and the return value is the pointer to the int [27]


*/
extern "C" __declspec(dllimport) int SkgGetGang(int* g27);
extern "C" __declspec(dllimport) int SkgGetFills(int igang, const char*** tfill);
extern "C" __declspec(dllimport) int SkgBuildMorphedTableSortedOver(int ib1);
extern "C" __declspec(dllimport) int* Skg_GetMorphedOrdered(int i, int* bandid);