我正在用DFS算法处理16 * 16数独问题。 Java代码的样子:DFS求解数独
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;
}
}
和主要方法是:
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.");
}
当我运行的代码,它经常终止之前的所有空格填满,留下许多-1难题。我不确定问题出在哪里。我将非常感谢任何帮助!
您的意思是[深度优先搜索]而不是[dfs]? –
是的,深度优先搜索 – HarryTao
然后你应该调整问题的标签。 –