SudokuP - Min Clue Project

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: SudokuP - Min Clue Project

Postby blue » Tue Jun 26, 2018 7:51 pm

blue wrote:
Mathimagics wrote:We can't canonicalise clue sets, only solutions (and I think this is due to the intricacies of blue's transformations).

Later today, I'll find that code, and make a version that takes a puzzle and its solution for input.

The original (C++) code was here.
The updated code is below.
[ The global variables are the same, and the grid canonicalization routine has been modified and renamed. ]

There are two canonicalization routines:
    sudokup_canonicalize_g(...) canonicalizes solution grids.
    sudokup_canonicalize_sp(...) canonicalizes (solution,puzzle) pairs.
The first one is the original 'sudokup_canonicalize' routine, modified to to "in place" canonicalization.
The new one, also does "in place" canonicalization.
They both do row-minlex canonicalization.

For (solution,puzzle) pairs, the canonical form is defined to be the one that has a (row-)minlex solution grid, with the puzzle being minlex with respect to the automorphisms of the minlex solution grid.

Hidden Text: Show
Code: Select all
enum { TrCount = 8, };
int transforms[TrCount][81];

void init_transforms()
{
   for (int rb = 0; rb < 3; rb++)
   for (int rp = 0; rp < 3; rp++)
   for (int cb = 0; cb < 3; cb++)
   for (int cp = 0; cp < 3; cp++)
   {
      transforms[0][9 * (3 * rb + rp) + (3 * cb + cp)] = 9 * (3 * rb + rp) + (3 * cb + cp);   // r' = r , c' = c , b' = b , p' = p   e
      transforms[1][9 * (3 * rb + rp) + (3 * cb + cp)] = 9 * (3 * cb + cp) + (3 * rb + rp);   // r' = c , c' = r , b' = b*, p' = p*   D
      transforms[2][9 * (3 * rb + rp) + (3 * cb + cp)] = 9 * (3 * rp + rb) + (3 * cp + cb);   // r' = r*, c' = c*, b' = p , p' = b   E
      transforms[3][9 * (3 * rb + rp) + (3 * cb + cp)] = 9 * (3 * rb + cb) + (3 * rp + cp);   // r' = b , c' = p , b' = r , p' = c   F
      transforms[4][9 * (3 * rb + rp) + (3 * cb + cp)] = 9 * (3 * cp + rp) + (3 * cb + rb);   // r' = p*, c' = b*, b' = c*, p' = r*   G
      transforms[5][9 * (3 * rb + rp) + (3 * cb + cp)] = 9 * (3 * cp + cb) + (3 * rp + rb);   // r' = c*, c' = r*, b' = p*, p' = b*   D*E
      transforms[6][9 * (3 * rb + rp) + (3 * cb + cp)] = 9 * (3 * cb + rb) + (3 * cp + rp);   // r' = b*, c' = p*, b' = c , p' = r   D*F
       transforms[7][9 * (3 * rb + rp) + (3 * cb + cp)] = 9 * (3 * rp + cp) + (3 * rb + cb);   // r' = p , c' = b , b' = r*, p' = c*   D*G
   }
}

const int p3[6][3] = { { 0, 1, 2, }, { 2, 0, 1, }, { 1, 2, 0, }, { 2, 1, 0 }, { 0, 2, 1, }, { 1, 0, 2, } };

int sudokup_canonicalize_g(unsigned char *grid, bool use_restricted_subgroup = false)
{
   // canonicalize SudokuP (solution) grid -- row-minlex canonicalization

   if (!transforms[0][1])
      init_transforms();

   unsigned char g_best[81];
   g_best[9] = 10;
   int g_automorphisms = 0;
   int tr_cnt = use_restricted_subgroup ? 2 : TrCount;

   for (int n = 0; n < tr_cnt; n++)
   {
      unsigned char tg[81];
      {
         unsigned char *t = transforms[n];
         for (int i = 0; i < 81; i++)
            tg[i] = grid[t[i]];
      }

      // choose a row to map to row 1
      for (int rb = 0; rb < 3; rb++)
      for (int rp = 0; rp < 3; rp++)
      {
         int r1 = 3 * rb + rp;

         // make initial choices for other rows
         int r2 = (rp < 2) ? r1 + 1 : r1 - 2;
         int r3 = rp ? r1 - 1 : r1 + 2;
         int r4 = (r1 < 6) ? r1 + 3 : r1 - 6;
         int r7 = (r1 >= 3) ? (r1 - 3) : r1 + 6;

         int r_order[9];
         r_order[0] = r1;

         // choose a column order for row 1
         for (int pcb = 0; pcb < 6; pcb++)
         for (int pcp = 0; pcp < 6; pcp++)
         {
            int c_order[9];
            unsigned char map[10];

            for (int cb = 0; cb < 3; cb++)
            for (int cp = 0; cp < 3; cp++)
               c_order[3 * cb + cp] = 3 * p3[pcb][cb] + p3[pcp][cp];

            // build a symbol map, mapping the final r1, to "123456789"
            for (int c = 0; c < 9; c++)
               map[tg[9 * r1 + c_order[c]]] = c + 1;

            int c1 = c_order[0];

            // swap the final rows 2&3, as necessary, to force r2c1 < r3c1
            if (map[tg[9 * r2 + c1]] < map[tg[9 * r3 + c1]])
            {
               r_order[1] = r2;
               r_order[2] = r3;
            }
            else
            {
               r_order[1] = r3;
               r_order[2] = r2;
            }
            // swap the final bands 2&3, as necessary, to force r4c1 < r7c1
            if (map[tg[9 * r4 + c1]] < map[tg[9 * r7 + c1]])
            {
               r_order[3] = r4;
               r_order[6] = r7;
            }
            else
            {
               r_order[3] = r7;
               r_order[6] = r4;
            }

            r_order[4] = r_order[1] + (r_order[3] - r_order[0]);
            r_order[5] = r_order[2] + (r_order[3] - r_order[0]);
            r_order[7] = r_order[1] + (r_order[6] - r_order[0]);
            r_order[8] = r_order[2] + (r_order[6] - r_order[0]);

            for (int r = 1; r < 8; r++)
            for (int c = 0; c < 8; c++)
            {
               if (map[tg[9 * r_order[r] + c_order[c]]] > g_best[9 * r + c])
                  goto next;   // result will be strictly worse (for "minlex" comparison)
               if (map[tg[9 * r_order[r] + c_order[c]]] < g_best[9 * r + c])
                  goto keep;   // result will be strictly better (for "minlex" comparison)
            }

            ++g_automorphisms;
            goto next;      // result would exactly match g_best case (in "minlex" comparison)

keep:         // update "g_best case"
            for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
               g_best[9 * r + c] = map[tg[9 * r_order[r] + c_order[c]]];

            g_automorphisms = 1;
next:         ;
         }
      }
   }

   memcpy(grid, g_best, sizeof(g_best));
   return g_automorphisms;   // grid automorphisms
}

int sudokup_canonicalize_sp(unsigned char *solution, unsigned char *puzzle, bool use_restricted_subgroup = false)
{
   // canonicalize SudokuP "(solution,puzzle)" pair -- "solution first", row-minlex canonicalization

   if (!transforms[0][1])
      init_transforms();

   unsigned char s_best[81], p_best[81];
   s_best[9] = 10;
   int sp_automorphisms = 0;
   int tr_cnt = use_restricted_subgroup ? 2 : TrCount;

   for (int n = 0; n < tr_cnt; n++)
   {
      unsigned char ts[81], tp[81];
      {
         unsigned char *t = transforms[n];
         for (int i = 0; i < 81; i++)
         {
            ts[i] = solution[t[i]];
            tp[i] = puzzle[t[i]];
         }
      }

      // choose a row to map to row 1
      for (int rb = 0; rb < 3; rb++)
      for (int rp = 0; rp < 3; rp++)
      {
         int r1 = 3 * rb + rp;

         // make initial choices for other rows
         int r2 = (rp < 2) ? r1 + 1 : r1 - 2;
         int r3 = rp ? r1 - 1 : r1 + 2;
         int r4 = (r1 < 6) ? r1 + 3 : r1 - 6;
         int r7 = (r1 >= 3) ? (r1 - 3) : r1 + 6;

         int r_order[9];
         r_order[0] = r1;

         // choose a column order for row 1
         for (int pcb = 0; pcb < 6; pcb++)
         for (int pcp = 0; pcp < 6; pcp++)
         {
            int c_order[9];
            unsigned char map[10];

            for (int cb = 0; cb < 3; cb++)
            for (int cp = 0; cp < 3; cp++)
               c_order[3 * cb + cp] = 3 * p3[pcb][cb] + p3[pcp][cp];

            // build a symbol map, mapping the final r1, to "123456789"
            map[0] = 0;
            for (int c = 0; c < 9; c++)
               map[ts[9 * r1 + c_order[c]]] = c + 1;

            int c1 = c_order[0];

            // swap the final rows 2&3, as necessary, to force r2c1 < r3c1
            if (map[ts[9 * r2 + c1]] < map[ts[9 * r3 + c1]])
            {
               r_order[1] = r2;
               r_order[2] = r3;
            }
            else
            {
               r_order[1] = r3;
               r_order[2] = r2;
            }
            // swap the final bands 2&3, as necessary, to force r4c1 < r7c1
            if (map[ts[9 * r4 + c1]] < map[ts[9 * r7 + c1]])
            {
               r_order[3] = r4;
               r_order[6] = r7;
            }
            else
            {
               r_order[3] = r7;
               r_order[6] = r4;
            }

            r_order[4] = r_order[1] + (r_order[3] - r_order[0]);
            r_order[5] = r_order[2] + (r_order[3] - r_order[0]);
            r_order[7] = r_order[1] + (r_order[6] - r_order[0]);
            r_order[8] = r_order[2] + (r_order[6] - r_order[0]);

            // check transformed solution grid
            for (int r = 1; r < 8; r++)
            for (int c = 0; c < 8; c++)
            {
               if (map[ts[9 * r_order[r] + c_order[c]]] > s_best[9 * r + c])
                  goto next;   // result will be strictly worse (for "minlex" comparison)
               if (map[ts[9 * r_order[r] + c_order[c]]] < s_best[9 * r + c])
                  goto keeps;   // result will be strictly better (for "minlex" comparison)
            }

            // transformed grid matches best case ...

            // check similarly transformed puzzle
            for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
            {
               if (map[tp[9 * r_order[r] + c_order[c]]] > p_best[9 * r + c])
                  goto next;   // result will be strictly worse (for "minlex" comparison)
               if (map[tp[9 * r_order[r] + c_order[c]]] < p_best[9 * r + c])
                  goto keepp;   // result will be strictly better (for "minlex" comparison)
            }

            ++sp_automorphisms;
            goto next;      // result would exactly match '(s_best,p_best)' case (in "minlex" comparison)

keeps:         // update "best case" solution
            for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
               s_best[9 * r + c] = map[ts[9 * r_order[r] + c_order[c]]];

keepp:         // update "best case" puzzle
            for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
               p_best[9 * r + c] = map[tp[9 * r_order[r] + c_order[c]]];

            sp_automorphisms = 1;

next:         ;
         }
      }
   }

   memcpy(solution, s_best, sizeof(s_best));
   memcpy(puzzle, p_best, sizeof(p_best));
   return sp_automorphisms;   // "(s,p)" automorphisms
}
blue
 
Posts: 683
Joined: 11 March 2013

Re: SudokuP: 11-clue Search Strategy

Postby blue » Tue Jun 26, 2018 8:22 pm

Mathimagics wrote:Colin (coloin) has suggested a reduction method for finding 11-clue puzzles that have explicit clues-per-box properties.

Most of our known solutions (admittedly a small sample) have some box with 3 clues. We can find these by first looking for 17-clue puzzles with one box filled in (9 clues) and 8 clues in the other boxes. Then we just test each of 11-clue puzzles obtained by reducing the full box to 3 clues:

For example:

(...)

This has to be done for each box, but we only need to build our UA list once, we can simply mask out those UA's that reference cells in the filled box.

The full treatment (9 passes) seems to run 4 to 8 times faster than one-pass full HSet = 11 enumeration.

HSet enumeration time tends to increase/decrease exponentially wrt target HSet size, so while searching for 4-clues in a box cases would be even quicker, 2-clues per box dies in the bum.

However, given the fact that most known cases (16 of the 18 ED 11-clue puzzles) have 3 clues in a box, it makes sense to proceed with this approach.

The 9 HSet=8 emumerations may be fast, but the number of valid 9+8 puzzles could be quite large, and the "(9+8) -> (3+8)" reduction time could swamp the whole idea.

Another thing to consider, is that the SudokuP transformations used in canonicalization, can map rows, columns or p-sets to boxes (and vica-versa). The "2 of 18" puzzles that didn't have a 3-clue box, oddly enough, have all 3 of the other variations present ... a row, a column, and a p-set, each containg 3 clues. Each of them can be transformed (in several ways) to have 3 clues in a box, and actually it seems kind of unlikely that thier canonical forms wouldn't have contained 3-clue box.

To fully counter that, you would need to do 4*9 HSet=8 enumerations ... 9 each, on the input grid, and 3 of its isomorphs.
Added: Alternatively, you could do 9 enumerations with a full box, 9 with a full row, and so on.
Last edited by blue on Tue Jun 26, 2018 10:36 pm, edited 1 time in total.
blue
 
Posts: 683
Joined: 11 March 2013

Re: SudokuP - Min Clue Project

Postby Serg » Tue Jun 26, 2018 9:17 pm

Hi, blue!
blue wrote:All in all, what we have is:

14 ED puzzles
12 ED solution grids, with 18 valid 11-clue puzzles
Code: Select all
.2.45..........13........6.....9...........7............7..............5.....3... # 15449135 (B1)
12..........79.......3...................1...........8.4.....67.............8.... # 22504781 (B2)
..3...........82.1.79......................7.2............3...........6..4....... # 22979593 (B3)
........9......2....8..........4...........7................6.2......3..7.1..4... # 23068647 (B4)
...........6.....2...............53..8..............9.........77.1..........89... # 23201464 (B5)
1........4.....3............6......7.89.....5....4...................2.......2... # 23201702 (B6)
.....6...4.7.....2..........................3..5..........3.....8....96..4....... # 53380826 (B7)
.2........................2.7...........9........6.15...1..............8.....8..3 # 53541837 (O5 morph)
..3..............6..8..1.....5.............7..........67.9...........3..2........ # 53557072 (O4 morph)
............2.......8........5.....4.....3.....6.......7...........6....23.....9. # 53557072 (O4 morph)
............2.......8........5...........3.....6.......7.....4.....6....23.....9. # 53557072 (O2 morph)
..3..............6..8........5.............7..........67.9...........3..2..1..... # 53557072 (O2 morph)
.....6...........2..9......6...........9..8..24........7.............1..3........ # 53624261 (O1 morph)
.....6...........2..9......6...........9..8..24......................17.3........ # 53624261 (O3 morph)
(added)
......7.9.......3..6...2............6..............8.........1........4.7...8.... # 53658889 (B8)
1.......9...8.........72....7....3.....5........6.........3.....1................ # 53658889 (B8 morph)
.................69..........1...........3..5.............3.....1....97..4.....2. # 53658890 (B9)
.2............1............5..9.....6..72..........8................4..8..6...... # 53658890 (B9 morph)


I have a program giving conventional row-minlex form for SudokuP puzzles. Here are cited above SudokuP puzzles in minlex form.
Code: Select all
.................1.....2...........3.......45..6.78.........2..8...........5..... # 15449135 (B1)
.................1.....2....3...........2.....45......16..........7..58.......... # 22504781 (B2)
.................1....1............2........3..4..5...4..............67....8.7... # 22979593 (B3)
.................1.....2....1.............34........5.67..2...................83. # 23068647 (B4)
.......................1..2........3.45.........3.6.........78........5.....4.... # 23201464 (B5)
.................1.....2....3....................4.5..62.......1............7.89. # 23201702 (B6)
.......................1.2.........2..3...........4..5......6...4..........37..8. # 53380826 (B7)
..........................1.......2.....1.....2....34...5.........3.6.....7.....8 # 53541837 (O5 morph)
.................1....1............2..3.....4.....5...6........7.....58....4..... # 53557072 (O4 morph)
.................1....1............2..3.....4.....5...6........7.....58....4..... # 53557072 (O4 morph)
.........................12........3..4.56..........783...........8...........6.. # 53557072 (O2 morph)
.........................12........3..4.56..........783...........8...........6.. # 53557072 (O2 morph)
.......................1.2.......3..4...........5.......5.......67..........84..3 # 53624261 (O1 morph)
.................1....1............2..3.....4.....5...6........7.....85....4..... # 53624261 (O3 morph)
.................1.....2...........3.......4..56.7....3......8...............84.. # 53658889 (B8)
.................1.....2...........3.......4..56.7....3......8...............84.. # 53658889 (B8 morph)
.................1....1............2........3..45.6...4...............7....8.7... # 53658890 (B9)
.................1....1............2........3..45.6...4...............7....8.7... # 53658890 (B9 morph)

You can see that there are 4 duplicate puzzles in this list, so I confirm, that we have 14 ED 11-clue SudokuP valid puzzles now.

Serg
Serg
2018 Supporter
 
Posts: 606
Joined: 01 June 2010
Location: Russia

Re: SudokuP: 11-clue Search Strategy

Postby Mathimagics » Tue Jun 26, 2018 10:42 pm

blue wrote:The 9 HSet=8 emumerations may be fast, but the number of valid 9+8 puzzles could be quite large, and the "(9+8) -> (3+8)" reduction time could swamp the whole idea.


Interestingly, that doesn't seem to be a problem.

Here are some stats for 3 sample grids, the first 2 are known solution grids, the 3rd a random selection from the pool:

Code: Select all
Grid #    sUA     NHS11    time         NHS8   N18P   time
----------------------------------------------------------
15449135   25    459665     284      1456118     12     32
22504781   16   4019288    1657      9205053     51    195
10516441   24    610613     816      5091718     19    160


sUA is the number of small UA's (sz <= 12). The total number of UA's used in the HS enum process is 250 per grid.

NHS11 is the number of HSets of size <= 11 (standard method), NHS8 is the number of HSets of size <= 8 (reduction method).

N18P is the actual number of 18-clue puzzles found. Reducing these is a relatively trivial overhead (84 extra solver calls) in any case.

The time difference is significant, despite the number of HSets being higher for reduction method. Reduction method enumerates many more HSets, performs consequently many more Solver calls.

The overweening cost in this procedure is the HSet enumeration. This rises more or less exponentially with the size of the HSet's being enumerated.

Not only do we have 3 less levels of recursion for the reduction method, we also have far less UA's to deal with at any one time, since we only deal with a fraction of them.

We could probably do the "full monty" (boxes, rows, cols) and still come in well ahead, but what I am concentrating on for the moment is the existence problem.

I would just like to find one new 11-clue puzzle, to rid myself of the niggling doubts about their existence!
User avatar
Mathimagics
2017 Supporter
 
Posts: 729
Joined: 27 May 2015

Re: SudokuP: 11-clue Search Strategy

Postby blue » Tue Jun 26, 2018 11:36 pm

Mathimagics wrote:
blue wrote:The 9 HSet=8 emumerations may be fast, but the number of valid 9+8 puzzles could be quite large, and the "(9+8) -> (3+8)" reduction time could swamp the whole idea.


Interestingly, that doesn't seem to be a problem.

(...)

That is interesting ... and for me, totally unexpected !

Cheers,
Blue.
blue
 
Posts: 683
Joined: 11 March 2013

Re: SudokuP: 11-clue Search Strategy

Postby Mathimagics » Wed Jun 27, 2018 12:23 am

blue wrote:The "2 of 18" puzzles that didn't have a 3-clue box, oddly enough, have all 3 of the other variations present ... a row, a column, and a p-set, each containg 3 clues. Each of them can be transformed (in several ways) to have 3 clues in a box, and actually it seems kind of unlikely that thier canonical forms wouldn't have contained 3-clue box.

To fully counter that, you would need to do 4*9 HSet=8 enumerations ... 9 each, on the input grid, and 3 of its isomorphs.
Added: Alternatively, you could do 9 enumerations with a full box, 9 with a full row, and so on.


The row/col/pset approach is preferable, since we wouldn't have to gen new UA's.

If the 2 cases of no 3-in-a-box both have 3-in everything else, and that turned out to be common to all 11C puzzles, then that would mean we'd only have to try 2 ways, not 4. That would make the "reduction" method both cheap (relative to HS11 method) AND rigorous.
User avatar
Mathimagics
2017 Supporter
 
Posts: 729
Joined: 27 May 2015

Re: SudokuP - Min Clue Project

Postby Leren » Wed Jun 27, 2018 12:32 am

Well done serg ! You've done what I was going to ask for without my asking. I've just rationalised your table by removing redundant entries, and dropping the unnecessary word morph, from the 14 known ED 11 Clue Sets.

Code: Select all
.......................1.2.......3..4...........5.......5.......67..........84..3 # 53624261 (O1)
.........................12........3..4.56..........783...........8...........6.. # 53557072 (O2)
.................1....1............2..3.....4.....5...6........7.....85....4..... # 53624261 (O3)
.................1....1............2..3.....4.....5...6........7.....58....4..... # 53557072 (O4)
..........................1.......2.....1.....2....34...5.........3.6.....7.....8 # 53541837 (O5)
.................1.....2...........3.......45..6.78.........2..8...........5..... # 15449135 (B1)
.................1.....2....3...........2.....45......16..........7..58.......... # 22504781 (B2)
.................1....1............2........3..4..5...4..............67....8.7... # 22979593 (B3)
.................1.....2....1.............34........5.67..2...................83. # 23068647 (B4)
.......................1..2........3.45.........3.6.........78........5.....4.... # 23201464 (B5)
.................1.....2....3....................4.5..62.......1............7.89. # 23201702 (B6)
.......................1.2.........2..3...........4..5......6...4..........37..8. # 53380826 (B7)
.................1.....2...........3.......4..56.7....3......8...............84.. # 53658889 (B8)
.................1....1............2........3..45.6...4...............7....8.7... # 53658890 (B9)

Hopefully this form of presentation will avoid confusion and double counting. Leren
Leren
 
Posts: 3307
Joined: 03 June 2012

Re: SudokuP - Min Clue Project

Postby Leren » Wed Jun 27, 2018 12:46 am

blue wrote: The "2 of 18" puzzles that didn't have a 3-clue box, oddly enough, have all 3 of the other variations present ... a row, a column, and a p-set, each containing 3 clues.

Actually that "problem" is easily overcome. By taking the F, G, or E transform of a puzzle that doesn't have a 3 clue box but has a 3 clue row/column, you can convert it into one with a 3 clue box.

Of the 14 ED clue sets, so far discovered, I was able to convert all of them into a form with a 3 clue box with the clues in one row and one column (non-diagonal), which I was able to then juggle into r1c12 and r2c1 and label them 123.

So in my (so far massively unsuccessful) search for the elusive (L1) I only have to place 8 clues, not 11. That and a lot of other tricks enable me to reduce the solution space, but so far no luck.

Leren
Leren
 
Posts: 3307
Joined: 03 June 2012

Re: SudokuP - Min Clue Project

Postby coloin » Wed Jun 27, 2018 8:45 am

Well done Mathimamagics for implementing it - the reduction of the HS and less clues do the trick it seems.
Removing clues has always been quick [ way back it was how we found the Easter Monster puzzle]

I'm sure i'm not the only one who has difficulty with visualizing an "equivalent" puzzle which has different clue count in a box - but i'm prepared to accept that the transformation allows this to be the case
I suppose we should confirm that there isn't an 11 clue puzzle which doesn't have a pseudo-equivalent puzzle with 3 clues in a box ! [ or you perhaps have already done this]

Interestingly the approach to find 9plus13s in normal sudoku - wasn't fast enough to recover from the x9 increase in the number of grids - but it appears that the exponential effect of less clues and less sets makes it more efficient in this case

interestingly - no new puzzles yet with the job i'm doing

Leren [ 3 plus 8 search ] hasn't found any either ! even with the tricks to reduce the space
coloin
 
Posts: 1727
Joined: 05 May 2005

Re: SudokuP - Min Clue Project

Postby Leren » Wed Jun 27, 2018 10:51 am

I just checked that blue announced the finding of B1 - B9 on March 10 ... and there has been a deathly silence ever since. Leren
Leren
 
Posts: 3307
Joined: 03 June 2012

Re: SudokuP - Min Clue Project

Postby coloin » Fri Jun 29, 2018 8:43 am

Mathimagic's modified program is blitzing through a small collection of possible solution grids .....and will finish in a few days.
Only blue knows how hard he tried to generate a new puzzle - but it is always possible that one will be found ....

A by product of the 3plus8 search is that a good few 9plus9s [Im presuming these are N18Ps] are found incidentally - there seems to be some grids with few and some with > 1000
Those which have many , take longer to process and have more low HS.
Random grids from the big collection I expect have less N18Ps
from Mathimagic's program
Code: Select all
G130 = 23181165, mode B, et =    377.398, HS6 = 1001, HS7 = 215333, HS8 = 12396725, HS11 = 32764, N18P = 13                               
G131 = 23181532, mode B, et =    556.739, HS5 = 5, HS6 = 1849, HS7 = 360095, HS8 = 17700244, HS11 = 32764, N18P = 82                     
G132 = 23183754, mode B, et =    379.738, HS6 = 426, HS7 = 190715, HS8 = 13794824, HS11 = 32764, N18P = 51                               
G133 = 23184506, mode B, et =    137.573, HS6 = 113, HS7 = 48517, HS8 = 4899614, HS11 = 32764, N18P = 4                                   
G134 = 23186895, mode B, et =     35.757, HS7 = 5593, HS8 = 1019211, HS11 = 32764, N18P = 1                                               
G135 = 23189096, mode B, et =     66.182, HS6 = 42, HS7 = 20366, HS8 = 1898606, HS11 = 32764, N18P = 0                                   
G136 = 23190907, mode B, et =     23.251, HS6 = 3, HS7 = 4510, HS8 = 665531, HS11 = 32764, N18P = 2                                       
G137 = 23193040, mode B, et =    585.548, HS5 = 2, HS6 = 1974, HS7 = 394845, HS8 = 19567473, HS11 = 32764, N18P = 78                     
G138 = 23196261, mode B, et =   3447.408, HS5 = 67, HS6 = 33814, HS7 = 3131382, HS8 = 84882679, HS11 = 32764, N18P = 86                   
G139 = 23198598, mode B, et =   1098.062, HS5 = 5, HS6 = 4644, HS7 = 794152, HS8 = 35230613, HS11 = 32764, N18P = 184                     
G140 = 23199767, mode B, et =    169.824, HS6 = 134, HS7 = 68928, HS8 = 6237552, HS11 = 32764, N18P = 9                                   
G141 = 23199892, mode B, et =    116.817, HS6 = 68, HS7 = 48788, HS8 = 4226068, HS11 = 32764, N18P = 44                                   
G142 = 23199965, mode B, et =  20167.546, HS4 = 1, HS5 = 2030, HS6 = 399497, HS7 = 20998374, HS8 = 368084735, HS11 = 32764, N18P = 8361   
G143 = 23200458, mode B, et =    488.702, HS5 = 6, HS6 = 2414, HS7 = 326700, HS8 = 14586000, HS11 = 32764, N18P = 141                     
G144 = 23200894, mode B, et =   2382.689, HS5 = 8, HS6 = 10503, HS7 = 1769839, HS8 = 78328460, HS11 = 32764, N18P = 592                   
G145 = 23201463, mode B, et =   2256.761, HS5 = 17, HS6 = 13998, HS7 = 1765795, HS8 = 65262478, HS11 = 32764, N18P = 886                 
G146 = 23201714, mode B, et =   6594.219, HS5 = 144, HS6 = 75015, HS7 = 6338996, HS8 = 163014180, HS11 = 32764, N18P = 1958               
G147 = 29198602, mode B, et =    423.469, HS5 = 2, HS6 = 1889, HS7 = 269580, HS8 = 12707045, HS11 = 32764, N18P = 19                     
G148 = 29235177, mode B, et =   1263.118, HS5 = 11, HS6 = 6866, HS7 = 923399, HS8 = 38328133, HS11 = 32764, N18P = 53                     
G149 = 29239726, mode B, et =    114.435, HS6 = 76, HS7 = 32450, HS8 = 3609841, HS11 = 32764, N18P = 23                                   
G150 = 29242685, mode B, et =    347.882, HS6 = 679, HS7 = 184249, HS8 = 11912718, HS11 = 32764, N18P = 15                               


In the interim - One way of casually looking for new puzzles [if there are any] would be to generate further N18Ps from these. say perform a {-1+1} on the 9 clues without the completed box.
This isn't quite as simple as in normal sudoku - possible 6^4 morphing needs to be done, the yield ultimately depending on how "close" and how many there are.
Reducing the found N18P to 9plus8 looking for 2plus9 or3plus8 as mentioned is an efficient process
coloin
 
Posts: 1727
Joined: 05 May 2005

Re: SudokuP - Min Clue Project

Postby Leren » Fri Jun 29, 2018 11:09 am

Hi Coloin, I'm not quite sure whether your 3+8 search is referring to my method but just in case it is, here are some of the extra "tricks" I have used to reduce my search space.

The following are suitably morphed versions of the 14 previously found 11 clue sets O1 - O5 and B1 - B9 to bring them into a common "shape"

Hidden Text: Show
Code: Select all
12.......3...........4.......4.....5..6...........2.....7..............8....7....   M (O1)
12.......3...........4.......4.....5..6.....7.....1.....8...................8....   M (O2)
12.......3..4...........5....5..6.....7..............2..8......................8.   M (O3)
12.......3..4...........5....5..6.....7..............1..8......................8.   M (O4)
12.......3..4...........5....6..7.....7..............2..8.....................8..   M (O5)
12.4.....3..............5....5..6.....7.............1...8.......................4   M (B1)
12.......3...........4..............5.6...........78.2....4....................6.   M (F(B2))
12.......3..4...........5....6...........7..3..5........8..........2.............   M(TB3)
12.4.....3...................5..6.....7.............2......8........5...........4   M(E(B4))
12.......3...........4.........................5..6.....7............4.3....78...   M(B5)
12.......3..4................5..6.....7.............2............8..9...........3   M(E(B6))
12.......3...4..........5....8......7...................5........6..7...........2   M(E(B7))
12.......3...........4...5.........5.6.........4...6............7...........8....   M(E(B8))
12.......3...........4..5..67..............3......6.....8..................8.....   M(B9)

When you stare at these long enough, you can adopt the following "rules" in addition to the placement of the first 3 clues.
Hidden Text: Show
1. Clue 4 can only be in Box 2 and can only be 4.

2. Clue 5 can only be in Boxes 3-6. If it's in Box 3 it can only be 5, in Box 4 it can only be 4 or 5. In the other boxes it can only be 1 - 5.

3. Clue 4 must be <= 6, Clue 5 must be <= 7, Clue 8 must be <= 8 and the last 3 clues can be any number.

4. The clues in Tier 1 are all different. The maximum number of clues in Box 4 and 7 is 2 each, and the number of clues in Box 4 >= the number of clues in Box 7.

5. The number of boxes with clues in them is 7 or 8.

6. The minimum number of solved cells after singles have been applied to the 11 clues must be 18. This was the case for all 14 clue sets except B6 (17) and B9 (9).

7. Obviously at least 8 different digits must be present in the clues.

All these "rules" are designed to overcome relabelling issues, differentiating between Tier and Stack 2 and 3 swaps and hopefully find a clue set that has a "shape" that roughly fits the known 14.

My programming is done in Visual Basic (because I'm lazy) no doubt much slower than C++, so I need all the help I can get ! About 1 in 1000 clues sets is looked at beyond singles and I have a "fast" solution counter that only differentiates between 0, 1 or >= 2 solutions.

So after about 6 Billion Tries I have had 10 hits, all of which were isomorphs of one of the 14 already found. As you can see I'm not trying to be too scientific here, I only really just want to find 1 new 11 clue set and get my initial on it.

Hope this helps, Leren
Last edited by Leren on Fri Jun 29, 2018 8:21 pm, edited 1 time in total.
Leren
 
Posts: 3307
Joined: 03 June 2012

Re: SudokuP - Min Clue Project

Postby Mathimagics » Fri Jun 29, 2018 1:05 pm

Leren wrote:My programming is done in Visual Basic (because I'm lazy) no doubt much slower than C++, so I need all the help I can get !


Is that VB6 or VB.Net?

I use VB6 extensively for front-end work, algorithm development etc. On 32-bit Windows (ie 7,8) VB6 number-crunching applications can be competitive (time-wise) with eqyivalent C versions by using compiler optimisations ( suppressing runtime error checking). VB6's internal compiler is actually a modified 'C' compiler.

We can make dobrichev's fast Sudoku/SudokuP solvers VB6-callable by placing them in a DLL.
User avatar
Mathimagics
2017 Supporter
 
Posts: 729
Joined: 27 May 2015

Re: SudokuP - Min Clue Project

Postby Leren » Fri Jun 29, 2018 9:02 pm

mathimagics wrote :Is that VB6 or VB.Net?

I'm not computer literate enough to understand your question. I use visual basic within Excel (I still use the version I bought way back in 2007). This has the advantage of having a ready made input/output interface (a worksheet).

I'm a bit more that 10% of the way through my process, I've actually got past the entire r1c4 = 4 search space.

Leren
Leren
 
Posts: 3307
Joined: 03 June 2012

Re: SudokuP - Min Clue Project

Postby Mathimagics » Fri Jun 29, 2018 9:40 pm

.
Ok, that explains why it's slow going - VBA (Visual Basic for Applications) is just an interpretive form of VB6 used in apps like ExCel.

Interpretive mode is much, much slower than compiled code.
User avatar
Mathimagics
2017 Supporter
 
Posts: 729
Joined: 27 May 2015

PreviousNext

Return to Sudoku variants