八皇后问题

八皇后问题就是在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 3

Sample Output 1

......Q.
Q.......
..Q.....
.......Q
.....Q..
...Q....
.Q......
....Q...

解法

本题使用回溯法来求解。

1. 在第一行的可行位置放置皇后
2. 在第二行的可行位置放置皇后
3. 以此类推，在前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);
}

转载请注明来源：https://www.longjin666.top/?p=1038

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~