尝试通过回溯来解决 N Queen 但没有返回 Java

发布于 2025-01-09 10:52:12 字数 1935 浏览 0 评论 0原文

我参考了某人用C编写的N Queen的回溯代码,并尝试用Java实现它,但我一直得到空输出。

下面是我编写的代码(isValid 用于检查在棋盘上放置皇后的有效性):

class Queen {
    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }
    public static List<List<String>> solveNQueens(int n) {
        StringBuilder sb=new StringBuilder(n);
        List<StringBuilder> board=new ArrayList<StringBuilder>();
        List<List<String>> res=new ArrayList<List<String>>();
        for(int i=0;i<n;i++){
            sb.append(".");
        }
        for(int i=0;i<n;i++){
            board.add(sb);
        }
        backtrack(board,n,0,res);
        return res;
    }
    public static void backtrack(List<StringBuilder> board,int n, int row,List<List<String>> res){
        if(row==n){
            List<String> cur=new ArrayList<String>();
            for(int i=0;i<n;i++){
                cur.add(board.get(i).toString());
            }
            res.add(cur);
            return;
        }
        for(int col=0;col<n;col++){
            if(!isValid(board, row, col, n)){
                continue;
            }
            board.get(row).setCharAt(col, 'Q');
            backtrack(board,n,row+1,res);
            board.get(row).setCharAt(col, '.');
        }

    }
    public static Boolean isValid(List<StringBuilder> board,int row,int col,int n){
        for(int i=0;i<n;i++){
            if(board.get(i).charAt(col)=='Q') return false;
        }
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(board.get(i).charAt(j)=='Q') return false;
        }
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(board.get(i).charAt(j)=='Q') return false;
        }
        return true;
    }
}

我主要关心的是我是否使用回溯并正确返回了列表。我想知道我是否犯了一些愚蠢的错误或者没有很好地理解算法。请帮我找出问题所在。提前非常感谢!

I referred to someone's backtracking code of N Queen in C and tried to implement it in Java, but I kept getting empty output.

Below is the code I wrote (isValid is for checking the validity of placing a queen on the board):

class Queen {
    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }
    public static List<List<String>> solveNQueens(int n) {
        StringBuilder sb=new StringBuilder(n);
        List<StringBuilder> board=new ArrayList<StringBuilder>();
        List<List<String>> res=new ArrayList<List<String>>();
        for(int i=0;i<n;i++){
            sb.append(".");
        }
        for(int i=0;i<n;i++){
            board.add(sb);
        }
        backtrack(board,n,0,res);
        return res;
    }
    public static void backtrack(List<StringBuilder> board,int n, int row,List<List<String>> res){
        if(row==n){
            List<String> cur=new ArrayList<String>();
            for(int i=0;i<n;i++){
                cur.add(board.get(i).toString());
            }
            res.add(cur);
            return;
        }
        for(int col=0;col<n;col++){
            if(!isValid(board, row, col, n)){
                continue;
            }
            board.get(row).setCharAt(col, 'Q');
            backtrack(board,n,row+1,res);
            board.get(row).setCharAt(col, '.');
        }

    }
    public static Boolean isValid(List<StringBuilder> board,int row,int col,int n){
        for(int i=0;i<n;i++){
            if(board.get(i).charAt(col)=='Q') return false;
        }
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(board.get(i).charAt(j)=='Q') return false;
        }
        for(int i=row-1,j=col+1;i>=0&&j<n;i--,j++){
            if(board.get(i).charAt(j)=='Q') return false;
        }
        return true;
    }
}

My main concern is if I used backtracking and returned the List correctly. I wonder if I made some silly mistake or did not understand the algorithm well. Please help me find what's the issue. Thank you so much in advance!

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

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

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文