八皇后问题
八皇后问题就是在8×8的国际象棋棋盘上放置8个皇后，保证任意2个皇后都无法互相攻击的问题。
题目：ALDS1_13_A
For a given chess board where k queens are already placed, find the solution of the 8 queens problem.
Input
In the first line, an integer k is given. In the following k lines, each square where a queen is already placed is given by two integers r and c. r and cc respectively denotes the row number and the column number. The row/column numbers start with 0.
Output
Print a 8×8 chess board by strings where a square with a queen is represented by ‘Q’ and an empty square is represented by ‘.’.
Constraints
- There is exactly one solution
Sample Input 1
2
2 2
5 3Sample Output 1
......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...解法
本题使用回溯法来求解。
- 在第一行的可行位置放置皇后
- 在第二行的可行位置放置皇后
- 以此类推，在前i行放好i个皇后且保证他们不会互相攻击后，在第i+1行寻找皇后摆放的位置。
- 如果不存在满足上述条件的格子，则返回第i行继续寻找下一个不会被攻击的格子，如果不存在该格子，则继续返回第i-1行
为了记录格子[i,j]是否会被其他皇后攻击，我们需要以下数组：
变量 | 对应的状态 |
|---|---|
row[N] | 当其为true时，表明第x行受到攻击 |
col[N] | 当其为true时，表明第x列受到攻击 |
dpos[2N-1] | 当dpos[x]为true时，则满足x=i+j的格子受到攻击 |
dneg[2N-1] | 当dneg[x]为true时，则满足x=i-j+N-1的格子受到攻击 |
在上表中，i是行标，j是列标。
dpos针对的是穿过当前格子斜向左下的线，同一条线上的格子都满足i+j相同。
dneg针对的是穿过当前格子斜向右下的线，同一条线上的格子都满足i-j+(N-1)相同。加上N-1的原因是为了防止数组下标为负数。
对于特定的格子而言，只要其满足上面四个bool数组均为false，则可以放置皇后。
代码：
#include <bits/stdc++.h>
using namespace std;
#define N 8
bool table[N][N] = {false};
bool row[N] = {false};
bool col[N] = {false};
bool dpos[2*N-1] = {false};
bool dneg[2*N-1] = {false};
void print()
{
for (int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
if (table[i][j])
cout << 'Q';
else
cout << '.';
}
cout << endl;
}
}
void solve(int r)
{
if (r == 8)
{
print();
return;
}
if (row[r])
solve(r + 1);
else
{
for (int c = 0; c < N; c++)
{
if(col[c]||dpos[r+c]||dneg[r-c+7])//不能放置
continue;
//放置皇后
table[r][c] = true;
row[r] = col[c] = dpos[r+c] = dneg[r-c+N-1] = true;
solve(r+1);
//恢复原状
table[r][c] = false;
row[r] = col[c] = dpos[r+c] = dneg[r-c+N-1] = false;
}
}
}
int main()
{
int k;
cin >> k;
int r, c;
for (int i = 0; i < k; ++i)
{
cin >> r >> c;
table[r][c] = true;
row[r] = true;
col[c] = true;
dpos[r + c] = true;
dneg[r - c + N-1] = true;
}
solve(0);
}腾讯云开发者
