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 (where 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.

回答1:

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:

1. use for loops for vertical, horizontal, and 3x3 regions.
2. 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).

回答2:

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!