Tuesday, September 25, 2007

Sudoku verifier using bit fields

A while back, a friend of mine had this idea of writing the most efficient sudoku verifier.

So I thought I would give it a shot. And this is what I've come up with:

char VerifySudoku(char grid[81])
{
   unsigned int bitFlags = 0;
   unsigned short buffer; // to speed up things
   char r, c;

   for (r = 0; r < 9; bitFlags = 0, ++r)
   {
      for (c = 0; c < 9; ++c)
      {
         buffer = r/3*3+c/3;

                     // check horizontally
         bitFlags |= 1 << (27-grid[(r<<3)+r+c])
                     // check vertically
                  |  1 << (18-grid[(c<<3)+c+r])
                     
// check subgrids
                  |  1 << (9-grid[(buffer<<3)+buffer+r%3*3+c%3]);
      }
      if (bitFlags != 0x7ffffff)
         return 0;
   }
   return 1;
}



Normally, one would have 3 loop one to scan horizontally, the other to scan vertically and lastly one to scan the 4 subgrids. If any one of that contain duplicated number, the grid is invalid. But here, one is enough. I scan 3 of the criteria in one single loop. Nothing fancy here, just the work of a boring soul. Haha...

No comments: