N皇后

 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
41
42
43
44
45
46
47
48
49
50
51
52
53

#include <bits/stdc++.h>

using namespace std;

int hash[10][10];
int cnt;

void doAdd(int r, int c, int n, int val) {
    if (r < 0 || r >= n) {
        return ;
    }
    if (c < 0 || c >= n) {
        return ;
    }
    hash[r][c] += val;
}

void add(int r, int c, int n, int val) {
    int i;
    for (i = 0; i < n; i++) {
        doAdd(r, i, n, val);
        doAdd(i, c, r, val);
    }
    for (i = 0; i < n; i++) {
        doAdd(r + 1, c + 1, n, val)
        doAdd(r - 1, c - 1, n, val)
        doAdd(r + 1, c - 1, n, val)
        doAdd(r - 1, c + 1, n, val)
    }
}

void dfs(int depth, int maxDepth) {
    int i;
    if (depth == maxDepth) {
        ++cnt;
        return ;
    }
    for (i = 0; i < maxDepth; i++) {
        if (hash[depth][i] == 0) {
            add(depth, i, maxDepth, i);
            dfs(depth + 1, maxDepth);
            add(depth, i, maxDepth, -i)
        }
    }
}

int main() {
    int n;
    cin >> n;
    memset(hash, 0, sizeof(hash));
    dfs(0, n);
    return cnt;
}

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

package PACK6;
// https://www.bilibili.com/video/BV14Y4y1C7SW
public class N皇后 {
    // 首先定义一个哈希表 hash ij大于0 表示这个位置不能放皇后
    static int[][] hash = new int[10][10];
    // 定义全局变量cnt 表示方案数
    static int cnt;

    public static void doADD(int r, int c, int n, int val) {
        // 如果行的范围越越界则标记无效
        if (r < 0 || r >= n) {
            return;
        }
        // 如果列的范围越越界则标记无效
        if (c < 0 || c >= n) {
            return;
        }
        // 如果对应位置是安全的，也就是没有皇后能够攻击到，则标记为1
//        (否则在对应位置的hash数组执行标记)
        if (hash[r][c] == 0) {
            hash[r][c] = val;
        }
    }

//    实现放置皇后的过程
    public static void add(int r,int c ,int n,int val) {
//        val = 1; // 代表(r,c)位置放置了一个皇后
//        val = -1; // 代表(r,c)位置取出了一个皇后
        int i;
        for (i = 0; i < n; i++) {
            // 每放入一个皇后,需要将他所在的行，所在的列，所在的对角线 都进行标记
            doADD(r, i, n, val); // 标记所在行
            doADD(i, c, n, val); // 标记所在列
        }
        for (i = 1; i <= n; i++) {
            // 标记主对角线
            doADD(r + i, c + i, n, val);
            doADD(r - i, c - i, n, val);
            // 标记副对角线
            doADD(r + i, c - i, n, val);
            doADD(r - i, c + i, n, val);
        }

    }
    public static void dfs(int depth, int maxDepth) {
        // 当前要放置的行号和总共要放置的行数
        // 如果当前行数==总行数 方案数+1 函数直接返回
        if (depth == maxDepth) {
            cnt++;
            return;
        }
        // 在当前行的每一列
        for (int i = 0; i < maxDepth; i++) {
//            如果发现有对应位置是安全的，也就是没有皇后能够攻击到，
            if (hash[depth][i] == 0) {
//                则调用add放置一个皇后
                add(depth, i, maxDepth, 1);
//                递归求解下一行
                dfs(depth + 1, maxDepth);
//                递归退出后，删除放置的皇后(取回前面放置的皇后)
                add(depth, i, maxDepth, -1);

            }
        }
    }
    public static int fakeMain(int n) {
//        初始化cnt = 0;
        cnt = 0;
//        初始化hash ij = 0,表示一开始一个空的棋盘
        for (int i = 0; i < 10; i++) {
            for (int j = 0; j < 10; j++) {
                hash[i][j] = 0;
            }
        }
//        递归模拟每一行放置皇后后的情况
        dfs(0, n);
        return cnt;
    }

    public static void main(String[] args) {
        fakeMain(4);
    }
}

 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

class Solution {
    int hash[10][10];
    int cnt;

    // 实现标记
    void doAdd(int r, int c, int n, int val) {
        // 如果行的范围越界 则标记失败
        if (r < 0 || r >= n) {
            return;
        }
        // 如果列的范围越界 则标记失败
        if (c < 0 || c >= n) {
            return;
        }
        // 否则在对应的位置上的hash数组执行标记
        hash[r][c] += val;
    }
    // 实现放置皇后的过程
    void add(int r,int c,int n,int val) {
        int i;
        for (i = 0; i < n; i++)
        {
            doAdd(r,i,n,val);
            doAdd(i,c,r,val);
        }
        for (i = 0; i < n; i++)
        {
            // 标记主对角线
            doAdd(r+i,c+i,n,val);
            doAdd(r-i,c-i,n,val);
            // 标记副对角线
            doAdd(r+i,c-i,n,val);
            doAdd(r-i,c+i,n,val);
        }
    }

    void dfs(int depth, int maxDepth) {
        int i;
        if(depth == maxDepth) {
            ++cnt;
            return ;
        }
        for (i = 0; i < maxDepth; i++)
        {
            if(hash[depth][i] == 0) //对应位置安全，没有皇后能攻击到
            {
                // 则调用add放置一个皇后
                add(depth, i, maxDepth , 1);
                // 递归求解下一行
                dfs(depth + 1, maxDepth);
                // 递归推出后，取出皇后
                add(depth, i, maxDepth, -1);
            }
        }

    }
public:
    int totalNQueens(int n) {
        cnt = 0;
        memset(hash, 0, sizeof(hash));
        dfs(0,n);
        return cnt;
    }
}