N皇后问题是计算机科学中最为经典的问题之一。1848年，国际西洋棋起手马克思·贝瑟尔提出了8皇后问题。
将N个皇后摆放在N*N的棋盘中，互相不可攻击，有多少种摆放方式，每种摆放方式具体是怎样的？
#include
#include
class Solution
{
public:
Solution() {};
~Solution() {};
std::vector<std::vector> solveNQueens(int n)
{
std::vector<std::vector> result;
std::vector<std::vector> mark;
std::vector location;
for (int i = 0; i < n; i++)
{
mark.push_back((std::vector()));
for (int j = 0; j < n; j++)
{
mark[i].push_back(0);
}
location.push_back("");
location[i].append(n,'.');
}
generate(0,n,location,mark,result);
return result;
}
private:
void put_down_the_queen(int x, int y, std::vector<std::vector>& mark)
{
static const int dx[] = { -1,1,0,0,-1,-1,1,1 };
static const int dy[] = { 0,0,-1,1,-1,1,-1,1 };
mark[x][y] = 1;
for (unsigned int i = 1; i < mark.size(); i++)
{
for (int j = 0; j = 0 && new_x = 0 && new_y < mark.size())
{
mark[new_x][new_y] = 1;
}
}
}
}
void generate(int k, int n, std::vector& location, std::vector<std::vector> &mark, std::vector<std::vector> &result)
{
if (k==n)
{
result.push_back(location);
return;
}
for (int i = 0; i < n; i++)
{
if (mark[k][i]==0)
{
std::vector<std::vector> tmp_mark=mark;
location[k][i] = 'Q';
put_down_the_queen(k, i, mark);
generate(k + 1, n, location, mark, result);
mark = tmp_mark;
location[k][i] = '.';
}
}
}
};
int main()
{
std::vector<std::vector> result;
Solution solve;
result = solve.solveNQueens(4);
for (unsigned int i = 0; i < result.size(); i++)
{
printf("i=%d\n",i);
for (int j = 0; j < result[i].size(); j++)
{
printf("%s\n",result[i][j].c_str());
}
printf("\n");
}
return 0;
}
运行结果为：
i=0
.Q..
...Q
Q...
..Q.
i=1
..Q.
Q...
...Q
.Q..