oh yeah... now it works. thanx a lot!
On May 29, 5:20 pm, Vishal Thanki <vishaltha...@gmail.com> wrote:
> sorry, i made a mistake in explaining. when you are solving the gird,
> you will have the matrix[][] array partially filled. the bitmap used
> for solving the grid is different than the one being used for
> verifying. in case of verifying, you will have a completely blank
> bitmap, with not bits set. you will iterate through the matrix array
> and set the bits in bitmap accordingly. so the if condition will
> evaluate to true for all the conditions till you have the correct
> values for cells in grid. as soon as you get a duplicate value for a
> cell, the condition will become false. i hope that is clear.
>
> hope that helps.
>
> PS: just ignore the fill_bitmap() routine, it is only used at the
> starting of solving the grid, and not for verifying. if you observe
> the verify() routine, the bitmap[] array is a local array and
> initialized to 0 before use.
>
>
>
>
>
>
>
> On Sun, May 29, 2011 at 5:40 PM, Dumanshu <duman...@gmail.com> wrote:
> > 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
> > 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.
