Forgot to mention that you have to fill the bitmap before calling this
routine. This code is the part of the actual sudoku solver code. Here
is the bitmap filling code which is very simple..
void fill_bitmap(int *bmp)
{
int i, j;
for (i = 0; i < GRID_SIZE; i++) {
for (j = 0; j < GRID_SIZE; j++) {
if (matrix[i][j]) {
bmp[bi] |= 1 << matrix[i][j];
bmp[bj] |= 1 << matrix[i][j];
bmp[bk] |= 1 << matrix[i][j];
}
}
}
}
Need not to mention that marix[][] is the 2-D array to represent sudoku grid.
On Sat, May 28, 2011 at 9:45 PM, Vishal Thanki <[email protected]> wrote:
> here is the code..
>
> #define bi (i)
> #define bj (GRID_SIZE+j)
> #define bk (int)((GRID_SIZE*2)+(glb_sqrt*(i/glb_sqrt)+(j/glb_sqrt)))
>
> /*glb_sqrt should be the square root of grid_size (i.e. 3 if its a 9x9
> sudoku). */
>
> /* #define bk (int)((GRID_SIZE*2)+(5*(i/5)+(j/5))) */
>
>
> /*
> * This function will verify solved grid. It will start with each element
> * in grid and update the bitmap step by step. As soon as it encounters an
> * element which is already present in bitmap, it will return error.
> *
> */
>
> int verify()
> {
> int i, j, k;
> int bitmap[GRID_SIZE*3] = {0};
> int bmp_idx;
> for (i = 0; i < GRID_SIZE; i++) {
> for (j = 0; j < GRID_SIZE; j++) {
> if ((((bitmap[bi] >> matrix[i][j]) & 0x1) == 0x0) &&
> (((bitmap[bj] >> matrix[i][j]) & 0x1)
> == 0x0) &&
> (((bitmap[bk] >> matrix[i][j]) & 0x1)
> == 0x0)) {
> bitmap[bi] |= 1 << matrix[i][j];
> bitmap[bj] |= 1 << matrix[i][j];
> bitmap[bk] |= 1 << matrix[i][j];
> } else {
> printf("Sudoku Error: i = %d, j = %d\n", i, j);
> return -1;
> }
>
>
> }
> }
> return 0;
> }
>
>
> On Sat, May 28, 2011 at 11:53 AM, Dumanshu <[email protected]> wrote:
>> Given a n by n matrix. Suggest an algorithm to verify its correctness
>> given a configuration. User can enter numbers only between 1 to n.
>> I need this in 2 ways -
>> 1. for the n by n matrix, suggest an elegant way for validating it.
>> 2. suggest a data structure for this sudoku so that the structure aids
>> in its verification.
>>
>> thnx for the help.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to [email protected].
>> To unsubscribe from this group, send email to
>> [email protected].
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
