|
View previous topic :: View next topic |
Author |
Message |
| briturner
| Joined: 14 Oct 2008 | Posts: 75 | : | | Items |
|
Posted: Sun Jan 11, 2009 9:37 pm Post subject: normalizing a sudoku puzzle |
|
|
Greetings,
I have trying to generate expert level puzzles. Everyone's ratings are different, but for me, that means a puzzle that needs a 2-Step Commonality to solve, of which I have only found 500 so far. None of the Top_50000 or Top_1465 qualify as expert level.
SE 1.2.1 rates these really hard puzzles at 10.3 to 11.9. Oddly, the highest rated by Suexratt (4580 , 1905), I do not consider an expert level, so ratings are somewhat subjective.
I generated some 10000+ new puzzles that are ranked expert, but I believe most of them are logical duplicates. I needed a method to compare puzzles. I saw some previous discussions on normalizing to a canonical version of the puzzle, but little on how exactly to do this.
Here is what I threw together to normalize a puzzle. I think it is correct, but not very efficient. I am sure there are better ways to do this.
Code: |
// define a box and grid type
struct box
{ union
{ char xy[3][3];
char a[9];
} g;
};
struct puz
{ union
{ box pxy[3][3];
box pa[9];
char str[81];
} pg;
};
// Char buffer functions (converting to puz type and normalizing the numbers)
//
// Str2Puz - loads a string into a puz data structure
// Puz2Str - converts the puz back into a string
// NormStr - normalizes the numbering in a string
puz Str2Puz (char *buf)
{ int i, j, x, y, t = 0;
puz p;
for (i = 0; i < 3; i++)
for (x = 0; x < 3; x++)
for (j = 0; j < 3; j++)
for (y = 0; y < 3; y++)
{ p.pg.pxy[i][j].g.xy[x][y] = buf[t++];
if ((p.pg.pxy[i][j].g.xy[x][y] < '1') || (p.pg.pxy[i][j].g.xy[x][y] > '9'))
p.pg.pxy[i][j].g.xy[x][y] = '.';
}
return p;
}
void Puz2Str (puz p, char *buf)
{ int i, j, x, y, t = 0;
for (i = 0; i < 3; i++)
for (x = 0; x < 3; x++)
for (j = 0; j < 3; j++)
for (y = 0; y < 3; y++)
buf[t++] = p.pg.pxy[i][j].g.xy[x][y];
buf[t] = 0;
}
void NormStr(char *buf)
{ char t[90], n = '1';
int i, j;
for (i = 0; i < 82; i++) t[i] = buf[i];
for (i = 0; i <81>= '1') && (t[i] <= '9'))
{ for (j = i+1; j < 81; j++)
if (t[j] == t[i]) { buf[j] = n; t[j] = '.';}
buf[i] = n; n++;
}
}
}
// Puzzle manipulation routines. These routines keep the same logical puzzles, but do
// things like rotate and mirror the puzzles to make it look different.
//
// RotatePuz (4) - Rotates the puzzle
// FlipOnDiag (4) - Flips the puzzle on either or both diagonals
// SwapBoxRow (6) - Swaps around the 3 rows of boxes
// SwapBoxCol (6) - Swaps around the 3 columns of boxes
// SwapRowInBox (6x3) - Swaps around the 3 rows within a set of boxes
// SwapColInBox (6x3) - Swaps around the 3 Columns within a set of boxes
//
// Rotate and FlipOnDiag I think are redundant, so you only need 1 of them
//
// Total posibilities are 4 * 6 * 6 * 6*6*6 * 6*6*6 = 6,718,464
// Add in the 9! ordering of numbers, and you have
// 6,718,464 * 362,880 = 2,437,996,216,320 variations
int order[6][3] = {{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}};
int rot[4][9] = {{0, 1, 2, 3, 4, 5, 6, 7, 8}, {6, 3, 0, 7, 4, 1, 8, 5, 2},
{2, 5, 8, 1, 4, 7, 0, 3, 6}, {8, 7, 6, 5, 4, 3, 2, 1, 0}};
puz RotatePuz (puz p, int n) // 0-3 (0 = no change)
{ puz t; int i, j, x;
if (!n) return p;
t = p;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
for (x = 0; x < 9; x++)
t.pg.pxy[i][j].g.a[x] = p.pg.pxy[i][j].g.a[rot[n][x]];
for (i = 0; i < 9; i++)
p.pg.pa[i] = t.pg.pa[rot[n][i]];
return p;
}
puz FlipOnDiag (puz p, int n) // 0-3 (0 = no change)
{ puz t; int i, j, x, y;
if (n & 1)
{ for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
for (x = 0; x < 3; x++)
for (y = 0; y < 3; y++)
t.pg.pxy[i][j].g.xy[x][y] = p.pg.pxy[i][j].g.xy[y][x];
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
p.pg.pxy[i][j] = t.pg.pxy[j][i];
}
if (n & 2)
{ for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
for (x = 0; x < 3; x++)
for (y = 0; y < 3; y++)
t.pg.pxy[i][j].g.xy[x][y] = p.pg.pxy[i][j].g.xy[2-y][2-x];
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
p.pg.pxy[i][j] = t.pg.pxy[2-j][2-i];
}
return p;
}
puz SwapBoxRow (puz p, int n) // 0-5 (0 = no change) // checked
{ puz t; int i, j;
if (!n) return p;
t = p;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
p.pg.pxy[j][i] = t.pg.pxy[order[n][j]][i];
return p;
}
puz SwapBoxCol (puz p, int n) // 0-5 (0 = no change) //checked
{ puz t; int i, j;
if (!n) return p;
t = p;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
p.pg.pxy[i][j] = t.pg.pxy[i][order[n][j]];
return p;
}
puz SwapRowInBox (puz p, int n, int b) // 0-5, 0-2 (0 = no change)
{ puz t; int i, j, k;
if (!n) return p;
t = p;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
for (k = 0; k < 3; k++)
p.pg.pxy[b][i].g.xy[k][j] = t.pg.pxy[b][i].g.xy[order[n][k]][j];
return p;
}
puz SwapColInBox (puz p, int n, int b) // 0-5, 0-2 (0 = no change)
{ puz t; int i, j, k;
if (!n) return p;
t = p;
for (i = 0; i < 3; i++)
for (j = 0; j < 3; j++)
for (k = 0; k < 3; k++)
p.pg.pxy[i][b].g.xy[j][k] = t.pg.pxy[i][b].g.xy[j][order[n][k]];
return p;
}
// Puzzle comparison funtions
//
// PuzEqual - Compares 2 puzzles, including digits, for equality
// PuzComp - Compares 2 puzzles for positional data only
int PuzEqual(puz p1, puz p2)
{ int i, j;
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
if (p1.pg.pa[i].g.a[j] != p2.pg.pa[i].g.a[j]) return 0;
return 1;
}
int PuzComp(puz p1, puz p2, int num)
{ int i, x, j, y, n = 0;
for (i = 0; i < 3; i++)
for (x = 0; x < 3; x++)
for (j = 0; j < 3; j++)
for (y = 0; y <3> num) return 0;
if ((p1.pg.pxy[i][j].g.xy[x][y] == '.') && (p2.pg.pxy[i][j].g.xy[x][y] == '.')) continue;
if ((p1.pg.pxy[i][j].g.xy[x][y] != '.') && (p2.pg.pxy[i][j].g.xy[x][y] != '.')) continue;
if ( p1.pg.pxy[i][j].g.xy[x][y] != '.') return -1; else return 1;
}
return 0;
}
// Normalize puzzle - returns a normalized version of a puzzle
void Normalize (char *buf)
{ puz p, p2, pRotate, pDiag, pBoxRow, pBoxCol, pRowBox0, pColBox0, pColBox1, pColBox2, pRowBox1, pRowBox2;
int i, rotate, diag, boxrow, boxcol, rowinbox0, colinbox0, colinbox1, colinbox2, rowinbox1, rowinbox2;
char buf2[90];
// note : Flipping on the diagonal and Rotations equate to the same thing, so one disabled
p = p2 = Str2Puz(buf);
for (rotate = 0; rotate < 4; rotate++)
{ pRotate = RotatePuz(p, rotate);
for (diag = 0; diag < 1 /*4*/; diag++)
{ pDiag = FlipOnDiag(pRotate, diag);
for (boxrow = 0; boxrow < 6; boxrow++)
{ pBoxRow = SwapBoxRow(pRotate, boxrow);
for (boxcol = 0; boxcol < 6; boxcol++)
{ pBoxCol = SwapBoxCol(pBoxRow, boxcol);
for (rowinbox0 = 0; rowinbox0 < 6; rowinbox0++)
{ pRowBox0 = SwapRowInBox(pBoxCol, rowinbox0, 0);
for (colinbox0 = 0; colinbox0 < 6; colinbox0++)
{ pColBox0 = SwapColInBox(pRowBox0, colinbox0, 0);
if (PuzComp(pColBox0, p2, 3) < 0) continue;
for (colinbox1 = 0; colinbox1 < 6; colinbox1++)
{ pColBox1 = SwapColInBox(pColBox0, colinbox1, 1);
if (PuzComp(pColBox1, p2, 6) < 0) continue;
for (colinbox2 = 0; colinbox2 < 6; colinbox2++)
{ pColBox2 = SwapColInBox(pColBox1, colinbox2, 2);
if (PuzComp(pColBox2, p2, 27) < 0) continue;
for (rowinbox1 = 0; rowinbox1 < 6; rowinbox1++)
{ pRowBox1 = SwapRowInBox(pColBox2, rowinbox1, 1);
if (PuzComp(pRowBox1, p2, 54) < 0) continue;
for (rowinbox2 = 0; rowinbox2 < 6; rowinbox2++)
{ pRowBox2 = SwapRowInBox(pRowBox1, rowinbox2, 2);
if (PuzComp(pRowBox2, p2, 81) < 0) continue;
Puz2Str(pRowBox2, buf2);
NormStr(buf2);
for (i = 0; i <81> buf[i]) break; if (buf2[i] <buf>= 85)
{ p2 = pRowBox2; for (i = 0; i < 81; i++) buf[i] = buf2[i]; buf[81] = 0; }
} } } } } } } } } } }
|
So, while this works, if there is a source for better code, please let me know. Since this is not a key to my generator, but run after, efficiency is not terribly important, so I don't really plan on optimizing this all that much. But, there should be a much better method for doing this.
brit |
|
Back to top |
|
|
| zhouyundong
| Joined: 22 Nov 2008 | Posts: 43 | : | | Items |
|
Posted: Thu Jan 22, 2009 4:31 pm Post subject: |
|
|
This is what I called Unify,I met difficult, I can not write continue.My code is Code: | int transCourse[40];
int pTransCourse;
void swapMode1(int a, int b, bool flag=true)
{
for(int i=0; i<81; i++)
{
if(board[i] == a)
{
board[i] = b;
}
else if(board[i] == b)
{
board[i] = a;
}
}
if(flag)
{
transCourse[pTransCourse++] = (1<<24) + (a<<8) + b;
}
}
void swapMode2(int a, int b, bool flag=true)
{
int temp;
int skip = mult9[b-a];
for(int i=mult9[a]; i<mult9[a]+9; i++)
{
temp = board[i];
board[i] = board[i+skip];
board[i+skip] = temp;
}
if(flag)
{
transCourse[pTransCourse++] = (2<<24) + (a<<8) + b;
}
}
void swapMode3(int a, int b, bool flag=true)
{
int i;
int temp;
int skip = b - a;
for(i=a; i<81; i+=9)
{
temp = board[i];
board[i] = board[i+skip];
board[i+skip] = temp;
}
if(flag)
{
transCourse[pTransCourse++] = (3<<24) + (a<<8) + b;
}
}
void swapMode4()
{
swapMode2(3, 6);
swapMode2(4, 7);
swapMode2(5, 8);
}
void swapMode5()
{
swapMode3(3, 6);
swapMode3(4, 7);
swapMode3(5, 8);
}
void swapMode31(int a, int b)
{
swapMode3(a, b);
swapMode1(a+1, b+1);
}
bool handleUnify2()
{
int i;
int startPoint[7] = {3, 3, 4, 6, 6, 7};
int endPoint[7] = {4, 5, 5, 7, 8, 8};
moveBoard('b', 'k');
getAnswer();
if(flagAnswer != 1)
{
return false;
}
moveBoard('a', 'b');
pTransCourse = 0;
for(i=0; i<8> board[18])
{
swapMode2(1, 2);
}
switch(board[9])
{
case 4:
switch(board[18])
{
case 6:
swapMode31(4, 5);
break;
case 8:
swapMode31(6, 7);
break;
case 9:
swapMode31(6, 8);
break;
}
break;
case 5:
swapMode31(3, 4);
switch(board[18])
{
case 6:
swapMode31(4, 5);
break;
case 8:
swapMode31(6, 7);
break;
case 9:
swapMode31(6, 8);
break;
}
break;
case 6:
swapMode31(3, 5);
switch(board[18])
{
case 8:
swapMode31(6, 7);
break;
case 9:
swapMode31(6, 8);
break;
}
break;
case 7:
case 8:
swapMode5();
swapMode1(4, 7);
swapMode1(5, 8);
swapMode1(6, 9);
if(board[9] == 4 && board[18] == 6)
{
swapMode31(4, 5);
}
else if(board[9] == 5)
{
swapMode31(3, 4);
swapMode31(4, 5);
}
break;
}
for(i=0; i<6> board[mult9[endPoint[i]]])
{
swapMode2(startPoint[i], endPoint[i]);
}
}
if(board[27] > board[54])
{
swapMode4();
}
if(board[36]== 6 && board[63] == 5)
{
swapMode31(4, 5);
}
if(board[36]== 8 && board[72] == 7)
{
swapMode31(6, 7);
}
if(board[45]== 9 && board[72] == 8)
{
swapMode31(7, 8);
}
if(board[45]== 8 && board[63] == 7)
{
swapMode31(6, 7);
}
moveBoard('k', 'b'); // bakBoard to board
for(i=0; i<pTransCourse>>24) == 1)
{
swapMode1((transCourse[i]>>8)&0xFF, transCourse[i]&0xFF, false);
}
else if((transCourse[i]>>24) == 2)
{
swapMode2((transCourse[i]>>8)&0xFF, transCourse[i]&0xFF, false);
}
else if((transCourse[i]>>24) == 3)
{
swapMode3((transCourse[i]>>8)&0xFF, transCourse[i]&0xFF, false);
}
}
return true;
}
|
|
|
Back to top |
|
|
| briturner
| Joined: 14 Oct 2008 | Posts: 75 | : | | Items |
|
Posted: Thu Jan 22, 2009 6:24 pm Post subject: |
|
|
Greetings,
actually, my code is rather poor for normalizing. I originally wrote it to create random variations of puzzle that were logically equivalent. I then added in a normalization routine that is not efficient at all. There is another thread going about "Canonical sudoku algorithm?" in the setting sudoku section that would probably help more.
If I was to make an efficient version, I would first set the minimum rows, rather than trying them all.
I will try loading your code tonight when I get home
brit |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|