[leetcode] N-Queens

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

分析：

把棋盘存储为一个N维数组a[N]，数组中第i个元素的值代表第i行的皇后位置，这样便可以把问题的空间规模压缩维O(N)，在判断是否冲突时也很简单，首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减得绝对值相等，即| row – i | = | col – a[i] | 。

 1 const int N_QUEEN = 1000;
 2 const int INVALID = -1000;
 3 
 4 class Solution
 5 {
 6 private:
 7   bool is_valid(const int row,const int col,const int n)
 8   {
 9     for(int i=0; i<n; ++i)
10       if(A[i] == col || abs(i-row) == abs(A[i]-col))
11         return false;
12 
13     return true;
14   }
15 
16   void show(vector<vector<string> > &ret, int n)
17   {
18     vector<string> temp;
19     string str = "";
20     for(int i=0; i<n; ++i)
21     {
22       str = "";
23       for(int j=0; j<n; ++j)
24       {
25         if(A[i] == j)
26           str += "Q";
27         else
28           str += ".";
29       }
30 
31       temp.push_back(str);
32     }
33 
34     ret.push_back(temp);
35   }
36 
37   void queen(vector<vector<string> > &ret, int n)
38   {
39     int i=0, j=0;
40 
41     while(i<n)
42     {
43       while(j<n)
44       {
45         if(is_valid(i, j, n))
46         {
47           A[i] = j;
48           j = 0;
49           break;
50         }
51         else
52           j++;
53       }
54 
55       if(A[i] == INVALID)
56       {
57         if(i == 0)
58           break;
59         else
60         {
61           i--;
62           j = A[i] + 1;
63           A[i] = INVALID;
64           continue;
65         }
66       }
67 
68       if(i == n-1)
69       {
70         show(ret, n);
71         j = A[i] + 1;
72         A[i] = INVALID;
73         continue;
74       }
75       i++;
76     }
77     cout << "i = " << i << "   ret.size() =  " << ret.size() <<endl;
78   }
79 
80 public:
81   vector<vector<string> > solveNQueens(int n)
82   {
83     for(int i=0; i<n; ++i)
84       A[i] = INVALID;
85 
86     vector<vector<string> > ret;
87     queen(ret, n);
88 
89     return ret;
90   }
91 
92 private:
93   int A[N_QUEEN];
94 };