设计一种算法,打印 N 皇后在 N × N 棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。这里的“对角线”指的是所有的对角线,不只是平分整个棋盘的那两条对角线。
注意:本题相对原题做了扩展
示例: 输入:4 输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释: 4 皇后问题存在如下两个不同的解法。 [ [".Q..", // 解法 1 "...Q", "Q...", "..Q."], ["..Q.", // 解法 2 "Q...", "...Q", ".Q.."] ]
Reflect:
我们分为几个步骤即可;
这里使用一个loca一维数组来保存所放置的皇后的列的位置,其行的位置我们用一维数组的下标充当;
Code:
class Solution { public List<List<String>> solveNQueens(int n) { int[] loca = new int[n]; List<List<String>> list = new ArrayList<>(); check(n,loca,0,list); //0代表第一个皇后 return list; } //放置皇后的方法 public void check(int n,int[] loca,int curN,List<List<String>> list){ if(curN == n){ //当curN为n时,即所有的皇后都摆好了 list.add(toStringList(loca)); return; } for(int i=0;i<n;i++){ loca[curN] = i; //先假设可以放 if(judge(curN,loca)){ //判断是否成功 check(n,loca,curN+1,list); //成功则放下一个 } //不成功的话按道理应该回溯,但由于下一次for会对其重新赋值所以省去了回溯 /*且我们是假设可以放,如果成功,我们会一直压栈的进行搜索直到找到一种解法然后输出; 如果不成功,其便不会再进行下一次放置了,因此会直接断了压栈的过程, 且其本身对loca的修改也会随着for循环的移动而自身产生回溯操作。 */ } } //判断是否可以放的方法 public boolean judge(int curN,int[] loca){ for(int i=0;i<curN;i++){ //即不能在同一行同一列同一斜线,由于我们放置的时候就已经控制了不在同一行了,因此不用考虑行了 //第一个条件来判断是否同一列, 第二个条件是根据棋盘的实际位置分析得到,即相差几个皇后,则列的位置就相差几 if(loca[i] == loca[curN] || Math.abs(loca[i]-loca[curN]) == Math.abs(curN-i)){ return false; } } return true; } //将数组保存的位置转换为list的形式返回 public List<String> toStringList(int[] loca){ List<String> list = new ArrayList<>(); for(int i=0;i<loca.length;i++){ String s = ""; for(int j=0;j<loca.length;j++){ if(j==loca[i]){ s+="Q"; } else{ s+="."; } } list.add(s); } return list; } }