no... what i mean to say is you have filled the bitmap in the process
of solving the grid. The way you are filling the bitmap is -> you are
taking values from the matrix and placing them in the bitmaps using bi
bj bk.
now in the verification you are checking the same matrix value against
the same bitmap field. it will "always" evaluate out to be false for
your if.
your if statement is checking whether the matrix value and the bitmap
value is same or not. you have used the matrix value to fill the
bitmap so obviously they will be same.
see in fill bitmap funciton u did for some i,j ->
bmp[bi] |= 1 << matrix[i][j];
bmp[bj] |= 1 << matrix[i][j];
bmp[bk] |= 1 << matrix[i][j];
that is for some particular i,j say 5,4
u took value matrix[5][4] =8 and set the bit in bitmap after
calculating bi,bj,bk - these values are bi ==5, bj== 13 and bk == 10
so now in bmp[5], bmp[10] and bmp[13] u have set the 8th bit.
now in verify function
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];
here during the loop when i==5 and j==4, the if condition will always
evaluate to false.
same thing will happen for every value in the matrix because the
corresponding bit has been set earlier.
so how is ur verification function working???
On May 29, 3:35 pm, Vishal Thanki <vishaltha...@gmail.com> wrote:
> yes, you are right. bitmap will be filled in the process of solving
> the grid. in verify routine, if the expression evaluates to false, it
> mean an element is encountered which is already present in row, col
> and 3x3 cube. this way you an tell that the solution is wrong.
>
> hope that helps.
>
>
>
>
>
>
>
> On Sun, May 29, 2011 at 2:01 PM, Dumanshu <duman...@gmail.com> wrote:
> > here in this part
> > 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];
>
> > I think you are checking the same values which u have already set in
> > the bitmap using the fill_bitmap function. like suppose the 1st cell
> > of the matrix has value 5. then using fill bitmap u have the set
> > corresponding 5th bit in all 3 places(row col 3by3 cell) using bi bj
> > and bk.
> > now in the verify function u checking the same bit against that matrix
> > value which u have already set. so everytime ur if statement will
> > evaluate to false.
>
> > I may be wrong... plz help.
>
> > On May 28, 9:15 pm, Vishal Thanki <vishaltha...@gmail.com> 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 <duman...@gmail.com> 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 algogeeks@googlegroups.com.
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+unsubscr...@googlegroups.com.
> >> > For more options, visit this group
> >> > athttp://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 algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group
> > athttp://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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
