leetcode筆記：N-Queens

leetcode筆記：N-Queens

一. 題目描述

The n-queens puzzle is the problem of placing n queens on an nn 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.<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPkZvciBleGFtcGxlLCBUaGVyZSBleGlzdCB0d28gZGlzdGluY3Qgc29sdXRpb25zIHRvIHRoZSA0LXF1ZWVucyBwdXp6bGU6PC9wPg0KPHByZSBjbGFzcz0="brush:java;"> [ [.Q.., // Solution 1 ...Q, Q..., ..Q.], [..Q., // Solution 2 Q..., ...Q, .Q..] ]

二. 題目分析

著名的N皇後問題，題目的意思是在一個n×n棋盤中，每行放一個棋子，使得棋子所在的列和兩條斜線上沒有其他棋子，打印所有可能。

使用深搜dfs去遍歷，考慮所有可能，row中標記每一行擺放棋子的對應下標的元素，col記錄當前列是否已有棋子，對角線的判斷就是兩點行差值和列差值是否相同。

當dfs深度達到n時，意味著已經可以遍歷完最低一層，存在滿足條件的解，把矩陣中個元素的信息轉化為'.'或'Q'，存到結果中。

三. 示例代碼

// 來源:http://blog.csdn.net/havenoidea/article/details/12167399
#include 
#include 

using namespace std;

class Solution
{
public:
    vector > solveNQueens(int n)
    {
        this->row = vector(n, 0); // 行信息
        this->col = vector(n, 0); // 列信息
        dfs(0, n, result); // 深搜
        return result;
    }

private:
    vector > result; // 存放打印的結果
    vector row; // 記錄每一行哪個下標是Q
    vector col; // 記錄每一列是否已有Q

    void dfs(int r, int n, vector > & result) // 遍歷第r行，棋盤總共有n行
    {
        if (r == n) // 可遍歷到棋盤底部，填入本次遍歷結果
        {
            vector temp;
            for (int i = 0; i < n; ++i)
            {
                string s(n, '.'); // 每行先被初始化為'.'
                s[row[i]] = 'Q';  // 每行下標被標記為1的元素被標記為Q
                temp.push_back(s);  
            }
            result.push_back(temp);
        }

        int i, j;
        for (i = 0; i < n; ++i)
        {
            if (col[i] == 0)
            {

                for (j = 0; j < r; ++j)
                    if (abs(r - j) == abs(row[j] - i))
                        break;

                if (j == r)
                {
                    col[i] = 1; // 標記第i列，已存在Q
                    row[j] = i; // 第j行的第i個元素放入Q
                    dfs(r + 1, n, result); // 遍歷第r + 1行
                    col[i] = 0;
                    row[j] = 0;
                }

            }
        }
    }
};

四. 小結

後續題目N-Queens II，其實比這一題簡化許多，因為只要求輸出解的個數，不需要輸出所有解的具體狀況。