51. N-Queens-白红宇

51. N-Queens

阅读量：4260 次

发布时间：2019-05-26

本文共 1523 字，大约阅读时间需要 5 分钟。

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

思路：N皇后问题可以看做一个N维数组的全排列问题，主要做法是回溯

bool isNQueens(vector
   
    & res){    for (int i = 0; i < res.size(); i++){        for (int j = i + 1; j < res.size(); j++){            if (i - j == res[i] - res[j] || i - j == res[j] - res[i])return false;        }    }    return true;}void dfs_SolveNQueens(vector
    
     & res, int pos, vector
     
      
       >& tt){    if (pos == res.size()){        if (isNQueens(res)){            vector
       
         temp(res.size(), string(res.size(), '.'));            for (int i = 0; i < res.size(); i++){                temp[i][res[i]] = 'Q';            }            tt.push_back(temp);        }        return;    }    for (int i = pos; i < res.size(); i++){        swap(res[i], res[pos]);        dfs_SolveNQueens(res, pos + 1, tt);        swap(res[i], res[pos]);    }}vector
        
         
          > solveNQueens(int n) { vector
          
           
            > res; if (n == 0)return res; vector
            
              temp; for (int i = 0; i < n; i++)temp.push_back(i); dfs_SolveNQueens(temp, 0, res); return res;}