[算法] 八皇后

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

因为题目太长以后都默认放在后面了，可以通过右边的目录快速定位

思路

DFS

条件判断

前提条件：所有已经放置的 quen 和当前位置不在同一条直线或者对角线上

附加条件 位置
j == y |
i + j == x + y /
i + y == x + j \

位运算

八皇后问题

unsigned char 8 位

  1. a, b, c 三个数来分别对应 /, |, \ 三种冲突

  2. d = ~(a | b | c) 得到的就是排除掉所有冲突后剩下的可行位置

  3. bit = d & -d 每次取最后一个 1 尝试

  4. b == 125 也就是所有的位都为 1 ，即每一行都填上了一个皇后便是答案

八皇后 Coding

1
2
3
4
5
6
7
8
9
10
11
12
void dfs(unsigned char a, unsigned char b, unsigned char c) {
    if (b == 125) {
        cnt++;
        return;
    }
    unsigned char d = ~(a | b | c);
    while (d) {
        unsigned char bit = d & -d;
        dfs((a | bit) << 1, b | bit, (c | bit) >> 1);
        d -= bit;
    }
}

N 皇后问题

第一思路 |

处理掉 a 的无效位

  1. 使用了 unsigned char 只能用来解决八皇后的问题，使用 unsigned int 将其升级到最高 32 x 32 的棋盘

  2. 需要注意的三个地方就是:

    1. while (d) 的边界问题。

      • d = ~(a | b | c) 需要 d 中确保全闲置位置部为 1，所以后 n 位全部为 0 的时候，就是 d 的最小边界(不包含，类似于 0),也就是八皇后时的边界：11111111....1 | 00000000

      • board = (~0 >> n) << n

    2. 下层 dfs() 时 a 的问题。

      • 在 unsigned char 中，对于多余的左移，会直接溢出(c 的右移同理)，但是 unsigned int 中，n < 32 的情况中，左移会移动到闲置位置上将其置为 1，这些位置必须保持为 0 不变。，使用 << 将移位后闲置多余的 1 移除即可.置于 c 因为是右移，不影响闲置位置，所以不用处理

      • ma = ((a | bit) << (32 - n)) >> (32 - n)

    3. b 的值，循环结束条件。

      • 在八皇后问题中，b = 125 便是结果，但是在 N 皇后问题中，需要的就是后 n 位全部为 1，由此便可以得知其最终的边界 00000...0 | 11111111

      • b == (1 << n) - 1

  3. 如何获得每一位的位置？bit 是选择的位置的 bit = 2 ^ i，因此求出对应的 i 即可

思路改进 &

只保留 d 的有效位

让 d 只保留有效的最后 n 位即可，不需要对 while 边界处理

1
2
3
4
int d = ~(a | b | c) & ((1 << n) - 1);
...
    dfs((a | bit) >> 1, b | bit, (c | bit) >> 1);
...

N 皇后 coding

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 求出二进制表示对应的列下标
int cal_i(int x) {
    int ret = 0;
    while (x) {
        x >>= 1;
        ret++;
    }
    return ret;
}

void dfs(unsigned int a, unsigned int b, unsigned int c) {
    if (b == (1 << n) - 1) {
        cnt++;
        return;
    }
    int d = ~(a | b | c) & ((1 << n) - 1);
    while (d) {
        int bit = d & -d;
        dfs((a | bit) >> 1, b | bit, (c | bit) >> 1);
        d -= bit;
    }
}

题目描述

检查一个如下的 6 x 6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

输入输出格式

输入格式：

一个数字 N (6 <= N <= 13) 表示棋盘是 N x N 大小的。

输出格式：

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

输入输出样例

输入样例#1：

1
6

输出样例#1：

1
2
3
4
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4