N皇后问题的深度优先搜索实现（基于Python）_ngetnq

N皇后问题的深度优先搜索实现（基于Python）

其实是人工智能大作业中的一部分啦~

解决方法就是很朴素的盲目搜索

---

算法简介

1.盲目搜索——DFS

DFS（Deep First Search），即深度优先搜索算法。将棋盘视为N行N列的矩阵（以二维列表的方式存储），从第1行开始放置皇后，然后第2行、第3行、…、第i行（i <= N），如果i=N，则所有皇后放置完毕；如果i != N且棋盘上已经没有可以放置皇后的位置，则当前放置方案不可行，回溯至上一个状态，寻找新的分支并继续求解。

2.回溯算法

回溯算法的核心是，当待解决的问题有一个最终的结果时（所有皇后放置完毕或者没有位置可以放置剩余的皇后），回溯当前状态，进入另一个分支，继续求解，直到搜索树遍历完毕。

---

算法设计与描述

1.State类

• 成员变量说明：
  N：棋盘大小N*N，N个皇后(整数)
  current_grid: 当前棋盘状态(二维列表)
  New_Q: 最新放置的皇后的位置(二维元组)
  parent_state: 父状态(State类对象)
  deep: 搜索进行的深度，即已放置的皇后的数量(整数)
• 成员函数说明：
  （1）init(self, parent_state, Q_ij, NQ)
  根据传入的父状态、最新放置皇后的位置、N，进行相应的赋值；更新棋盘的空间状态(update_grid函数)
  （2）update_grid(self)
  将棋盘中皇后的位置赋值为10；将皇后的可攻击范围的棋盘位置赋值为1；返回赋值结束后的棋盘状态(二维列表)
  （3）show_grid(self)
  打印当前棋盘状态；值为10的位置为皇后的位置，其余位置为空

2.get_extended_space_list(current_state, NQ)

• 参数说明：
  current_state: 当前状态(State类对象)
  NQ：N皇后的N
• 返回值说明：
  res_list: 还能用来放置皇后的位置(二维元组)
• 程序框图
  

3. 主程序

• 改变NQ的值以求解其他N皇后问题
• 程序框图
  

---

实现代码

import copy as cp
global count

count = 0

class State:
    N = 8
    current_grid = []  # 当前棋盘
    NewQ = (-1, -1)  # 当前棋子的位置
    parent_state = None  # 父状态
    deep = 0  # 状态深度

    def __init__(self, parent_state, Q_ij, NQ):
        if parent_state is None:
            self.N = NQ
            self.NewQ = Q_ij  # 当前棋子的位置
            self.parent_state = parent_state
            self.deep = 0
            self.current_grid = [[0 for i in range(self.N)] for j in range(self.N)]  # 当前棋盘
        else:
            self.N = NQ
            self.NewQ = Q_ij  # 当前棋子的位置
            self.parent_state = parent_state
            self.deep = self.parent_state.deep + 1
            self.current_grid = self.update_grid()  # 当前棋盘

    # 根据父状态和当前棋子位置，对当前棋盘的空余位置情况作更新
    def update_grid(self):
        line = self.NewQ[0]
        column = self.NewQ[1]
        if line != -1 and column != -1:
            if self.parent_state is None:
                next_grid = [[0 for i in range(self.N)] for j in range(self.N)]
                next_grid[line][column] = 10
            else:
                next_grid = cp.deepcopy(self.parent_state.current_grid)
                next_grid[line][column] = 10
                # 向上占位
                while line > 0:
                    next_grid[line - 1][column] = 1
                    line = line - 1
                line = self.NewQ[0]
                # 向下占位
                while line < self.N - 1:
                    next_grid[line + 1][column] = 1
                    line = line + 1
                line = self.NewQ[0]
                # 向左占位
                while column > 0:
                    next_grid[line][column - 1] = 1
                    column = column - 1
                column = self.NewQ[1]
                # 向右占位
                while column < self.N - 1:
                    next_grid[line][column + 1] = 1
                    column = column + 1
                column = self.NewQ[1]
                # 向左下角占位
                while column > 0 and line < self.N - 1:
                    next_grid[line + 1][column - 1] = 1
                    column = column - 1
                    line = line + 1
                line = self.NewQ[0]
                column = self.NewQ[1]
                # 向右下角占位
                while column < self.N - 1 and line < self.N - 1:
                    next_grid[line + 1][column + 1] = 1
                    column = column + 1
                    line = line + 1
            return next_grid
        else:
            print("no solution here!")
            return None

    # 打印当前棋盘
    def show_grid(self):
        for i in range(len(self.current_grid)):
            print("|", end="")
            for j in range(len(self.current_grid[i])):
                if self.current_grid[i][j] == 1:
                    print(" ", end=" ")
                else:
                    print("Q", end=" ")
            print("|")
        print("*****-----------------*****\n*****-----------------*****")


def get_extended_space_list(current_state, NQ):
    global count
    res_list = []
    if current_state.parent_state is None:
        line = 0
        for column in range(len(current_state.current_grid[line])):
            if current_state.current_grid[line][column] == 0:
                res_list.append((line, column))
    else:
        line = current_state.NewQ[0] + 1
        column = 0
        while column <= NQ - 1:
            count += 1
            if current_state.current_grid[line][column] >= 1:
                column = column + 1
            else:
                res_list.append((line, column))
                column = column + 1
    return res_list


NQ = 10
start_grid = [[0 for i in range(NQ)] for j in range(NQ)]
start_Q_ij = (-1, -1)
start_state = State(None, start_Q_ij, NQ)
start_space = get_extended_space_list(start_state, NQ)
open_list = []
solution = 0  # 记录成功结果的数量
search_sum = 0  # 记录找到单个结果时所用搜索次数
sum_in_total = 0  # 记录所有成功结果的搜索次数和
for i in range(len(start_space)):
    new = State(start_state, start_space[i], NQ)
    open_list.insert(0, new)
while len(open_list) != 0:
    # search_sum = search_sum + 1
    # print(len(open_list))
    current_state = open_list.pop(0)
    if current_state.deep == NQ:  # 如果当前状态的deep为NQ，说明所有棋子都放置完毕，即得到一种解
        solution = solution + 1
        print("this is solution No.", solution, sep="")
        current_state.show_grid()
        sum_in_total = sum_in_total + search_sum
        print("search_sum = ", search_sum)
        search_sum = 0
        continue
    new_space = get_extended_space_list(current_state, NQ)  # 得到可放置棋子的位置坐标列表
    for i in range(len(new_space)):
        search_sum += 1
        new_state = State(current_state, new_space[i], NQ)
        open_list.insert(0, new_state)

print("\n\n******************\nThere are ", solution, " solutions to ", NQ, "-Queens problem in total!", sep="")
# print("平均搜索次数为", sum_in_total / solution)
print("平均搜索次数为%.3f" % (count / solution))
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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141