八数码问题的三种解法_本关任务:八数码问题是在一个3×3的棋盘上有1 8位数字随机分布,以及一个空格,

作者：盐析白兔 | 2024-06-20 06:24:24

踩

本关任务:八数码问题是在一个3×3的棋盘上有1 8位数字随机分布,以及一个空格,

北民大人工智能作业，其他相关作业资料和问题可留言交流
这里没有用课本上的open表和close表的方式，这个问题完全可以看图找规律解出来，而且三个代码(广度、A、A*)没有多少区别，代码相似度极高，将每个操作步骤抽成方法后A和A*就只有一个入队规则不一样而已，广度就是直接去掉这个规则。

这里的规律就是根据课本上给出的启发公式(格式为F=A+B；A是棋盘所在的深度；B在A算法中是不在位的元素个数，在A*算法中就是所有元素要移动的步数和)来设计入队规则，因为同一层上的棋盘一起考虑，所以落实到代码中A部分的深度属性就没用了，因为同一层上的这个参数都是一样的，只需考虑参数B就行。另外就是从第二层上的棋盘开始，往下的分支会出现它父节点的父节点棋盘状态，这个要剔除掉，否则会陷入无限的循环当中。

关于自己代码的评价：优点是便于理解，更贴合初学者或者是没有参考课本思路的人的想法；个人觉得比课本上的open表close表的方式要简单的多，其次目前A和A算法运行效率要比网上用open、close表的代码强非常多。缺点是：在最初的设想时没有考虑周全，棋盘的表示已经确定，但是发现棋盘分支会出现它父节点的父节点棋盘状态时，想用回溯的方法就需要大的改动，所以干脆用一个列表存储所有出现过的棋盘，后续棋盘状态不允许出现列表中已有的棋盘，以此来回避回溯问题，这就带来了效率上的漏洞，A和A因为有入队条件限制，所以感觉不出问题，但是放到广度算法里边，有些棋盘状态的演算，跑了14个小时依然没有结果，这个问题回随着演算步骤的加深疯狂的放大。解决办法自然是使用回溯方式，为每个棋盘增加一个父节点属性，用来存储父棋盘，每次只要根据棋盘的父节点属性找到上两步的棋盘与之对比即可，就无需比对所有出现过的棋盘了。

这里先给出三个实现代码，下边再附上课本上的三幅图已经这三个代码大致的流程走向图。

广度算法

import numpy as np
import copy
import time

"""
1. 空洞用数字0表示，其他各个位置用1...8表示
2. 同一层deep都一样，所以直接不考虑
3. 注意深浅拷贝问题
4. 注意闭包问题
5. 注意stack不是栈，是队列queue，temp是step代表步数，懒得改了
6. print("this state no answer!")已经没用了，最初是验证是否会出现没解的情况，现在有了judge_have_answer()方法
7. 使用规则：输入初始和最终棋盘元素，横着从左到右挨着输入，空洞为0，其他为1...8
8. 注意日期打印时.format()方式不能使用
"""

final_checkerboard = np.zeros((3, 3), dtype=int)  # 记录最终的棋盘状态
total_stack = []
final_stack = []
mid_stack = []
step = 0
start_time = 0

def create_checkerboard(checkerboard):
    order = 0
    for i in range(3):
        for j in range(3):
            order += 1
            element = int(input("请输入第{}个数：".format(order)))
            checkerboard[i][j] = element

def move_checkerboard(before_state):
    global mid_stack

    # 首先确定空洞的位置
    position = np.argwhere(before_state == 0)
    first_position = position[0][0]
    second_position = position[0][1]

    if first_position == 0:
        if second_position == 0:
            zuoyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        elif second_position == 2:
            youyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        else:
            youyi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
    elif first_position == 2:
        if second_position == 0:
            xiayi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
        elif second_position == 2:
            youyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
        else:
            youyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
    else:
        if second_position == 0:
            zuoyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        elif second_position == 2:
            xiayi(before_state, first_position, second_position)
            youyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        else:
            youyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)

def equal_all_position(first_checkerboard):
    for t in total_stack:
        num = 0
        for i in range(3):
            for j in range(3):
                if first_checkerboard[i][j] == t[i][j]:
                    num += 1
        if num == 9:
            return 0
        else:
            pass

    return 1


def shangyi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position + 1][second_position]  # 数字上移
    after_state[first_position + 1][second_position] = 0
    tap = equal_all_position(after_state)
    if tap:
        statistics(after_state)  # 这里保留是为了判断是否达到最终状态
        ruzhan(after_state)

def xiayi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position -1][second_position]  # 数字下移
    after_state[first_position - 1][second_position] = 0
    tap = equal_all_position(after_state)
    if tap:
        statistics(after_state)
        ruzhan(after_state)

def zuoyi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position][second_position + 1]  # 数字左移
    after_state[first_position][second_position + 1] = 0
    tap = equal_all_position(after_state)
    if tap:
        statistics(after_state)
        ruzhan(after_state)

def youyi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position][second_position - 1]  # 数字右移
    after_state[first_position][second_position - 1] = 0
    tap = equal_all_position(after_state)
    if tap:
        statistics(after_state)
        ruzhan(after_state)

def ruzhan(checkerboard):
    global mid_stack
    global step
    step += 1
    print(step)
    mid_stack.append(checkerboard)
    total_stack.append(checkerboard)

    print(checkerboard)
    print("====================")

# 用来统计当前棋盘有多少个元素不在目标位置
def statistics(checkboard):
    number = 0

    for i in range(3):
        for j in range(3):
            if checkboard[i][j] == final_checkerboard[i][j]:
                number += 1

    if number == 9:
        print("最终结果为：")
        print(checkboard)
        end_time = time.time()
        print("end_time=",end_time)
        global start_time
        print("用时=",end_time - start_time)
        exit()
    return 9 - number

def iterator_all_elements(final_stack):
    for i in final_stack:
        move_checkerboard(i)

# 这里的教训告诉我们没事不要瞎用不熟悉的库，最后还是numpy转list
def judge_have_answer(initial_checkerboard):
    initial_checkerboard_result = 0
    final_checkerboard_result = 0

    initial_checkerboard_backup = copy.deepcopy(initial_checkerboard)
    final_checkerboard_backup = copy.deepcopy(final_checkerboard)

    new_initial = initial_checkerboard_backup.reshape((1,9)).tolist()[0]
    new_final = final_checkerboard_backup.reshape((1,9)).tolist()[0]

    new_initial.remove(0)
    new_final.remove(0)

    for i in range(8):
        for j in range(i):
            if new_initial[j] > new_initial[i]:
                initial_checkerboard_result += 1

    for i in range(8):
        for j in range(i):
            if new_final[j] > new_final[i]:
                final_checkerboard_result += 1

    return initial_checkerboard_result, final_checkerboard_result

def main():
    initial_checkerboard = np.zeros((3, 3), dtype=int) #记录初始的棋盘状态

    print("空棋盘如下：")
    print(initial_checkerboard)

    print("请输入初始状态棋盘数据：")
    create_checkerboard(initial_checkerboard)

    print("初始棋盘状态如下：")
    print(initial_checkerboard)

    print("请输入终止状态棋盘数据：")
    create_checkerboard(final_checkerboard)

    print("最终棋盘状态如下：")
    print(final_checkerboard)
    print("-------------------")

    number1, number2 = judge_have_answer(initial_checkerboard)

    if (number1 % 2) != (number2 % 2):
        print("该起始状态无法达到最终状态!")
        exit()

    global start_time
    start_time = time.time()
    print("start_time=", start_time)

    statistics(initial_checkerboard)

    global final_stack
    global mid_stack
    mid_checkerboard = copy.deepcopy(initial_checkerboard)
    final_stack.append(mid_checkerboard)
    total_stack.append(mid_checkerboard)
    while(len(final_stack) != 0):
        iterator_all_elements(final_stack)
        final_stack = copy.deepcopy(mid_stack)
        mid_stack = []
    print("this state no answer!")

if __name__ == '__main__':
    main()
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230

A算法

import numpy as np
import copy

"""
1. 空洞用数字0表示，其他各个位置用1...8表示
2. 同一层deep都一样，所以直接不考虑
3. 注意深浅拷贝问题
4. 注意闭包问题
5. 注意stack不是栈，是队列queue，temp是step代表步数，懒得改了
6. print("this state no answer!")已经没用了，最初是验证是否会出现没解的情况，现在有了judge_have_answer()方法
7. 使用规则：输入初始和最终棋盘元素，横着从左到右挨着输入，空洞为0，其他为1...8
"""

final_checkerboard = np.zeros((3, 3), dtype=int)  # 记录最终的棋盘状态
min_element_number = 0
total_stack = []
final_stack = []
mid_stack = []
temp = 0

def create_checkerboard(checkerboard):
    order = 0
    for i in range(3):
        for j in range(3):
            order += 1
            element = int(input("请输入第{}个数：".format(order)))
            checkerboard[i][j] = element

def move_checkerboard(before_state):
    # 首先确定空洞的位置
    position = np.argwhere(before_state == 0)
    first_position = position[0][0]
    second_position = position[0][1]

    if first_position == 0:
        if second_position == 0:
            zuoyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        elif second_position == 2:
            youyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        else:
            youyi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
    elif first_position == 2:
        if second_position == 0:
            xiayi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
        elif second_position == 2:
            youyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
        else:
            youyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
    else:
        if second_position == 0:
            zuoyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        elif second_position == 2:
            xiayi(before_state, first_position, second_position)
            youyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        else:
            youyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)

def equal_all_position(first_checkerboard):
    for t in total_stack:
        num = 0
        for i in range(3):
            for j in range(3):
                if first_checkerboard[i][j] == t[i][j]:
                    num += 1
        if num == 9:
            return 0
        else:
            pass
    return 1

def shangyi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position + 1][second_position]  # 数字上移
    after_state[first_position + 1][second_position] = 0
    tap = equal_all_position(after_state)
    if tap:
        number = statistics(after_state)
        ruzhan(after_state, number)

def xiayi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position -1][second_position]  # 数字下移
    after_state[first_position - 1][second_position] = 0
    tap = equal_all_position(after_state)
    if tap:
        number = statistics(after_state)
        ruzhan(after_state, number)

def zuoyi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position][second_position + 1]  # 数字左移
    after_state[first_position][second_position + 1] = 0
    tap = equal_all_position(after_state)
    if tap:
        number = statistics(after_state)
        ruzhan(after_state, number)

def youyi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position][second_position - 1]  # 数字右移
    after_state[first_position][second_position - 1] = 0
    tap = equal_all_position(after_state)
    if tap:
        number = statistics(after_state)
        ruzhan(after_state, number)

def ruzhan(checkerboard,number):
    global mid_stack
    global min_element_number
    if len(mid_stack) == 0:
        mid_stack.append(checkerboard)
        total_stack.append(checkerboard)
        min_element_number = number
    else:
        if number > min_element_number:
            print("未插入")
        elif number == min_element_number:
            mid_stack.append(checkerboard)
            total_stack.append(checkerboard)
            min_element_number = number
        elif number < min_element_number:
            mid_stack = []
            mid_stack.append(checkerboard)
            total_stack.append(checkerboard)
            min_element_number = number

    print(checkerboard)
    print("====================")

# 用来统计当前棋盘有多少个元素不在目标位置
def statistics(checkboard):
    number = 0

    for i in range(3):
        for j in range(3):
            if checkboard[i][j] == final_checkerboard[i][j]:
                number += 1

    if number == 9:
        print("最终结果为：")
        print(checkboard)
        exit()
    return 9 - number

def iterator_all_elements(final_stack):
    for i in final_stack:
        move_checkerboard(i)

# 这里的教训告诉我们没事不要瞎用不熟悉的库，最后还是numpy转list
def judge_have_answer(initial_checkerboard):
    initial_checkerboard_result = 0
    final_checkerboard_result = 0

    initial_checkerboard_backup = copy.deepcopy(initial_checkerboard)
    final_checkerboard_backup = copy.deepcopy(final_checkerboard)

    new_initial = initial_checkerboard_backup.reshape((1,9)).tolist()[0]
    new_final = final_checkerboard_backup.reshape((1,9)).tolist()[0]

    new_initial.remove(0)
    new_final.remove(0)

    for i in range(8):
        for j in range(i):
            if new_initial[j] > new_initial[i]:
                initial_checkerboard_result += 1

    for i in range(8):
        for j in range(i):
            if new_final[j] > new_final[i]:
                final_checkerboard_result += 1

    return initial_checkerboard_result, final_checkerboard_result

def main():
    initial_checkerboard = np.zeros((3, 3), dtype=int) #记录初始的棋盘状态

    print("空棋盘如下：")
    print(initial_checkerboard)

    print("请输入初始状态棋盘数据：")
    create_checkerboard(initial_checkerboard)

    print("初始棋盘状态如下：")
    print(initial_checkerboard)

    print("请输入终止状态棋盘数据：")
    create_checkerboard(final_checkerboard)

    print("最终棋盘状态如下：")
    print(final_checkerboard)
    print("-------------------")

    number1, number2 = judge_have_answer(initial_checkerboard)

    if (number1 % 2) != (number2 % 2):
        print("该起始状态无法达到最终状态!")
        exit()

    statistics(initial_checkerboard)

    global final_stack
    global mid_stack
    mid_checkerboard = copy.deepcopy(initial_checkerboard)
    final_stack.append(mid_checkerboard)
    total_stack.append(mid_checkerboard)
    global temp
    while(len(final_stack) != 0):
        temp += 1
        iterator_all_elements(final_stack)
        final_stack = copy.deepcopy(mid_stack)
        mid_stack = []
    print("this state no answer!")

if __name__ == '__main__':
    main()
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230

A*算法

import numpy as np
import copy

"""
1. 空洞用数字0表示，其他各个位置用1...8表示
2. 同一层deep都一样，所以直接不考虑
3. 注意深浅拷贝问题
4. 注意闭包问题
5. 注意stack不是栈，是队列queue，temp是step代表步数，懒得改了
6. print("this state no answer!")已经没用了，最初是验证是否会出现没解的情况，现在有了judge_have_answer()方法
7. 使用规则：输入初始和最终棋盘元素，横着从左到右挨着输入，空洞为0，其他为1...8
"""

final_checkerboard = np.zeros((3, 3), dtype=int)  # 记录最终的棋盘状态
min_element_number = 0
total_stack = []
final_stack = []
mid_stack = []
temp = 0
total_step = 0

def create_checkerboard(checkerboard):
    order = 0
    for i in range(3):
        for j in range(3):
            order += 1
            element = int(input("请输入第{}个数：".format(order)))
            checkerboard[i][j] = element

def move_checkerboard(before_state):
    # 首先确定空洞的位置
    position = np.argwhere(before_state == 0)
    first_position = position[0][0]
    second_position = position[0][1]

    if first_position == 0:
        if second_position == 0:
            zuoyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        elif second_position == 2:
            youyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        else:
            youyi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
    elif first_position == 2:
        if second_position == 0:
            xiayi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
        elif second_position == 2:
            youyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
        else:
            youyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
    else:
        if second_position == 0:
            zuoyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        elif second_position == 2:
            xiayi(before_state, first_position, second_position)
            youyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)
        else:
            youyi(before_state, first_position, second_position)
            xiayi(before_state, first_position, second_position)
            zuoyi(before_state, first_position, second_position)
            shangyi(before_state, first_position, second_position)

def equal_all_position(first_checkerboard):
    for t in total_stack:
        num = 0
        for i in range(3):
            for j in range(3):
                if first_checkerboard[i][j] == t[i][j]:
                    num += 1
        if num == 9:
            return 0
        else:
            pass
    return 1

def step_total_number(checkerboard):
    global final_checkerboard
    global total_step
    total_step = 0
    for i in range(3):
        for j in range(3):
            key = checkerboard[i][j]
            if (checkerboard[i][j] == 0):
                continue
            position = np.argwhere(final_checkerboard == key)
            # 这里是获取到终止状态的位置
            horizontal_position = position[0][0]
            vertical_position = position[0][1]
            hang_step = abs(horizontal_position - i)
            lie_step = abs(vertical_position - j)
            total_step += hang_step + lie_step
    if total_step == 0:
        print("最终结果为：")
        print(checkerboard)
        exit()
    return total_step

def shangyi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position + 1][second_position]  # 数字上移
    after_state[first_position + 1][second_position] = 0
    tap = equal_all_position(after_state)
    if tap:
        number = step_total_number(after_state)
        ruzhan(after_state, number)

def xiayi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position -1][second_position]  # 数字下移
    after_state[first_position - 1][second_position] = 0
    tap = equal_all_position(after_state)
    if tap:
        number = step_total_number(after_state)
        ruzhan(after_state, number)

def zuoyi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position][second_position + 1]  # 数字左移
    after_state[first_position][second_position + 1] = 0
    tap = equal_all_position(after_state)
    if tap:
        number = step_total_number(after_state)
        ruzhan(after_state, number)

def youyi(checkerboard, first_position, second_position):
    after_state = copy.deepcopy(checkerboard)
    after_state[first_position][second_position] = after_state[first_position][second_position - 1]  # 数字右移
    after_state[first_position][second_position - 1] = 0
    tap = equal_all_position(after_state)
    if tap:
        number = step_total_number(after_state)
        ruzhan(after_state, number)

def ruzhan(checkerboard,number):
    global mid_stack
    global min_element_number
    if len(mid_stack) == 0:
        mid_stack.append(checkerboard)
        total_stack.append(checkerboard)
        min_element_number = number
    else:
        if number > min_element_number:
            print("未插入")
        elif number == min_element_number:
            mid_stack.append(checkerboard)
            total_stack.append(checkerboard)
            min_element_number = number
        elif number < min_element_number:
            mid_stack = []
            mid_stack.append(checkerboard)
            total_stack.append(checkerboard)
            min_element_number = number

    print(checkerboard)
    print("====================")

def iterator_all_elements(final_stack):
    for i in final_stack:
        move_checkerboard(i)

# 这里的教训告诉我们没事不要瞎用不熟悉的库，最后还是numpy转list
def judge_have_answer(initial_checkerboard):
    initial_checkerboard_result = 0
    final_checkerboard_result = 0

    initial_checkerboard_backup = copy.deepcopy(initial_checkerboard)
    final_checkerboard_backup = copy.deepcopy(final_checkerboard)

    new_initial = initial_checkerboard_backup.reshape((1,9)).tolist()[0]
    new_final = final_checkerboard_backup.reshape((1,9)).tolist()[0]

    new_initial.remove(0)
    new_final.remove(0)

    for i in range(8):
        for j in range(i):
            if new_initial[j] > new_initial[i]:
                initial_checkerboard_result += 1

    for i in range(8):
        for j in range(i):
            if new_final[j] > new_final[i]:
                final_checkerboard_result += 1

    return initial_checkerboard_result, final_checkerboard_result

def main():
    initial_checkerboard = np.zeros((3, 3), dtype=int) #记录初始的棋盘状态

    print("空棋盘如下：")
    print(initial_checkerboard)

    print("请输入初始状态棋盘数据：")
    create_checkerboard(initial_checkerboard)

    print("初始棋盘状态如下：")
    print(initial_checkerboard)

    print("请输入终止状态棋盘数据：")
    create_checkerboard(final_checkerboard)

    print("最终棋盘状态如下：")
    print(final_checkerboard)
    print("-------------------")

    number1, number2 = judge_have_answer(initial_checkerboard)

    if (number1 % 2) != (number2 % 2):
        print("该起始状态无法达到最终状态!")
        exit()

    step_total_number(initial_checkerboard)

    global final_stack
    global mid_stack
    mid_checkerboard = copy.deepcopy(initial_checkerboard)
    final_stack.append(mid_checkerboard)
    total_stack.append(mid_checkerboard)
    global temp
    while(len(final_stack) != 0):
        temp += 1
        iterator_all_elements(final_stack)
        final_stack = copy.deepcopy(mid_stack)
        mid_stack = []
    print("this state no answer!")

if __name__ == '__main__':
    main()
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238

程序大致的流程走向图
在这里插入图片描述
相关方法的简单介绍：

课本中广度相关部分图片：

A算法：

A*算法

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】