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.."] ]
Hide Tags
Backtracking
Hide Similar Problems
(H) N-Queens II
按照题目的意思，就是横竖以及两对角线都不能同时又两个Q，
比较直接的想法是通过一个辅助的矩阵，每当加入一个Q，就把它的横竖左右对角全都置为taken，
这样就能比较直接地判断出后面的Q是否还可以放得下。
按照这个思路实现了一下，结果不太理想，20ms.
其中还有一个问题是每次恢复被置为taken的标志时，不能用置位一样的算法，
因为有些位是置位之前就已经被别的Q置了位的，直接删去会出错。
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> rst;
vector<string> buf;
bool* taken = new bool[n*n]();
if(n)
build(n, 0, taken, buf, rst);
if(taken)
free(taken);
return rst;
}
void build(int n, int row, bool* taken, vector<string>& buf, vector<vector<string>>& rst)
{
string rr(n, '.');
int base = row*n;
for(int ii=0; ii<n; ++ii)
{
if(false == taken[base + ii])
{
vector<int> modified;
setTaken(n, row, ii, taken, modified);
rr[ii] = 'Q';
buf.push_back(rr);
if(row==n-1)
rst.push_back(buf);
else
build(n, row+1, taken, buf, rst);
buf.pop_back();
rr[ii] = '.';
unsetTaken(n, taken, modified);
}
}
return;
}
void setTaken(int n, int row, int col, bool* taken, vector<int>& modified)
{
int base = (row-1)*n;
for(int rr=row; rr<n; ++rr)
{
int roff = rr-row;
base += n;
for(int cc=0; cc<n; ++cc)
{
int idx = base+cc;
if((false==taken[idx]) && ((rr==row)||(cc==col)||(roff==abs(cc-col))) )
{
taken[idx] = true;
modified.push_back(idx);
}
}
}
}
void unsetTaken(int n, bool* taken, vector<int>& modified)
{
int total = modified.size();
for(int tt=0; tt<total; ++tt)
taken[modified[tt]] = false;
}
};
20 ms.
而后翻看讨论区，看到两个比较清晰的解法：
一个是直接利用结果区里面的Q，来判断当前位置的横竖左右对角上是不是已经有Q了
不需要像我前面在辅助数组里那样把整条横竖左右对角全部置位 / 恢复，
只需要判断当前线路上有没有任何一个 Q ，相对简洁不少。
Solution A: Directly check the validity of each position, 12ms:
另一个解法则是分别用三个辅助数组分别来表示纵向的列，左对角线，右对角线的占用情况。class Solution { public: std::vector<std::vector<std::string> > solveNQueens(int n) { std::vector<std::vector<std::string> > res; std::vector<std::string> nQueens(n, std::string(n, '.')); solveNQueens(res, nQueens, 0, n); return res; } private: void solveNQueens(std::vector<std::vector<std::string> > &res,std::vector<std::string> &nQueens, int row, int &n) { if (row == n) { res.push_back(nQueens); return; } for (int col = 0; col != n; ++col) if (isValid(nQueens, row, col, n)) { nQueens[row][col] = 'Q'; solveNQueens(res, nQueens, row + 1, n); nQueens[row][col] = '.'; } } bool isValid(std::vector<std::string> &nQueens, int row, int col, int &n) { //check if the column had a queen before. for (int i = 0; i != row; ++i) if (nQueens[i][col] == 'Q') return false; //check if the 45° diagonal had a queen before. for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) if (nQueens[i][j] == 'Q') return false; //check if the 135° diagonal` had a queen before. for (int i = row - 1, j = col + 1; i >= 0 && j < n; --i, ++j) if (nQueens[i][j] == 'Q') return false; return true; } };
对于一个宽度为 n 的矩阵，其有 n 个列，有 2*n –1 条左对角线，有 2*n –1 条右对角线；
而对于一个点 （x， y）而言，它：
列|/第一左对角
1 2 3
X 4 5 6
7 8 9
\第一右对角
-- 所在的列是 第 y 列，
-- 所在的左对角线是第 (x + y) 条， （以最左边出现的对角线为第 0 条）
-- 所在的右对角线是第 (( (n-1) - x ) + y ) 条，也就是 (n-1 –x + y ) 条。（以最左边出现的对角线为第 0 条）
这样就可以在一个Q出现的时候，直接把某一列，某一左对角线，某一右对角线被占用的情况标识出来了。
Solution B: Use flag vectors as bitmask, 4ms:经典的题，当然有不少经典的解法。
The number of columns isn,
the number of 45° diagonals is2 * n - 1,
the number of 135° diagonals is also2 * n - 1.
When reach[row, col], the column No. iscol,
the 45° diagonal No. isrow + coland the 135° diagonal No. isn - 1 + col - row.
We can use three arrays to indicate if the column or the diagonal had a queen before,
if not, we can put a queen in this position and continue.
/** | | | / / / \ \ \ * O O O O O O O O O * | | | / / / / \ \ \ \ * O O O O O O O O O * | | | / / / / \ \ \ \ * O O O O O O O O O * | | | / / / \ \ \ * 3 columns 5 45° diagonals 5 135° diagonals (when n is 3) */ class Solution { public: std::vector<std::vector<std::string> > solveNQueens(int n) { std::vector<std::vector<std::string> > res; std::vector<std::string> nQueens(n, std::string(n, '.')); std::vector<int> flag_col(n, 1), flag_45(2 * n - 1, 1), flag_135(2 * n - 1, 1); solveNQueens(res, nQueens, flag_col, flag_45, flag_135, 0, n); return res; } private: void solveNQueens(std::vector<std::vector<std::string> > &res, std::vector<std::string> &nQueens, std::vector<int> &flag_col, std::vector<int> &flag_45, std::vector<int> &flag_135, int row, int &n) { if (row == n) { res.push_back(nQueens); return; } for (int col = 0; col != n; ++col) if (flag_col[col] && flag_45[row + col] && flag_135[n - 1 + col - row]) { flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 0; nQueens[row][col] = 'Q'; solveNQueens(res, nQueens, flag_col, flag_45, flag_135, row + 1, n); nQueens[row][col] = '.'; flag_col[col] = flag_45[row + col] = flag_135[n - 1 + col - row] = 1; } } };
用bit位来做标识符，可能是各种解法里最快的一个了。
参考了一个介绍的帖子，写了如下的实现，跑的结果是 4 ms.
原理是，用colflags, ldflags, rdflags 分别来表示列，左对角，右对角的占用情况，
每次把三者相或，得到所有占用的bit，而后求反，跟掩码再与，就得到当前available的bit位了。
再从这个available的bit位里，取出最右侧的（最右侧是最低的第0位bit，所以从右边开始），
假设取它为新的 Q 的位置，然后再把它占用的列，左右对角补充到bit flags里面去，进行下一次的尝试
如果所有colflags全部填满，则找到一组答案，push到结果区即可。
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> rst;
vector<string> buf;
int mask = (1<<n)-1;
if(n)
build(0, 0, 0, n, mask, buf, rst);
return rst;
}
void build(int colflags, int ldflags, int rdflags,
int n, int mask, vector<string>& buf, vector<vector<string>>& rst)
{
if(mask == colflags)
rst.push_back(buf);
else
{
int available = mask & (~(colflags | ldflags | rdflags));
while(available)
{
int lowestbitone = available & (-available);
available -= lowestbitone;
int idx=0;
while(lowestbitone > (1<<idx))
idx++;
string ss(n, '.');
ss[idx] = 'Q';
buf.push_back(ss);
//原帖是把lowestbitone“+”到flags上去，我改用了“|”，这样更贴切。
build(colflags|lowestbitone,
(ldflags|lowestbitone)<<1,
(rdflags|lowestbitone)>>1, n, mask, buf, rst);
buf.pop_back();
ss[idx] = '.';
}
}
}
};
看原帖的评论，有人提到随机爬山法可以秒杀百万皇后问题，好奇地搜罗了一下，果然开眼。
以下段落来自另一个博客，代码我还没有验证过：
N皇后问题 - 使用随机爬山法实现其快速解法
NOV 8TH, 2009 | COMMENTS
N皇后问题是一个经典的问题，在很多地方都有讨论过。 回溯法是经典的解法，但是随着N的增大，其复杂度的增加呈指数增长， 如果N=100使用回溯解法的话，回溯要运行的时间估计你可以去喝一壶茶了。
这段时间在看《人工智能》，里面也有对其的讨论，介绍了爬山法在N皇后问题中的应用。 爬山法是一种向值增加的方向持续移动到简单循环过程，它将会在到达一个“峰顶”时终止， 此时相邻状态中没有比该它更高的值。这个算法不维护搜索树。
最基本的爬上搜索算法(节选自《人工智能》第二版)：
随机爬山算法
function HILL-CLIMBING(problem) return a state thate is a locak maximum inputs: problem local variables: current, a node neighbor,a node current = MakeNode(INITAL-STATE(problem)); loop do neighbor = a highest-valued successor of current ; if VALUE[neighbor] <= VALUE[current] then return STATE[current]; current = neighbor ;
爬山法属于一种局部的贪婪搜索方法，当它在搜索过程中遇到了局部最大值就很难继续向下搜索了。因此产生了爬山法的变种如随机爬山法及其变种如随机爬山法，随机重新开始的爬山法， 模拟退火搜索能够非常有效的解决N皇后问题。
结合实际，我使用了随机爬山法的一个测试程序，不试不知道，测试发现速度果然是非常的快， 对于100皇后都是瞬间秒杀。不过这个程序要实现百万皇后的问题秒杀，估计还是一项很艰巨的工作。 不过随机爬山法这种方法是一种很有效的解决复杂搜索问题的方法之一。
程序如下，供以后参考：
使用随机爬山法解决N皇后问题
#include <stdio.h> #include <stdlib.h> #include <iostream> #include <iterator> #include <vector> typedef std::vector<int> CollisionList_t; void print_row_mark(int N) { for (int i=0; i<N; ++i) { std::cout << "+---"; } std::cout << "+" << std::endl; } void print_row(int N, int fill) { for (int i=0; i<N; ++i) { std::cout << "| " << ((i==fill) ? 'X' : ' ') << " "; } std::cout << "|" << std::endl; print_row_mark(N); } // 皇后位置的表示方法: // 使用数组chessman[N]来表示N个皇后的位置 // 第i个皇后chessman[i]的下标i表示其行所在的位置， // chessman[i]表示其列的位置。 // // 一个四皇后问题的表示方法如下所示： // (0, 1) (1, 3) (2, 0) (3, 2) // +---+---+---+---+ // | | X | | | // +---+---+---+---+ // | | | | X | // +---+---+---+---+ // | X | | | | // +---+---+---+---+ // | | | X | | // +---+---+---+---+ // void print_chessboard(int* chessman, int N) { for (int i=0; i<N; ++i) { std::cout << "(" << i << ", " << chessman[i] << ") "; } std::cout << std::endl; print_row_mark(N); for (int i=0; i<N; ++i) { print_row(N, chessman[i]); } } // 随机生成一个初始化状态，在每行每列上放置一个皇后 void generate_init_state(int* chessman, int N) { for (int i=0; i<N; ++i) { chessman[i] = i; } for (int i=0; i<N; ++i) { int r = rand(); r = r % N; std::swap(chessman[r], chessman[N-r-1]); } } // 返回冲突的皇后个数 int h(int* chessman, int N, CollisionList_t& collision_list) { collision_list.clear(); int collision = 0; for (int i=0; i<N; ++i) { for (int row=i+1; row<N; row++) { if ((chessman[row] == chessman[i] + row - i) || (chessman[row] == chessman[i] - (row - i))) { collision_list.push_back(row); ++collision; } } } return collision; } // 如果交换后冲突不比原来的大，就进行交换 // 只有交换成功后才改变cl为新的冲突列表 int try_exchange(int* chessman, int N, int row1, int row2, CollisionList_t& cl) { CollisionList_t new_cl; // 交换两行的皇后的位置 std::swap(chessman[row1], chessman[row2]); int new_collision = h(chessman, N, new_cl); if (new_collision > cl.size()) { // 取消之前的交换 std::swap(chessman[row1], chessman[row2]); } else { cl = new_cl; } return new_cl.size(); } int choose_next_state(int* chessman, int N, CollisionList_t& cl) { int old_collision = cl.size(); int new_collision; int row1 = -1; int row2 = -1; // 优化最后只有一个冲突的解 if (cl.size() == 1) { for (int i=0; i<N; ++i) { if (i != cl[0] && (try_exchange(chessman, N, cl[0], i, cl) == 0)) { return 0; } } } do { // 最后的选择，随机的选择两个皇后调换其位置 row1 = rand() % N; do { row2 = rand() % N; } while (row1 == row2); new_collision = try_exchange(chessman, N, row1, row2, cl); } while (new_collision > old_collision); return new_collision; } // 使用随机爬山法寻找一个N皇后问题的解 int queue_solution(int N) { int* chessman = new int[N]; int max_tries = N*N; int max_steps = N*N; int tries = 0; while (tries < max_tries) { ++tries; int steps = 0; int collision; CollisionList_t collision_list; srand(time(NULL) + tries * collision); generate_init_state(chessman, N); collision = h(chessman, N, collision_list); while ((collision != 0) && (steps<max_steps)) { collision = choose_next_state(chessman, N, collision_list); ++steps; } if (collision == 0) { std::cout << "Found a solution. Tries: " << tries << " Steps: " << steps << std::endl; print_chessboard(chessman, N); return 1; } } return 0; } // 接受一个命令行参数，要求为整数N，表示要寻找的解是N皇后问题。 int main(int argc, char* argv[]) { int N = 8; // 缺省为寻找8皇后问题的一个解 if (argc == 2) { N = atoi(argv[1]); std::cout << "N: " << N << std::endl; } if (N <= 0) { std::cout << "Input error: parameter must be a postive integer" << std::endl; return 1; } srand(time(NULL)); int result = queue_solution(N); if (result != 1) { std::cout << "Failed, please try re-run to get a solution." << std::endl; } return 0; }
TODO：在选择下一步的时候还有改进空间，比如优先从冲突的皇后中随机选择皇后进行下一次的位置调换等。
这道题可以琢磨的东西还真不少，先写到这里，得空再继续学习。
扩展：
ReplyDeletehttp://xuyuanda.blogspot.com/2015/08/n-queens.html
//原帖是把lowestbitone“+”到flags上去，我改用了“|”，这样更贴切。
ReplyDeletebuild(colflags|lowestbitone,
(ldflags|lowestbitone)<<1,
(rdflags|lowestbitone)>>1, n, mask, buf, rst);
对于左右对角，当在(x, y)位置防止一个皇后之后，下一行里受影响的位置分别是 y 的左右两个，因此要分别左右移动一个bit。