[algogeeks] Sudoku verification problem
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.
Re: [algogeeks] Sudoku verification problem
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 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.
Re: [algogeeks] Sudoku verification problem
Forgot to mention that you have to fill the bitmap before calling this
routine. This code is the part of the actual sudoku solver code. Here
is the bitmap filling code which is very simple..
void fill_bitmap(int *bmp)
{
int i, j;
for (i = 0; i GRID_SIZE; i++) {
for (j = 0; j GRID_SIZE; j++) {
if (matrix[i][j]) {
bmp[bi] |= 1 matrix[i][j];
bmp[bj] |= 1 matrix[i][j];
bmp[bk] |= 1 matrix[i][j];
}
}
}
}
Need not to mention that marix[][] is the 2-D array to represent sudoku grid.
On Sat, May 28, 2011 at 9:45 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 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.
