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 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
}
