Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

normalizing a sudoku puzzle

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Sun Jan 11, 2009 9:37 pm    Post subject: normalizing a sudoku puzzle Reply with quote
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
View user's profile Send private message
zhouyundong

Joined: 22 Nov 2008
Posts: 43
:

Items
PostPosted: Thu Jan 22, 2009 4:31 pm    Post subject: Reply with quote
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
View user's profile Send private message Send e-mail
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Thu Jan 22, 2009 6:24 pm    Post subject: Reply with quote
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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron