[algogeeks] Re: Sudoku verification problem
A data structure could be a mapping from each of the N*N cells to the three regions it belongs to, and then for each region, a set of N bits indicating which values it already contains. Then the validation simply involves iterating over the cells. For each one, if any of the three regions already contain the value of that cell, validation fails. Otherwise, set the bit for that value in the three regions. A more challenging problem: Given an unsolved Sudoku puzzle with some given cells and some unknown cells, either indicate that there is no solution, provide the one unique solution, or report that there are multiple solutions and provide one example. Don On May 28, 1:23 am, Dumanshu 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 at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sudoku verification problem
oh yeah... now it works. thanx a lot!
On May 29, 5:20 pm, Vishal Thanki 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 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 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 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 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;
> >> >>
Re: [algogeeks] Re: Sudoku verification problem
what i understood from your problem is, when the configuration is
given by user, it can be directly stored into matrix[][] array. that
will solve your problem in o(n^2), where n=9.
On Sun, May 29, 2011 at 5:50 PM, Dumanshu wrote:
> 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 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 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 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 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;
>> > >>
Re: [algogeeks] Re: Sudoku verification problem
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 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 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 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 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)
>> >> &&
>
[algogeeks] Re: Sudoku verification problem
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 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 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 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 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
[algogeeks] Re: Sudoku verification problem
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 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 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 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 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 dat
Re: [algogeeks] Re: Sudoku verification problem
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 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 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 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 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.
[algogeeks] Re: Sudoku verification problem
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 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 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 at
http://groups.google.com/group/algogeeks?hl=en.
