【每日一题14】AcWing 1432. 棋盘挑战

发表于 更新于 分类于 Valine：
本文字数： 159 阅读时长 ≈ 1 分钟

Day14 AcWing 1432. 棋盘挑战

思路

  1. DFS
  2. 剪枝
  3. 对角线判断
    $y=x+b$ $\Rightarrow$ $b=y-x+n$(防止负数)
    $y=-x+b$ $\Rightarrow$ $b=y+x$

拓展

  1. 八皇后问题
  2. Dancing Links

类似题目

  1. AcWing 166. 数独
  2. Acwing 169. 数独2
  3. AcWing 183. 靶形数独

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 15;

int n;
bool col[N], d[N * 2], ud[N * 2];
int ans, path[N];

void dfs(int x)
{
    if (x > n)
    {
        ans ++ ;
        if (ans <= 3)
        {
            for (int i = 1; i <= n; i ++ ) cout << path[i] << ' ';
            cout << endl;
        }
        return;
    }

    for (int y = 1; y <= n; y ++ )
        if (!col[y] && !d[x + y] && !ud[x - y + n])
        {
            col[y] = d[x + y] = ud[x - y + n] = true;
            path[x] = y;
            dfs(x + 1);
            col[y] = d[x + y] = ud[x - y + n] = false;
        }
}

int main()
{
    cin >> n;
    dfs(1);
    cout << ans << endl;
    return 0;
}