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 <duman...@gmail.com> 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 <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.
