问题描述:

I'm working on 16*16 sudoku problem with DFS algorithm. Java code looks like:

 public class dfs {

public boolean dfs(int[][] puzzle,int i,int j){

if(i==15&&j>=16) return true;

if(j==16){

//System.out.println(String.valueOf(i));

return dfs(puzzle,i+1,0); //{j=0; i++;

}

if(puzzle[i][j]!=-1){

return dfs(puzzle,i,j+1); //next cell in the same row

}

else{

for(int num=1;num<=16;num++){

//System.out.println("trying"+i+","+j+","+num);

if(valid(puzzle,i,j,num)){

//System.out.println(String.valueOf(num));

puzzle[i][j]=num;

if(dfs(puzzle,i,j+1)){

return true;

}

}

//else return false;

}

}

return false;

}

public boolean valid(int[][] puzzle,int x,int y,int num){

for(int i=0;i<16;i++){

if(puzzle[i][y]==num) {

//System.out.println("a");

return false;

}

}

for(int j=0;j<16;j++){

if(puzzle[x][j]==num){

//System.out.println("b");

return false;

}

}

int c=(x/4)*4;

int r=(y/4)*4;

for(int i=0;i<4;i++){

for(int j=0;j<4;j++){

if(puzzle[c+i][r+j]==num){

//System.out.println("c");

return false;

}

}

}

return true;

}

}

And the main method is:

 public static void main(String[] args) {

sudoku sudokuPuzzleGenerator = new sudoku();

long start = System.currentTimeMillis();

int numOfSudokuMatrix = 1;

List<int[][]> sudoku = new ArrayList<int[][]>();

for (int count = 1; count <= numOfSudokuMatrix; count++) {

int[][] randomMatrix = sudokuPuzzleGenerator.generatePuzzleMatrix();

int hole = 81;

while (hole > 0) {

Random randomGenerator = new Random();

int x = randomGenerator.nextInt(16);

int y = randomGenerator.nextInt(16);

if (randomMatrix[x][y] != -1) {

randomMatrix[x][y] = -1;

hole--;

}

}

for(int i=0;i<16;i++){

for(int j=0;j<16;j++){

System.out.print(randomMatrix[i][j] + " ");

}

System.out.println();

}

sudoku.add(randomMatrix);

}

System.out.println();

long start2 = System.currentTimeMillis();

for (int[][] p:sudoku) {

dfs d=new dfs();

boolean b=d.dfs(p,0,0);

for (int rowNum = 0; rowNum < 16; rowNum++) {

for (int colNum = 0; colNum < 16; colNum++) {

System.out.print(p[rowNum][colNum] + " ");

}

System.out.println();

}

}

Long end2 = System.currentTimeMillis();

Long time2 = end2 - start2;

System.out.println("It took: " + time2 + " milliseconds.");

}

When I run the code, it often terminates before all blank spaces be filled, leaving many -1 in the puzzle. I'm not sure where the problem is. I will be really thankful for any help!

网友答案:

It doesn't matter, but this would probably be classified as a backtracking problem, not a search. Anyway, I think this is it, but it's hard to test without that generatePuzzleMatrix method. After you check every possible number at a given cell, if you don't find an answer (hit your base case), you need to set the cell back to -1.

for(int num=1;num<=16;num++){
    if(valid(puzzle,i,j,num)){
        puzzle[i][j]=num;
        if(dfs(puzzle,i,j+1)){
            return true;
        }
    }
}
puzzle[i][j] = -1;

Without setting this value back to -1, you are going to leave these values set as the highest valid value, even if you didn't find an answer. Future iterations of your recursive algorithm will skip that value because they assume it is correct. Thus, your loop will end without testing all possibilities and finding an answer. Hope this does it for ya.

Comment Response

Yes, I agree there is at least 1 solution. I believe the problem is that your loop is ending before you actually test all possibilities. Your recursive calls need to set the grid back once they have tested every possibility. At an arbitrary depth in the recursive stack, say you add a valid number to your grid. The number being valid at that stage does not imply it is in the right position. You could create a ripple effect. Though it is currently valid for that particular number, you have unintentionally elimanted the possibility of any solution based on the cells you have filled so far. Once you hit that scenario, you have a problem. Your grid will retain the most recently set value, and you will never try setting it to anything else (because you have a condition that ignores values != -1).

相关阅读:
Top