尝试通过回溯来解决 N Queen 但没有返回 Java
我参考了某人用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 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论