首页 > 搜索 > DFS搜索 > LeetCode-N-Queens[DFS]
2014
11-18

LeetCode-N-Queens[DFS]

N-Queens

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

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.."]
]

标签: Backtracking
分析

经典的深搜题。

代码1

// LeetCode, N-Queens
// 深搜+剪枝
// 时间复杂度O(n!),空间复杂度O(n)
class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        this->columns = vector<int>(n, 0);
        this->main_diag = vector<int>(2 * n, 0);
        this->anti_diag = vector<int>(2 * n, 0);

        vector<vector<string> > result;
        vector<int> C(n, 0);  // C[i]表示第i行皇后所在的列编号
        dfs(C, result, 0);
        return result;
    }
private:
    // 这三个变量用于剪枝
    vector<int> columns;  // 表示已经放置的皇后占据了哪些列
    vector<int> main_diag;  // 占据了哪些主对角线
    vector<int> anti_diag;  // 占据了哪些副对角线

    void dfs(vector<int> &C, vector<vector<string> > &result, int row) {
        const int N = C.size();
        if (row == N) { // 终止条件,也是收敛条件,意味着找到了一个可行解
            vector<string> solution;
            for (int i = 0; i < N; ++i) {
                string s(N, '.');
                for (int j = 0; j < N; ++j) {
                    if (j == C[i]) s[j] = 'Q';
                }
                solution.push_back(s);
            }
            result.push_back(solution);
            return;
        }

        for (int j = 0; j < N; ++j) {  // 扩展状态,一列一列的试
            const bool ok = columns[j] == 0 && main_diag[row + j] == 0 &&
                    anti_diag[row - j + N] == 0;
            if (!ok) continue;  // 剪枝:如果合法,继续递归
            // 执行扩展动作
            C[row] = j;
            columns[j] = main_diag[row + j] = anti_diag[row - j + N] = 1;
            dfs(C, result, row + 1);
            // 撤销动作
            // C[row] = 0;
            columns[j] = main_diag[row + j] = anti_diag[row - j + N] = 0;
        }
    }
};

Java代码:

public class Solution {
    static int path[];
	public static List<String[]> solveNQueens(int n) {
       path = new int[n];
       List<String[]> listStr = new ArrayList<String[]>(100); 
       nqueens(0,n, listStr);
       return listStr;
    }
    public static boolean check(int row){
    	for(int i=0; i<row; i++){
    		if(path[i] == path[row] || Math.abs(row-i) == Math.abs(path[row]-path[i]))
    			return false;
    	}
    	return true;
    }
	private static void nqueens(int row,int n, List<String[]> listStr) {
		if(row == n){
			String[] strs = new String[n];
			char charArr[][] = new char[n][n];
			for(int i=0; i<n; i++){
				Arrays.fill(charArr[i],'.');
				charArr[i][ path[i] ] = 'Q';
				strs[i] = new String(charArr[i]);
			}
			listStr.add(strs);
			
			
		}else{
			for(int i=0; i<n; i++){
				path[row] = i;
				if(check(row)){
					nqueens(row+1, n, listStr);
				}
			}
			
		}
	}
}

相关题目
N-Queens II


  1. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count

  3. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.