The New Sudoku Players' Forum

[champagne]

Having now a first version of a brute force solver in DLL, I had all the tools to make a test on one possible format for a canonical puzzle.

As proposed in this thread,
http://forum.enjoysudoku.com/high-density-files-for-solution-grids-and-18-clues-puzzles-t42669-60.html

I think that a good competitor for this is a puzzle shown as

The rank 1- 5 472 730 538 of the solution grid
A binary field of 81 bit for the active cells of the puzzle.

I made a test on “loki”, the first puzzle known with a tridagon pattern

Code: Select all

57....9..........8.1.........168..4......28.9..2.9416.....2.....6.9.82.4...41.6..
576843921493261578218759436951687342647132859832594167184326795365978214729415683 solution grid


Code: Select all

123456789457189236698372145241893657589627314736514928314968572862735491975241863 min lexical
1.3.5......71.9...69.37......1..3..75.96.73.....51.......96..........4....5...86. min lexical loki


To get the min lexical in this case, we had first to transpose the grid, then
465 978 312 rows reordering
978 645 132 columns reordering
And this solution grid has no auto morph. (expected to be 1/10000 of the solution grids)

The solution grid has the rank 3 636 310 645.
Using this 64 characters equivalence
".123456789abcdefghiklmnopqrstuvwxyzABCDEFGHIKLMNOPQRSTUVWXYZ&"
The bit field becomes
mx5sxBL13p.84Z

so, in text mode, the canonical “loki” could be
3636310645mx5sxBL13p.84Z

Easy to decompress (some micro seconds per puzzle),
Not too hard to compress (28 milliseconds in my test)
with a sorting sequence per solution grid.

and for sure, 2 puzzles having a different canonical morph are different.
note: in my current code, the auto morphs issue is not covered


I’ll make a test on the 17 clues data base to see what gives the .zip compressor on such a file
but it would be interesting to test the new data base of puzzles having the tridagon pattern.
I am missing the link to download the current status of this data base;

[coloin]

Very good.
I was going to say that you dont need to worry about automorphs in the minlex solution grid.
But I see now that two puzzle isomorphs would be different in the minlex solution grid...
Maybe the solution could be that on the rare occasion the solution grid is isomorphic .. you somehow generate all the isomorphic puzzles and take the min lex.

please could you show how the 64 code works to generate the pattern !

presumably this code gives the minlex solution grid and the puzzle

[champagne]

Hi coloin

Very good.
I was going to say that you dont need to worry about automorphs in the minlex solution grid.
But I see now that two puzzle isomorphs would be different in the minlex solution grid...
Maybe the solution could be that on the rare occasion the solution grid is isomorphic .. you somehow generate all the isomorphic puzzles and take the min lex.

Right for all.
The code missing in my current draft is the comparison of 2 bit fields of size 81 to chose the min lexical one.
But even if it is not a frequent case, this must be done "live" in the clearing of redundant puzzles appearing in the scan of a solution grid to extract puzzles of size X.

Very good.
please could you show how the 64 code works to generate the pattern !
presumably this code gives the minlex solution grid and the puzzle

The code uses all DLLS recently created.
my draft (main actions)

call the brute force solver to get the solution grid
call the minlexing function and get back the minimal sol and the perm descriptors (usually one with a maximum of 648)
Morph the puzzle to the first permutation (not finished do the same with auto morphs and keep the min lexical 81 bits field)
call the virtual catalog to get the rank
Turn all to the output format.
Here my working draft written yesterday

Hidden Text: Show

Code: Select all

const char* bit6 = ".123456789abcdefghiklmnopqrstuvwxyzABCDEFGHIKLMNOPQRSTUVWXYZ&";

void PuzzleInBitField(char* puz, char* d) {
   // d is 14*6=84 bits in 14 char
   for (int i = 0, k = 0; i < 14; i++) {
      register int v = 0;
      for (int j = 0; j < 6; j++,k++) {
         if (puz[k] != '.')v |= 1 << j;
         d[i] = bit6[v];
      }
   }
}


void C11() {
   cout << " C11_ find canonical for a file of puzzles" << endl;
   char* ze = finput.ze,zem[82], zem2[82]; zem[81]=0; zem2[81] = 0;
   int smin[81];
   ptpgc= SkbsSetModeWithAutos();
   pzhe= SkbfGetZhePointer();
   int* vv = pzhe->gsol;
   if (SkvcatSetModeGetVCDESK(2, &pvcdesc)) {
      cout << " set mode failed" << endl;
      return;
   }
   while (finput.GetLigne()) {
      if (strlen(ze) < 81)continue;// no empty line
      cout << ze << " puzzle to caniconalize" << endl;
      {
         int ir1 = SkbfCheckValidityQuick(ze);
         if (ir1 != 1) {
            cout << " invalid puzzle ir1="<<ir1 << endl;
            continue;
         }

         for (int i = 0; i < 81; i++) cout << vv[i] + 1;
         cout << " solback" << endl;
         //cout << pzhe->gsol << " sol to do min lex" << endl;
         SkbsGetMin(vv, smin);
         for (int i = 0; i < 81; i++) cout << smin[i] + 1;
         cout << " min solback" << endl;

      }
      GRIDPERM wgperm;
      char* pbase = ptpgc->t[0];
      for (int i = 0; i < 19; i++) cout << pbase[i];
      cout << " pbase nperm=" << ptpgc->nt << endl;
      wgperm.Import19(vv, pbase);
      wgperm.MorphPuzzle(ze, zem);
      cout << zem << " puz morphed" << endl;

      uint64_t r = SkvcatGetRankFromSolMin( smin);
      if (!r) {
         cout << " failed to find rank  " << endl;
         continue;
      }
      for (int i = 0; i < 81; i++) cout << smin[i] + 1;
      cout << " solmin rank  " << r << endl;
      char zbit[15]; zbit[14] = 0;
      PuzzleInBitField(zem, zbit);
      cout << zbit << "  bbit pattern for the puzzle" << endl;
      cout << r << ";" << zbit << " proposal for canonical" << endl;
      if (ptpgc->nt > 1) {
         cout << " auto morphs seen, check more" << endl;
         for (int i = 1; i < ptpgc->nt; i++) {// check auto morph get the smallest
            wgperm.Import19(vv, pbase);
            wgperm.MorphPuzzle(ze, zem2);
         }
      }

   }
   cout << "end of file   " << endl;
}


BTW, as the use of such a canonical morph implies a compressor decompressor tool,
a simpler option can be

33 bits for the rank of the solution grid
81 bits for the puzzle

114 bits in total exactly 19 bytes using the text mode 6 bits per byte, saving 5 bytes.

[champagne]

I an running a first validation test on the file of 4 634 322 sudokus in the t&e 3 "mith"s data base.

a stupid bug in the previous post, one character is missing to cover the 64 possible values of a 6 bit field, but this doesn't change the following results.

757 254 puzzles have been processed in a little more than 3 and half hours
around 57 sudokus per seconds to get the "canonical"
Only 5978 different solution grids are there, giving an average 126 sudokus per solution grid.

I suspected something similar. The full run will take about 30 hours, so the final result is expected to-morrow.

next task is to write the canonical => puzzle code and see what is the average run time per canonical.

[blue]

a stupid bug in the previous post, one character is missing to cover the 64 possible values of a 6 bit field, but this doesn't change the following results.

Before you get too far: there were 3 characters missing ... 'j' and 'J' included.
Another thing: this line in your code, is reading 3 bytes of garbage data.
There's a "fix" for it below.

Code: Select all

if (puz[k] != '.')v |= 1 << j;
->
if (k < 81 && puz[k] != '.')v |= 1 << j;

[champagne]

a stupid bug in the previous post, one character is missing to cover the 64 possible values of a 6 bit field, but this doesn't change the following results.

Before you get too far: there were 3 characters missing ... 'j' and 'J' included.
Another thing: this line in your code, is reading 3 bytes of garbage data.
There's a "fix" for it below.

Code: Select all

if (puz[k] != '.')v |= 1 << j;
->
if (k < 81 && puz[k] != '.')v |= 1 << j;

As usual, sharp eyes from blue.
The "6 bits transformer" must have 64 four printable characters. i added the missing "jJ"
and for the second fix, I preferred this

Code: Select all

   for (int j = 0; j < 6; j++,k++) {
         if (puz[k] != '.')v |= 1 << j;
         d[i] = bit6[v];
         if(k==80) break;
      }

thanks for help