I think ur verification function is correct but it works only if user
is entering the values one by one. as soon as he enters a duplicate
value it will show a error. It will work for the case of ur solver as
ur code itself is generating the values.
But here in this verification problem u r given a configuration from a
user. i.e. all values at once not one by one.
So one thing that can be done is use ur fillbitmap function and then
check if any of the 9 Least significant bits of the 27 values in ur
bmp array is not set. If thats the case then sukoku isn't correct.
but then this code would take O(n^2) = (3*n*n) time here n is 9.
On May 29, 5:10 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.
