Sudoku - Region testing
I'm creating a sudoku generator, using a 'brute-force' randomity approach. I have been able to check the x / y axis for duplicate numbers just fine using the code:
for(l=0; l<9; l++){//Makes all vertical work.
if(sudoku[l][j] == temp){
isUsed=true;
}
}
for(m=0; m<9; m++){//makes all horizontal work
if(sudoku[i][m] == temp){
isUsed=true;
}
}
I decided to implement the 'box' or 'region' checking (whe开发者_开发技巧re you check every 3x3 square from the origin) and I just can't seem to wrap my head around the code. Here's what I've done so far. I just can't quite figure out where my logic error lies (for the record the program will run with this code, but will not check regions properly)
rowbase = i-(i%3);
if(i==2 || i==5 || i==8 ){
if(rowbase == 0 || rowbase == 3 || rowbase == 6){
isUsed= RegionCheck.RegCheck(rowbase, sudoku);
}
}
Contents of regionCheck.java:
boolean okay = false;
int[] regionUsed = new int[9];
int i=0, j=0, regionTester=0, counter=0, numcount;
for (i=regionTester; i<regionTester+3; i++){
for (; j<3; j++){
regionUsed[counter]=sudoku[i][j];
counter++;
}
}
for(i=0; i<9; i++){
numcount=regionUsed[i];
for(j=0; j<9; j++){
if(j==i){
//null
}
else if(numcount == regionUsed[j]){
okay=false;
}
}
}
return okay;
Somewhere along the way I'm just getting lost and not understanding how to 'select' a region and iterate through regions.
Full source here: http://ideone.com/FYLwm
Any help on simply how to 'select' a region for testing and then iterate through it would be greatly appreciated as I'm really out of ideas.
You need to abstract it a bit. Think of it this way, any region (box, column, row) is just a list of values (and empty values). To check whether a value x
can be inserted into region R
, simply represent all the values in R
as a list of values L
. Now all you need to do is to check if L
contains x
Good luck!
I cannot understand what you mean testing a region, I assume test means each region has every number from 1 to 9 without duplication.
We can make may implementations:
- use for loops for vertical, horizontal, and 3x3 regions.
- use table which have location to each region, including horizontal or vertical one.
My recommend is 2nd one. If you have a table, the loop which access regions is implemented once. On the other hand, 1st one requires to implement 3 similar loops for vertical/horizontal/3x3.
Here is a code to generate the table:
for(int i=0, k=0; i<9; i++) {
// generate vertical regions
for(int j=0; j<9; j++)
table[k][j] = new table_t(i, j);
k++;
// generate horizontal regions
for(int j=0; j<9; j++)
table[k][j] = new table_t(j, i);
k++;
// generate 3x3 regions
for(int j=0; j<9; j++)
table[k][j] = new table_t((i/3)*3+j/3, (i%3)*3+j%3);
k++;
}
The code to generate vertical or horizontal regions is easy to read.
Though 3x3 region generation should be described.
The variable i
is taken from 0 to 8, ((i/3)*3
, (i%3)*3
) points the corner of a 3x3 region each. And (+j/3
, +j%3
) moves each box in the region.
And you can test the matrix sudoku
comply or not by following code:
boolean okey = true;
for(int i=0; i<27; i++) {
int [] counter = new int[10];
for(int j=0; i<10; i++)
counter[i]=0;
for(int j=0; j<9; j++)
counter[ sudoku[table[i][j].x][table[i][j].y] ] ++;
boolean ok = true;
for(int j=0; j<9; j++)
if(counter[j+1]!=1)
ok = false;
if(!ok)
okey = false;
}
The array counter
counts number of appearance for each digit
(I assume 0
is some special meaning and digits between 1
and 9
is valid).
精彩评论