1 year ago
#215914
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