1 year ago

#215914

test-img

Tina

Trying to solve N Queen by backtracking but returns nothing Java

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!

java

algorithm

recursion

backtracking

n-queens

0 Answers

Your Answer

Accepted video resources