0

我花了很多时间思考一种方法来实现基于回溯的数独求解算法。但是，我遇到了一个问题——算法一旦出错就不会回溯。为了使事情尽可能简单，这是我的主要功能：

public class Sudoku {
    private int[][] grid = new int[9][9];
    private int col;
    private int row;

    public boolean solveSudoku() {
        if(!(this.FindEmptyCell())) {
            return true;
        }

        for(int num = 1; num <= 9; num++) {
            if(this.isPossible(this.col, this.row, num)) {
                this.grid[this.col][this.row] = num;
                if(this.solveSudoku()) {
                    return true;
                }
                this.grid[col][row] = 0;
            }
        }
        return false;
    }
}

数独类的构造函数创建一个空棋盘，然后计算机必须用满足数独规则的数字填充整个网格。
FindEmptyCell 方法将字段行和列的值设置为等于第一个未占用单元格的索引。这个网格代表我的程序返回 false 时的状态：

1 2 3 4 5 6 7 8 9 
4 5 6 1 2 3 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0


请你告诉我，到目前为止，我的算法是否一切都正确？如果是这样，那就意味着错误出在辅助功能的某个地方。例如，我不知道使用字段来存储索引是否不会阻止回溯。
任何帮助，将不胜感激。另外，如果这篇文章在某种程度上违反了这个委员会的规则，请在投票前在评论中告诉我——我希望以后避免这些错误。



编辑：提供剩余的方法：

public Sudoku() {
    for(int i = 0; i < 9; i++) {
        for(int j = 0; j < 9; j++) {
            grid[i][j] = 0;
        }
    }
}

public boolean FindEmptyCell(int col, int row) {
    for(col = 0; col < 9; col++) {
        for(row = 0; row < 9; row++) {
            if(this.grid[col][row] == 0) {
                return true;
            }
        }
    }
    return false;
}

public boolean usedInRow(int row, int num) {
    for(int col = 0; col < 9; col++) {
        if(grid[col][this.row] == num) {
            return true;
        }
    }
    return false;
}

public boolean usedInColumn(int col, int num) {
    for(int row = 0; row < 9; row++) {
        if(grid[this.col][row] == num) {
            return true;
        }
    }
    return false;
}

public boolean usedInBox(int boxStartRow, int boxStartCol, int num) {
    for(int col = 0; col < 3; col++) {
        for(int row = 0; row < 3; row++) {
            if(grid[col+boxStartCol][row + boxStartRow] == num) {
                return true;
            }
        }
    }
    return false;
}

public boolean isPossible(int col, int row, int number) {
    return !(this.usedInRow(this.row, number)) && !this.usedInColumn(this.col, number) && !this.usedInBox(row - row%3, col-col%3, number);
}
4

0 回答 0