数独回溯无效数独

我创建了一个Sudoku Backtracking解算器,它工作正常,但现在我想发出一个错误,如果数独无法解决,因为它是无效的,例如,如果给出这个数独:

http://img5.imageshack.us/img5/2241/sudokugq.jpg

如果不能解决,我该怎么办才能使我的求解方法出错? 我总是最终使用Zeros或陷入循环。

public void solve( int row, int col ) throws Exception { // Throw an exception to stop the process if the puzzle is solved if( row > 8 ){ //Gelöst } // If the cell is not empty, continue with the next cell if( sudo[row][col] != 0 ){ next( row, col ) ; } else { // Find a valid number for the empty cell for( int num = 1; num < 10; num++ ) { if( checkHorizontal(row,num) == false && checkVertikal(col,num)== false&& checkBox(row,col,num)== false ) { sudo[row][col] = num ; // Delegate work on the next cell to a resudosive call next( row, col ) ; } } // No valid number was found, clean up and return to caller sudo[row][col] = 0 ; } } //Ruft solve für das nächste Feld auf public void next( int row, int col ) throws Exception { if( col < 8 ) solve( row, col + 1 ) ; else solve( row + 1, 0 ) ; } 

当你点击sudo[row][col] = 0 ; 代码你刚刚尝试了一个正方形中的每个值,并找不到任何解决方案。 当然,这是你决定放弃无解决状态的地步。

进一步思考 – 我怀疑我几乎是对的。 如果您点击此代码这是您正在尝试的第一个单元格(即您找到的第一个空单元格),那么这就是您的失败时刻。

顺便说一句 – 我不确定使用Exception来表示您在评论中提出的解决方案是个好主意。


现在这正确地拒绝了您发布的电路板 – 请注意,第一行中不仅有两个“3”,第一列中还有两个“5”。 这段代码现在似乎对我有用。 也许你可以尝试一个不可解决的问题。

 public class Test { static final int S = 9; int[][] sudo; public Test() { // Just leave it empty. sudo = new int[S][S]; } public Test(int[][] sudo) { this.sudo = sudo; } // This number should not appear anywhere in the row. public boolean checkHorizontal(int row, int num) { for (int i = 0; i < S; i++) { if (sudo[row][i] == num) { return false; } } return true; } // This number should not appear anywhere in the col. public boolean checkVertical(int col, int num) { for (int i = 0; i < S; i++) { if (sudo[i][col] == num) { return false; } } return true; } // This number should not appear anywhere in the box. private boolean checkBox(int row, int col, int num) { // Round down to nearest 3. int r = (row / 3) * 3; int c = (col / 3) * 3; for (int i = r; i < r + 3; i++) { for (int j = c; j < c + 3; j++) { if (sudo[i][j] == num) { return false; } } } return true; } boolean check(int row, int col, int num) { // All checks must pass. return checkHorizontal(row, num) && checkVertical(col, num) && checkBox(row, col, num); } public boolean solve(int row, int col) { // Got to the end? if (row >= S) { //Gelöst return true; } // If the cell is empty if (sudo[row][col] == 0) { // Find a valid number for the empty cell for (int num = 1; num < 10; num++) { // Can this number be put there? if (check(row, col, num)) { // Yes! sudo[row][col] = num; // Try that. if (next(row, col)) { return true; } } } // Clean up. sudo[row][col] = 0; } else { // Move on. if (next(row, col)) { return true; } } // Failed to find a solution. return false; } //Ruft solve für das nächste Feld auf public boolean next(int row, int col) { if (col < S - 1) { // Step right. return solve(row, col + 1); } else { // Step down. return solve(row + 1, 0); } } public boolean boardOk() { // Initial test to ensure it is a valid array. // Must have that many rows. boolean ok = sudo.length == S; for (int row = 0; ok && row < S; row++) { // Each row must be that long. ok &= sudo[row].length == S; for (int col = 0; ok && col < S; col++) { // Each filled square must be valid. if (sudo[row][col] != 0) { int num = sudo[row][col]; // Remove it. sudo[row][col] = 0; // Check it can be added. ok &= check(row, col, num); // Put it back. sudo[row][col] = num; } } } return ok; } void solve() { if (boardOk()) { boolean solved = solve(0, 0); if (solved) { System.out.println("Solved!"); print(); } } else { System.out.println("Insoluble!"); print(); } } public void print() { for (int i = 0; i < sudo.length; i++) { System.out.println(Arrays.toString(sudo[i])); } } /** * @param args the command line arguments */ public static void main(String[] args) { new Test().solve(); int[][] test = { {0, 0, 6, 5, 8, 3, 3, 2, 7}, {0, 0, 0, 0, 9, 0, 0, 5, 0}, {5, 8, 0, 0, 0, 0, 0, 0, 3}, {0, 3, 1, 0, 4, 0, 5, 0, 0}, {0, 0, 0, 9, 2, 0, 3, 0, 6}, {0, 0, 0, 0, 0, 0, 0, 0, 1}, {3, 4, 2, 0, 0, 6, 9, 1, 5}, {5, 0, 5, 4, 0, 9, 0, 3, 2}, {0, 1, 0, 0, 0, 0, 0, 0, 4},}; new Test(test).solve(); } }