51. 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*n的棋盘，在棋盘里放入n个Q，要求每一行，每一列都只有一个Q，而且每个Q的对角线上只能有一个Q。
思路：
这是一个典型的回溯问题。一条路走到黑，走到黑了退回来一步，然后再走，直到走通一条路。退回来继续寻找其他出路。
解决这个问题需要解决几个关键点：
1.关于保存一个可行路线的数据结构的选择
保存一个可行路线的时候，选择数据结构时选择一个2维数组还是什么这里需要动脑筋了，最后衡量，选择了一维数组。
比如说4-Queue时一个合法路线为
[".Q..", // Solution 1 "...Q", "Q...", "..Q."],
那么它对应的1位数组为{1，3，0，2}
解释：
1是数组第0位，对应二维数组第0行，对应的值是1，表示在第0行时，第1列可以放Q。
3是数组第1位，对应二维数组第1行，对应的值是3，表示在第1行时，第3列可以放Q。
0是数组第2位，对应二维数组第3行，对应的值是0，表示在第2行时，第0列可以放Q。
2是数组第3位，对应二维数组第3行，对应的值是2，表示在第3行时，第2列可以放Q。
数组的下标为行，数组的元素值为列。通过行列来确定Q的位置。
2.关于如何判断要加入的元素是否为合法
要插入一个合法元素到合法位置上，需要判断是否合法，在这里使用了函数
bool isValid(int curIndex, int val ,int n, vector<int> &a)
curIndex表示当前要插入的元素在合法数组中的下标，也就是行。val是要插入的列值。n是有多少个Queue，a是保存临时合法路线的一个数组。
判断a[i] == val 相等说明该列重复。
对角线的斜率为1或-1，所以如果 |val - a[i]| / |cur - i| == 1，那么说明在同一对角线上。
3.将合法的路径一个一个的放入结果临时数组中。从结果临时数组转换成结果数组。
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
class
Solution {
public
:
//判断当前要插入的值val在这个位置curIndex是否合法
bool
isValid(
int
curIndex,
int
val ,
int
n, vector<
int
> &a)
{
if
(curIndex < n )
{
for
(
int
i = curIndex - 1; i >= 0; --i)
{
if
(a[i] == val)
//判断列上是否有重复的
return
false
;
}
for
(
int
i = curIndex - 1; i >= 0; --i)
{
if
(
abs
(val - a[i]) == (curIndex - i))
//判断斜线上是否有重复的
{
return
false
;
}
}
return
true
;
}
return
false
;
}
void
PutQueens(
int
val , vector<
int
> &a)
//将合法的值放入当前临时结果数组
{
a.push_back(val);
}
//start开始的行数，也就是第start+1个Queue的放置
void
solveNQueensToIntVector(
int
start,
int
n, vector<
int
> &cur,
vector<vector<
int
>> &result)
//先转换成int来处理
{
if
(cur.size() == n)
{
result.push_back(cur);
return
;
}
if
(start == n)
return
;
//典型的回溯套路
for
(
int
i = 0; i < n; i++)
{
if
(!isValid(cur.size(),i, n, cur))
continue
;
vector<
int
> temp(cur);
//保存变化前的vector
PutQueens(i, cur);
solveNQueensToIntVector(start + 1, n, cur, result);
cur.swap(temp);
}
}
vector<vector<string>> solveNQueens(
int
n)
{
vector<
int
> cur;
vector<vector<
int
>> tempResult;
vector<vector<string>> result;
solveNQueensToIntVector(0,n,cur,tempResult);
//vector<vector<int>> tempResult 转换成 目标结果result
for
(
int
i = 0; i < tempResult.size(); i++)
{
vector<string> floorVector;
string
floor
;
for
(
int
j = 0; j < tempResult[i].size(); j++)
{
for
(
int
k = 0; k < tempResult[i][j]; k++)
{
floor
+=
"."
;
}
floor
+=
"Q"
;
for
(
int
k = tempResult[i][j] + 1; k < n ; k++)
{
floor
+=
"."
;
}
floorVector.push_back(
floor
);
floor
.clear();
}
result.push_back(floorVector);
floorVector.clear();
}
return
result;
}
};
|
本题总结：
回溯问题在N-Queue这道题中体现的十分明显。
回溯法解题思路（1）针对所给问题，定义问题的解空间；
（2）确定易于搜索的解空间结构；
（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
回溯就是让计算机自动的去搜索，碰到符合的情况就结束或者保存起来，在一条路径上走到尽头也不能找出解，就回到原来的岔路口，选择一条以前没有走过的路继续探测，直到找到解或者走完所有路径为止。就这一点，回溯和所谓的DFS（深度优先搜索）是一样的。那现在的关键是，怎么实现搜索呢？回溯既然一般使用递归来实现，那个这个递归调用该如何来写呢？我的理解就是，先判断这一次试探是否有效，如果有效则加入这个元素，然后进行下一次递归，递归后恢复加入这个合法元素之前的状态，进行下一次循环；如果无效则直接进行下一次循环。
本文转自313119992 51CTO博客，原文链接:http://blog.51cto.com/qiaopeng688/1838480
