C/C++教程

Leetcode.面试题 08.12. 八皇后__DFS+回溯

本文主要是介绍Leetcode.面试题 08.12. 八皇后__DFS+回溯,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

面试题 08.12. 八皇后

设计一种算法,打印 N 皇后在 N × N 棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。这里的“对角线”指的是所有的对角线,不只是平分整个棋盘的那两条对角线。

注意:本题相对原题做了扩展

示例:

 输入:4
 输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

Reflect:

我们分为几个步骤即可;

  1. 第一个皇后先放第一行第一列
  2. 第二个皇后放在第二行第一列、然后判断是否OK, 如果不OK,继续放在第二列、第三列、依次把所有列都放完,找到一个合适
  3. 继续第三个皇后,还是第一列、第二列……直到第N个皇后也能放在一个不冲突的位置,算是找到了一个正确解;
  4. 当得到一个正确解时,在栈回退到上一个栈时,就会开始回溯,即将第一个皇后,放到第一列的所有正确解,全部得到.
  5. 然后回头继续第一个皇后放第二列,后面继续循环执行 1,2,3,4的步骤

这里使用一个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;
    }
}
这篇关于Leetcode.面试题 08.12. 八皇后__DFS+回溯的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!