設計一種算法,打印 N 皇后在 N × N 棋盤上的各種擺法,其中每個皇后都不同行、不同列,也不在對角線上。這里的“對角線”指的是所有的對角線,不只是平分整個棋盤的那兩條對角線。
注意:本題相對原題做了擴展
示例:
輸入:4
輸出:[[".Q…","…Q",“Q…”,"…Q."],["…Q.",“Q…”,"…Q",".Q…"]]
解釋: 4 皇后問題存在如下兩個不同的解法。
[
[".Q…", // 解法 1
“…Q”,
“Q…”,
“…Q.”],
["…Q.", // 解法 2
“Q…”,
“…Q”,
“.Q…”]
]
代碼
class Solution {List<List<String>> cList=new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] chars=new char[n][n];for(int i=0;i<n;i++)Arrays.fill(chars[i],'.');//全部都沒放皇后solveNQ(n,chars,0);return cList;}public void solveNQ(int n,char[][] chars,int row) {if(row==n)//返回結果{List<String> temp=new ArrayList<>();for(int i=0;i<n;i++){temp.add(String.valueOf(chars[i]));}cList.add(temp);return;}for(int i=0;i<n;i++)//選擇列{if(isOk(i,chars,row)){chars[row][i]='Q';solveNQ(n,chars,row+1);//下一行chars[row][i]='.';//回溯}}}public boolean isOk(int col,char[][] chars,int row) {//檢查位置是否合法for(int i=row-1;i>=0;i--){if(chars[i][col]=='Q')return false;if(col+row-i<chars.length&&chars[i][col+row-i]=='Q')return false;if(col-row+i>=0&&chars[i][col-row+i]=='Q')return false;}return true;}
}