n皇后问题
mufiye 内核新手
  2021-05-13 11:40:57 2021-05-13 11:40      1.8k 字  8 分钟  

n皇后问题

一、问题介绍

n皇后问题借鉴了国际象棋中皇后的概念，此处我先介绍一下这里的皇后指的是什么。在国际象棋中，在一个棋盘上，皇后可以横着走、竖着走和斜着走。而n皇后问题指的就是，假设有n个皇后，在一张n*n的棋盘上，如何将这些皇后放在这张棋盘上，是这些皇后彼此不在对方的打击范围内，也就是怎么样放才能使她们都是安全的。

二、算法

在本文中，我将使用回溯算法来解决这个问题。回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。用回溯算法解决问题的一般步骤一是针对所给问题，定义问题的解空间，二是确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间，三是以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

针对n皇后问题，我们可以将棋盘表示为一个n行n列的矩阵，我们将这个矩阵初始化为一个全0的矩阵，假如这个棋盘的i行j列放了一个皇后，我们就将这个矩阵的i行j列的值设置为1。由题设，我们易知每一行有且只有一个皇后，我们可以用一个树的结构来表示整个搜索过程，因此我们可以将每一层树定义为将每一行的皇后放入棋盘中的某一列。之后我们进行深度优先搜索，如果某一次将皇后放入棋盘导致一些皇后不安全，那么我们就把这一次放置的情况作为根的树剪掉，并且回溯到之前的放法，直到遍历完整颗树。

三、代码实现

为了节省资源，我发现不用使用空间复杂度过大的矩阵而使用向量也能够表示将皇后放在棋盘的某个位置并完成搜索。因为为了保证每个皇后的安全，每一行有且只有一个皇后，那么我们可以用向量的第一个元素表示第一行的皇后放在哪一列，第二个元素表示第二行的皇后放在哪一列，第n个元素表示第n行的皇后放在哪一列。

在具体的代码中，我使用了递归函数solveNQ来实现搜索，使用is_safe来判断放入某个皇后是否会导致某些皇后不安全，最后我定义了一个findAllNQ函数来实现保证搜索完了整一棵树，得到所有的解。以下为具体的代码及测试结果：

代码：

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
def findAllNQ(n,solution):
    row=1
    vector=[0 for i in range(n)]
    solveNQ(vector.copy(),row,solution)
        
def solveNQ(vector,row,solution):
    index=row-1
    if row>len(vector):
        solution.append(vector.copy())
        return False
    for col in range(1,len(vector)+1):
        if is_safe(vector,row,col):
            vector[index]=col
            if solveNQ(vector,row+1,solution):
                return True
            else:
                vector[index]=0
    return False
            
def is_safe(vector,row,col):
    for i in range(row-1):
        if col==vector[i]:
            return False
    for i in range(row-1):
       if (vector[i]+i+1)==(col+row):#左斜，和相等
          return False
       if abs(i+1-row)==abs(vector[i]-col):#右斜，差相等
          return False
    return True

测试1：

1
2
3
4
5
6
7
8
solution=[]
n=4
findAllNQ(n,solution)
print("-------------------------")
print("the solutions are:")
for i in solution:
     print(i)
print("the total number of the solutions is {}".format(len(solution)))

结果1：

1
2
3
4
5
-------------------------
the solutions are:
[2, 4, 1, 3]
[3, 1, 4, 2]
the total number of the solutions is 2

测试2：

1
2
3
4
5
6
7
8
solution=[]
n=8
findAllNQ(n,solution)
print("-------------------------")
print("the solutions are:")
for i in solution:
     print(i)
print("the total number of the solutions is {}".format(len(solution)))

结果2：

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
84
85
86
87
88
89
90
91
92
93
94
95
-------------------------
the solutions are:
[1, 5, 8, 6, 3, 7, 2, 4]
[1, 6, 8, 3, 7, 4, 2, 5]
[1, 7, 4, 6, 8, 2, 5, 3]
[1, 7, 5, 8, 2, 4, 6, 3]
[2, 4, 6, 8, 3, 1, 7, 5]
[2, 5, 7, 1, 3, 8, 6, 4]
[2, 5, 7, 4, 1, 8, 6, 3]
[2, 6, 1, 7, 4, 8, 3, 5]
[2, 6, 8, 3, 1, 4, 7, 5]
[2, 7, 3, 6, 8, 5, 1, 4]
[2, 7, 5, 8, 1, 4, 6, 3]
[2, 8, 6, 1, 3, 5, 7, 4]
[3, 1, 7, 5, 8, 2, 4, 6]
[3, 5, 2, 8, 1, 7, 4, 6]
[3, 5, 2, 8, 6, 4, 7, 1]
[3, 5, 7, 1, 4, 2, 8, 6]
[3, 5, 8, 4, 1, 7, 2, 6]
[3, 6, 2, 5, 8, 1, 7, 4]
[3, 6, 2, 7, 1, 4, 8, 5]
[3, 6, 2, 7, 5, 1, 8, 4]
[3, 6, 4, 1, 8, 5, 7, 2]
[3, 6, 4, 2, 8, 5, 7, 1]
[3, 6, 8, 1, 4, 7, 5, 2]
[3, 6, 8, 1, 5, 7, 2, 4]
[3, 6, 8, 2, 4, 1, 7, 5]
[3, 7, 2, 8, 5, 1, 4, 6]
[3, 7, 2, 8, 6, 4, 1, 5]
[3, 8, 4, 7, 1, 6, 2, 5]
[4, 1, 5, 8, 2, 7, 3, 6]
[4, 1, 5, 8, 6, 3, 7, 2]
[4, 2, 5, 8, 6, 1, 3, 7]
[4, 2, 7, 3, 6, 8, 1, 5]
[4, 2, 7, 3, 6, 8, 5, 1]
[4, 2, 7, 5, 1, 8, 6, 3]
[4, 2, 8, 5, 7, 1, 3, 6]
[4, 2, 8, 6, 1, 3, 5, 7]
[4, 6, 1, 5, 2, 8, 3, 7]
[4, 6, 8, 2, 7, 1, 3, 5]
[4, 6, 8, 3, 1, 7, 5, 2]
[4, 7, 1, 8, 5, 2, 6, 3]
[4, 7, 3, 8, 2, 5, 1, 6]
[4, 7, 5, 2, 6, 1, 3, 8]
[4, 7, 5, 3, 1, 6, 8, 2]
[4, 8, 1, 3, 6, 2, 7, 5]
[4, 8, 1, 5, 7, 2, 6, 3]
[4, 8, 5, 3, 1, 7, 2, 6]
[5, 1, 4, 6, 8, 2, 7, 3]
[5, 1, 8, 4, 2, 7, 3, 6]
[5, 1, 8, 6, 3, 7, 2, 4]
[5, 2, 4, 6, 8, 3, 1, 7]
[5, 2, 4, 7, 3, 8, 6, 1]
[5, 2, 6, 1, 7, 4, 8, 3]
[5, 2, 8, 1, 4, 7, 3, 6]
[5, 3, 1, 6, 8, 2, 4, 7]
[5, 3, 1, 7, 2, 8, 6, 4]
[5, 3, 8, 4, 7, 1, 6, 2]
[5, 7, 1, 3, 8, 6, 4, 2]
[5, 7, 1, 4, 2, 8, 6, 3]
[5, 7, 2, 4, 8, 1, 3, 6]
[5, 7, 2, 6, 3, 1, 4, 8]
[5, 7, 2, 6, 3, 1, 8, 4]
[5, 7, 4, 1, 3, 8, 6, 2]
[5, 8, 4, 1, 3, 6, 2, 7]
[5, 8, 4, 1, 7, 2, 6, 3]
[6, 1, 5, 2, 8, 3, 7, 4]
[6, 2, 7, 1, 3, 5, 8, 4]
[6, 2, 7, 1, 4, 8, 5, 3]
[6, 3, 1, 7, 5, 8, 2, 4]
[6, 3, 1, 8, 4, 2, 7, 5]
[6, 3, 1, 8, 5, 2, 4, 7]
[6, 3, 5, 7, 1, 4, 2, 8]
[6, 3, 5, 8, 1, 4, 2, 7]
[6, 3, 7, 2, 4, 8, 1, 5]
[6, 3, 7, 2, 8, 5, 1, 4]
[6, 3, 7, 4, 1, 8, 2, 5]
[6, 4, 1, 5, 8, 2, 7, 3]
[6, 4, 2, 8, 5, 7, 1, 3]
[6, 4, 7, 1, 3, 5, 2, 8]
[6, 4, 7, 1, 8, 2, 5, 3]
[6, 8, 2, 4, 1, 7, 5, 3]
[7, 1, 3, 8, 6, 4, 2, 5]
[7, 2, 4, 1, 8, 5, 3, 6]
[7, 2, 6, 3, 1, 4, 8, 5]
[7, 3, 1, 6, 8, 5, 2, 4]
[7, 3, 8, 2, 5, 1, 6, 4]
[7, 4, 2, 5, 8, 1, 3, 6]
[7, 4, 2, 8, 6, 1, 3, 5]
[7, 5, 3, 1, 6, 8, 2, 4]
[8, 2, 4, 1, 7, 5, 3, 6]
[8, 2, 5, 3, 1, 7, 4, 6]
[8, 3, 1, 6, 2, 5, 7, 4]
[8, 4, 1, 3, 6, 2, 7, 5]
the total number of the solutions is 92

四、结论

在本文中，我成功使用回溯算法解决了n皇后问题，回溯算法作为一种特殊的穷举算法，使用深度优先搜索和剪枝大大降低了算法复杂度，而在解决n皇后问题时，使用向量代替矩阵来表示解空间又大大降低了解决该问题的算法复杂度。

  • 本文标题：n皇后问题
  • 本文作者：mufiye
  • 创建时间：2021-05-13 11:40:57
  • 本文链接：http://mufiye.github.io/2021/05/13/n皇后问题/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论