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 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 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.
