leetcode 51. N-Queens DFS深度优先遍历

墨蓝 2022-06-09 10:42 194阅读 0赞

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.  
![这里写图片描述][SouthEast]

Given an integer n, return all distinct solutions to the n-queens puzzle.  
Each solution contains a distinct board configuration of the n-queens’ placement, where ‘Q’ and ‘.’ both indicate a queen and an empty space respectively.  
For example,  
There exist two distinct solutions to the 4-queens puzzle:  
\[  
\[“.Q..”, // Solution 1  
“…Q”,  
“Q…”,  
“..Q.”\],

\[“..Q.”, // Solution 2  
“Q…”,  
“…Q”,  
“.Q..”\]  
\]

这个是一个很经典的问题：八皇后，不过这里换成了N皇后，解决方法是一样的，DFS深度优先遍历，就是不断的尝试一个一个可能的解。

代码如下：

import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    public class Solution 
    {
        
        /*
         * 这个是N皇后问题，是八皇后的一个小的变种，递归遍历，最简单
         * 需要一个数字记录每一个N皇后的solution，大小为n
         * index[i]=j 表示在i行j列放置皇后
         * */
        int []index;
        List<List<String>> res=new ArrayList<List<String>>();
        public List<List<String>> solveNQueens(int n)
        {
            //特殊情况处理
            if(n<=0)
                return res;
            index=new int[n];
            Arrays.fill(index, -1);
            NQuees(0,n);
            return res;
        }
    
        public void NQuees(int k, int n) 
        {
            if(k==n)
            {
                List<String> one=new ArrayList<>();
                for(int i=0;i<n;i++)
                {
                    StringBuilder builder=new StringBuilder();
                    for(int j=0;j<n;j++)
                    {
                        if(index[i]==j)
                            builder.append("Q");
                        else
                            builder.append(".");
                    }
                    one.add(builder.toString());
                }
                res.add(one);
                return ;
    
            }else
            {
                //在i到n列中依次尝试所有的可能解
                for(int i=0;i<n;i++)
                {
                    //这个是为了判断k行i列是否可以放置皇后
                    if(vaild(k,i))
                    {
                        index[k]=i;
                        NQuees(k+1, n);
                    }
                }
            }
    
        }
    
        /*
         * 判断在row行和col列处是否可以放置皇后
         * */
        private boolean vaild(int row, int col)
        {
            for(int i=0;i<row;i++)
            {
                //只要判断是否同一列，同一行，是否在正对角线，还是斜对角线上就可以了
                if(row==i || col==index[i] || Math.abs(row-i)==Math.abs(index[i]-col))
                    return false;
            }
            return true;
        }
    }

下面是C++的做法，这个问题是我在学习C++程序设计的时候遇到的一个问题，一开始一直搞不清楚怎么做，后来才明白这个是通过DFS深度优先遍历做的，很值得学习

代码如下：

#include <iostream>
    #include <vector>
    #include <string>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        vector<vector<string>> res;
        int* record;
        vector<vector<string>> solveNQueens(int n) 
        {
            record = new int[n];
            dfs(0, n);
            return res;
        }
    
        bool isVaild(int row,int col)
        {
            for (int i = 0; i < row; i++)
            {
                if (record[i] == col || i == row || abs(col-record[i])==abs(row-i) )
                    return false;
            }
            return true;
        }
    
        void dfs(int row, int size)
        {
            if (row == size)
            {
                vector<string> one;
                for (int i = 0; i < size; i++)
                {
                    string tmp = "";
                    for (int j = 0; j < size; j++)
                    {
                        if (record[i] == j)
                            tmp += "Q";
                        else
                            tmp += ".";
                    }
                    one.push_back(tmp);
                }
                res.push_back(one);
                return;
            }
            else
            {
                for (int i = 0; i < size; i++)
                {
                    if (isVaild(row, i))
                    {
                        record[row] = i;
                        dfs(row + 1, size);
                    }
                }
            }
        }
    };

[SouthEast]: /images/20220609/b9a5b63c1f9a4eba94d599bcc341d534.png