当前位置： 文江博客话题详情

使用递归和回溯的数独求解器

发布于 2025-01-09 06:36:44 字数 1976 浏览 4 评论 0原文

我正在尝试使用 Java 实现数独求解器。这是我现在编写的代码。如果我尝试运行它，它会进入无限循环，继续打印数独板的第一行，并且解决方案也不正确。我想我在这里实施回溯的方式不正确。我想我打印的是最后的也是错误的，因为每次只打印第一行。有人可以帮我修复我的代码并告诉我哪里出了问题吗？

public static void display(int[][] board) {
    for(int[] arr : board) {
        System.out.println(Arrays.toString(arr));
        return;
    }
}

public static boolean isSafe(int[][] board, int row, int col, int i) {
    //check row
    for(int a=0; a<board.length; a++) {
        if(board[a][col]==i) {
            return false;
        }
    }
    //check col
    for(int b=0; b<board.length; b++) {
        if(board[row][b]==i) {
            return false;
        }
    }
    //check cell
    int strow = row-(row%3);
    int stcol = col-(col%3);
    
    for(int x=strow; x<strow+3; x++) {
        for(int y=stcol; y<stcol+3; y++) {
            if(board[x][y]==i) {
                return false;
            }
        }
    }
    return true;
}

public static void sudoku(int[][] board, int row, int col) {
    if(row==board.length) {
        display(board);
        System.out.println();
        return; //modify this to print ans
    }
    if(col==board.length) {
        sudoku(board, row+1, 0);
        return;
    }
    if(board[row][col]==0) {
        for(int i=1; i<=9; i++) {
            if(isSafe(board, row, col, i)) {
                board[row][col]=i;
                sudoku(board, row, col+1);
                board[row][col]=0;
            }
        }
    }
    sudoku(board, row, col+1);
}

public static void main(String args[]) {
    int[][] board= 
           { {3, 0, 6, 5, 0, 8, 4, 0, 0}, 
             {5, 2, 0, 0, 0, 0, 0, 0, 0}, 
             {0, 8, 7, 0, 0, 0, 0, 3, 1}, 
             {0, 0, 3, 0, 1, 0, 0, 8, 0}, 
             {9, 0, 0, 8, 6, 3, 0, 0, 5}, 
             {0, 5, 0, 0, 9, 0, 6, 0, 0}, 
             {1, 3, 0, 0, 0, 0, 2, 5, 0}, 
             {0, 0, 0, 0, 0, 0, 0, 7, 4}, 
             {0, 0, 5, 2, 0, 6, 3, 0, 0} };
    sudoku(board, 0, 0);
}
原文

I am trying to implement a Sudoku solver using Java. This is the code I've written as of now. If I try to run it, it goes on to an endless loop that keeps on printing the first row of the Sudoku board, and that too with an incorrect solution. I guess I'm implementing backtracking the incorrect way over here. I think I am printing the final and wrong as well, as only the first row is printed every time. Can someone please help me fix my code and tell me as to where I am going wrong?

public static void display(int[][] board) {
    for(int[] arr : board) {
        System.out.println(Arrays.toString(arr));
        return;
    }
}

public static boolean isSafe(int[][] board, int row, int col, int i) {
    //check row
    for(int a=0; a<board.length; a++) {
        if(board[a][col]==i) {
            return false;
        }
    }
    //check col
    for(int b=0; b<board.length; b++) {
        if(board[row][b]==i) {
            return false;
        }
    }
    //check cell
    int strow = row-(row%3);
    int stcol = col-(col%3);
    
    for(int x=strow; x<strow+3; x++) {
        for(int y=stcol; y<stcol+3; y++) {
            if(board[x][y]==i) {
                return false;
            }
        }
    }
    return true;
}

public static void sudoku(int[][] board, int row, int col) {
    if(row==board.length) {
        display(board);
        System.out.println();
        return; //modify this to print ans
    }
    if(col==board.length) {
        sudoku(board, row+1, 0);
        return;
    }
    if(board[row][col]==0) {
        for(int i=1; i<=9; i++) {
            if(isSafe(board, row, col, i)) {
                board[row][col]=i;
                sudoku(board, row, col+1);
                board[row][col]=0;
            }
        }
    }
    sudoku(board, row, col+1);
}

public static void main(String args[]) {
    int[][] board= 
           { {3, 0, 6, 5, 0, 8, 4, 0, 0}, 
             {5, 2, 0, 0, 0, 0, 0, 0, 0}, 
             {0, 8, 7, 0, 0, 0, 0, 3, 1}, 
             {0, 0, 3, 0, 1, 0, 0, 8, 0}, 
             {9, 0, 0, 8, 6, 3, 0, 0, 5}, 
             {0, 5, 0, 0, 9, 0, 6, 0, 0}, 
             {1, 3, 0, 0, 0, 0, 2, 5, 0}, 
             {0, 0, 0, 0, 0, 0, 0, 7, 4}, 
             {0, 0, 5, 2, 0, 6, 3, 0, 0} };
    sudoku(board, 0, 0);
}

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（1）

烟─花易冷 2025-01-16 06:36:44

此处可以应用回溯算法，问题发生在您的数独方法中。
首先，我们可以只通过棋盘，而不想通过行和列。
我们可以直接通过棋盘并遍历每个单元格。
只考虑那些为 0 的单元格。
我们不想考虑任何其他单元格，因为 0" 是我们感兴趣的单元格。
现在，如果我们看到一个单元格为 0，我们会尝试找到适合该单元格的从 1 到 9 的所有不同可能性，并应用“isSafe()”逻辑，该逻辑将执行相同的检查。
我们回溯并继续检查。

public static void display(int[][] board) {
    for(int[] arr : board) {
        System.out.println(Arrays.toString(arr));
    }
}

public static boolean isSafe(int[][] board, int row, int col, int i) {
    //check row
    for(int a=0; a<board.length; a++) {
        if(board[a][col]==i) {
            return false;
        }
    }
    //check col
    for(int b=0; b<board.length; b++) {
        if(board[row][b]==i) {
            return false;
        }
    }
    //check cell
    int strow = row-(row%3);
    int stcol = col-(col%3);
    
    for(int x=strow; x<strow+3; x++) {
        for(int y=stcol; y<stcol+3; y++) {
            if(board[x][y]==i) {
                return false;
            }
        }
    }
    return true;
}

public static boolean sudoku(int [][] board) {
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                int current = board[i][j];
                if (current == 0) {
                    for (int ch = 1; ch <= 9; ch++) {
                        if (isSafe(board, i, j, ch)) {
                            board[i][j] = ch;
                            if (sudoku(board)) {
                                return true;
                            }
                            board[i][j] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
public static void main(String args[]) {
    int[][] board= 
           { {3, 0, 6, 5, 0, 8, 4, 0, 0}, 
             {5, 2, 0, 0, 0, 0, 0, 0, 0}, 
             {0, 8, 7, 0, 0, 0, 0, 3, 1}, 
             {0, 0, 3, 0, 1, 0, 0, 8, 0}, 
             {9, 0, 0, 8, 6, 3, 0, 0, 5}, 
             {0, 5, 0, 0, 9, 0, 6, 0, 0}, 
             {1, 3, 0, 0, 0, 0, 2, 5, 0}, 
             {0, 0, 0, 0, 0, 0, 0, 7, 4}, 
             {0, 0, 5, 2, 0, 6, 3, 0, 0} };
    sudoku(board);
    display(board);
    
    }

以下是更改后的输出

[3, 1, 6, 5, 7, 8, 4, 9, 2]
[5, 2, 9, 1, 3, 4, 7, 6, 8]
[4, 8, 7, 6, 2, 9, 5, 3, 1]
[2, 6, 3, 4, 1, 5, 9, 8, 7]
[9, 7, 4, 8, 6, 3, 1, 2, 5]
[8, 5, 1, 7, 9, 2, 6, 4, 3]
[1, 3, 8, 9, 4, 7, 2, 5, 6]
[6, 9, 2, 3, 5, 1, 8, 7, 4]
[7, 4, 5, 2, 8, 6, 3, 1, 9]

注意：我将返回类型更改为 true 或 false，以确保特定单元格可以填充数字 x。如果可能，我们返回 true 并继续处理下一个为 0 的单元格，否则我们回溯并检查其他可能性。

更新：
您缺少的唯一更改是最后的 else 块，因为即使单元格为 0 或任何其他数字，您也在执行递归 sudoku(board, row, col+1);。因此，只需将该语句包含在 else 块中即可给出所需的输出。

代码更改而不更改返回类型：

public static void display(int[][] board) {
    for(int[] arr : board) {
        System.out.println(Arrays.toString(arr));
    }
}

public static boolean isSafe(int[][] board, int row, int col, int i) {
    //check row
    for(int a=0; a<board.length; a++) {
        if(board[a][col]==i) {
            return false;
        }
    }
    //check col
    for(int b=0; b<board.length; b++) {
        if(board[row][b]==i) {
            return false;
        }
    }
    //check cell
    int strow = row-(row%3);
    int stcol = col-(col%3);
    
    for(int x=strow; x<strow+3; x++) {
        for(int y=stcol; y<stcol+3; y++) {
            if(board[x][y]==i) {
                return false;
            }
        }
    }
    return true;
}

public static void sudoku(int[][] board, int row, int col) {
    if(row==board.length) {
        display(board);
        System.out.println();
        return; //modify this to print ans
    }
    if(col==board.length) {
        sudoku(board, row+1, 0);
        return;
    }
    if(board[row][col]==0) {
        for(int i=1; i<=9; i++) {
            if(isSafe(board, row, col, i)) {
                board[row][col]=i;
                sudoku(board, row, col+1);
                board[row][col]=0;
            }
        }
    }
    else
        sudoku(board, row, col+1);
}
public static void main(String args[]) {
    int[][] board= 
           { {3, 0, 6, 5, 0, 8, 4, 0, 0}, 
             {5, 2, 0, 0, 0, 0, 0, 0, 0}, 
             {0, 8, 7, 0, 0, 0, 0, 3, 1}, 
             {0, 0, 3, 0, 1, 0, 0, 8, 0}, 
             {9, 0, 0, 8, 6, 3, 0, 0, 5}, 
             {0, 5, 0, 0, 9, 0, 6, 0, 0}, 
             {1, 3, 0, 0, 0, 0, 2, 5, 0}, 
             {0, 0, 0, 0, 0, 0, 0, 7, 4}, 
             {0, 0, 5, 2, 0, 6, 3, 0, 0} };
    sudoku(board, 0, 0);
    
    }

输出：

[3, 1, 6, 5, 7, 8, 4, 9, 2]
[5, 2, 9, 1, 3, 4, 7, 6, 8]
[4, 8, 7, 6, 2, 9, 5, 3, 1]
[2, 6, 3, 4, 1, 5, 9, 8, 7]
[9, 7, 4, 8, 6, 3, 1, 2, 5]
[8, 5, 1, 7, 9, 2, 6, 4, 3]
[1, 3, 8, 9, 4, 7, 2, 5, 6]
[6, 9, 2, 3, 5, 1, 8, 7, 4]
[7, 4, 5, 2, 8, 6, 3, 1, 9]

A bactracking algorithm can be applied here and the problem happens in your sudoku method.
First of all we can just pass the board and we don't want to pass the row and col.
We can just pass the board and the just traverse through each and every cell.
Only consider those cells that are 0's.
We don't want to consider any other cells as 0"s are the cells we are interested in.
Now if we see a cell which is 0, we try to find all the different possibilites from 1 to 9 which can fit in that cell and apply the 'isSafe()` logic which will just do the same check.
And we backtrack and continue with our checking.

public static void display(int[][] board) {
    for(int[] arr : board) {
        System.out.println(Arrays.toString(arr));
    }
}

public static boolean isSafe(int[][] board, int row, int col, int i) {
    //check row
    for(int a=0; a<board.length; a++) {
        if(board[a][col]==i) {
            return false;
        }
    }
    //check col
    for(int b=0; b<board.length; b++) {
        if(board[row][b]==i) {
            return false;
        }
    }
    //check cell
    int strow = row-(row%3);
    int stcol = col-(col%3);
    
    for(int x=strow; x<strow+3; x++) {
        for(int y=stcol; y<stcol+3; y++) {
            if(board[x][y]==i) {
                return false;
            }
        }
    }
    return true;
}

public static boolean sudoku(int [][] board) {
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                int current = board[i][j];
                if (current == 0) {
                    for (int ch = 1; ch <= 9; ch++) {
                        if (isSafe(board, i, j, ch)) {
                            board[i][j] = ch;
                            if (sudoku(board)) {
                                return true;
                            }
                            board[i][j] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
public static void main(String args[]) {
    int[][] board= 
           { {3, 0, 6, 5, 0, 8, 4, 0, 0}, 
             {5, 2, 0, 0, 0, 0, 0, 0, 0}, 
             {0, 8, 7, 0, 0, 0, 0, 3, 1}, 
             {0, 0, 3, 0, 1, 0, 0, 8, 0}, 
             {9, 0, 0, 8, 6, 3, 0, 0, 5}, 
             {0, 5, 0, 0, 9, 0, 6, 0, 0}, 
             {1, 3, 0, 0, 0, 0, 2, 5, 0}, 
             {0, 0, 0, 0, 0, 0, 0, 7, 4}, 
             {0, 0, 5, 2, 0, 6, 3, 0, 0} };
    sudoku(board);
    display(board);
    
    }

Here is the output after the change

[3, 1, 6, 5, 7, 8, 4, 9, 2]
[5, 2, 9, 1, 3, 4, 7, 6, 8]
[4, 8, 7, 6, 2, 9, 5, 3, 1]
[2, 6, 3, 4, 1, 5, 9, 8, 7]
[9, 7, 4, 8, 6, 3, 1, 2, 5]
[8, 5, 1, 7, 9, 2, 6, 4, 3]
[1, 3, 8, 9, 4, 7, 2, 5, 6]
[6, 9, 2, 3, 5, 1, 8, 7, 4]
[7, 4, 5, 2, 8, 6, 3, 1, 9]

Note : I changed the return type to true or false inorder to make sure that a particular cell can be filled with a number say x. If its possible we return true and continue with the next cell which is 0, other wise we backtrack and check for other possibilities.

Updates :
The only change you are missing is an else block at the very end because even if the cell is 0 or any other number you are doing recursion sudoku(board, row, col+1);. So just enclose that statement in the else block and will give the desired output.

Code change without changing the return type:

public static void display(int[][] board) {
    for(int[] arr : board) {
        System.out.println(Arrays.toString(arr));
    }
}

public static boolean isSafe(int[][] board, int row, int col, int i) {
    //check row
    for(int a=0; a<board.length; a++) {
        if(board[a][col]==i) {
            return false;
        }
    }
    //check col
    for(int b=0; b<board.length; b++) {
        if(board[row][b]==i) {
            return false;
        }
    }
    //check cell
    int strow = row-(row%3);
    int stcol = col-(col%3);
    
    for(int x=strow; x<strow+3; x++) {
        for(int y=stcol; y<stcol+3; y++) {
            if(board[x][y]==i) {
                return false;
            }
        }
    }
    return true;
}

public static void sudoku(int[][] board, int row, int col) {
    if(row==board.length) {
        display(board);
        System.out.println();
        return; //modify this to print ans
    }
    if(col==board.length) {
        sudoku(board, row+1, 0);
        return;
    }
    if(board[row][col]==0) {
        for(int i=1; i<=9; i++) {
            if(isSafe(board, row, col, i)) {
                board[row][col]=i;
                sudoku(board, row, col+1);
                board[row][col]=0;
            }
        }
    }
    else
        sudoku(board, row, col+1);
}
public static void main(String args[]) {
    int[][] board= 
           { {3, 0, 6, 5, 0, 8, 4, 0, 0}, 
             {5, 2, 0, 0, 0, 0, 0, 0, 0}, 
             {0, 8, 7, 0, 0, 0, 0, 3, 1}, 
             {0, 0, 3, 0, 1, 0, 0, 8, 0}, 
             {9, 0, 0, 8, 6, 3, 0, 0, 5}, 
             {0, 5, 0, 0, 9, 0, 6, 0, 0}, 
             {1, 3, 0, 0, 0, 0, 2, 5, 0}, 
             {0, 0, 0, 0, 0, 0, 0, 7, 4}, 
             {0, 0, 5, 2, 0, 6, 3, 0, 0} };
    sudoku(board, 0, 0);
    
    }

Output :

[3, 1, 6, 5, 7, 8, 4, 9, 2]
[5, 2, 9, 1, 3, 4, 7, 6, 8]
[4, 8, 7, 6, 2, 9, 5, 3, 1]
[2, 6, 3, 4, 1, 5, 9, 8, 7]
[9, 7, 4, 8, 6, 3, 1, 2, 5]
[8, 5, 1, 7, 9, 2, 6, 4, 3]
[1, 3, 8, 9, 4, 7, 2, 5, 6]
[6, 9, 2, 3, 5, 1, 8, 7, 4]
[7, 4, 5, 2, 8, 6, 3, 1, 9]
回复 原文
~没有更多了~

关于作者

你与昨日

暂无简介

文章
评论
25 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

╰ゝ天使的微笑

文章 0 评论 0

少女净妖师

文章 0 评论 0

朱洁

文章 0 评论 0

觉浅

文章 0 评论 0

滥情空心

文章 0 评论 0

hl1314520

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文