爬山法求解八皇后问题_爬山搜索算法解决八皇后问题

import random, copy, time

"""

解决8皇后问题

初始化

随机生成皇后位置,使其不同列、不同行只有一个

"""

def init():

    # 随机生成皇后位置,使其不同列、不同行只有一个

    status = []

    for r in range(8):

        while len(status) <= 8:

            c = random.randint(0, 7)

            if c not in [mm[1] for mm in status]:

                status.append((r, c))

                break

    return status

"""

遍历所有皇后

计算有冲突的皇后坐标(同一行，同一列，斜边)

计算整个棋盘冲突的数量

假设初始化传入皇后位置：

[(0, 3), (1, 6), (2, 7), (3, 0), (4, 2), (5, 1), (6, 4), (7, 5)]

"""

def conflict(status):

    num = 0  # 存储冲突数量

    conflict_chess = []

    for pos in status:

        for other_pos in status:

            if pos == other_pos or pos in conflict_chess:

                continue

            elif pos[0] == other_pos[0] or pos[1] == other_pos[1] or abs(pos[0] - other_pos[0]) == abs(

                    pos[1] - other_pos[1]):

                num += 1

                conflict_chess.append(pos)

    return num, conflict_chess

"""

遍历所有空位

计算当行的皇后移动到此空位时整个棋盘的冲突值

会得出8*8-8 = 56个冲突值

也就是56种移动方法

选择冲突值最小的一种进行移动

"""

def move_chess(status):

    empty_pos = {}  # 用字典保存所有空位冲突值

    for r in range(8):

        for c in range(8):

            if (r, c) not in status:

                new_status = copy.deepcopy(status)

                new_status[r] = (r, c)

                empty_pos[(r, c)] = conflict(new_status)[0]

            else:

                continue

    return empty_pos

"""

循环获取冲突数量

若数量>1,执行move_chess

指导冲突数量=0，此时寻找到最佳位置

"""

def climbing(status):

    # 获取当前皇后位置的冲突值

    conflict_num = conflict(status)[0]

    # 设置循环次数，避免一直循环，冲突值一直无法降到最低0时，自动跳出循环

    # 设置移动皇后500次，如果找不到正确位置就重新初始化皇后位置

    loop_cnt = 0

    while conflict_num != 0 and loop_cnt < 500:

        # 获取所有空位冲突值

        empty_pos = move_chess(status)

        min_value = min(empty_pos.values())

        # 获取最小冲突值对应的key 即坐标pos

        min_pos_ls = []

        for k, v in empty_pos.items():

            # print(v, min_value)

            if v == min_value and (k not in min_pos_ls):

                min_pos_ls.append(k)

        # print(min_pos_ls, min_value)

        # print(status)

        # 随机取一个空位点，与当前同一行皇后交换位置，然后计算所有空位置的冲突值和当前棋局内皇后自身冲突值

        i = random.randint(0, len(min_pos_ls) - 1)

        status[min_pos_ls[i][0]] = min_pos_ls[i]

        conflict_num = conflict(status)[0]

        loop_cnt += 1

    return status, loop_cnt

if __name__ == '__main__':

    # 这一个随机数会导致一直找不到最高点

    # status = [(0, 0), (1, 2), (2, 4), (3, 3), (4, 1), (5, 5), (6, 7), (7, 6)]

    # climbing(status)

    """

    生成随机位置，迭代600次尽可能多的找出八皇后不同位置

    """

    start = time.time()

    all_pos = []

    for i in range(600):

        status = init()

        # 设置loop_cnt防止一直陷入死循环无法找到最佳点

        # 如果一直找不到就跳出来并且重新生成初始位置

        status, loop_cnt = climbing(status)

        # print(loop_cnt)

        if loop_cnt == 500:

            continue

        elif status not in all_pos:

            all_pos.append(status)

    end = time.time()

    print("一共找到{}组八皇后位置,共耗时{}s".format(len(all_pos), end - start))

    for pos in all_pos:

        print(pos)

目录：

代码段一：导包

代码段二：函数定义

代码段三：调用运行

导包

import numpy as np

import matplotlib

import matplotlib.pyplot as plt

#设定中文字符集，解决绘图时中文乱码问题

matplotlib.rcParams['font.sans-serif'] = ['SimHei']

函数定义

#放置函数,参数为已放置的皇后数量

def Queen_set(n):

    global num

    global queen_list

    queen_col_loc=[i+1 for i in queen_list]

    #方案可行

    if n==8:

        print("第"+str(num)+"种:",(1,queen_col_loc[0]),(2,queen_col_loc[1]),(3,queen_col_loc[2]),(4,queen_col_loc[3])

        ,(5,queen_col_loc[4]),(6,queen_col_loc[5]),(7,queen_col_loc[6]),(8,queen_col_loc[7]))

        #绘制当前的皇后摆放方案

        plot_chess(queen_list)

        num+=1

        return

    else:

        #检查当前行哪一个位置可以放置

        for i in range(8):

            if check(n,i):

                queen_list.append(i)#在当前位置放置皇后

                Queen_set(n+1)#递归放置下一个皇后

                queen_list.pop()#回溯，尝试当前行的其他皇后摆放方法

#检测，传入参数为皇后摆放的位置

def check(row,col):

    if row==0:

        return True

    else:

        #检测列是否与之前摆放的皇后有冲突

        for i in range(row):

            if col==queen_list[i]:

                return False

            #检测对角线是否有冲突,分为主对角线和副对角线，满足直线方程x+y=n 和x-y=n

            elif i+queen_list[i]==row+col or i-queen_list[i]==row-col:

                return False

        return True

#绘制棋盘并保存求解结果

def plot_chess(result):

    global num

    map=np.zeros((8,8))

    for i in range(8):

        map[i,result[i]]=1

    cmap = matplotlib.colors.LinearSegmentedColormap.from_list('my_camp', ['white', 'black'], 2)

    plt.imshow(map, cmap=cmap)

    plt.title("第" + str(num) + "种解法", fontsize=16)

    plt.xticks([])

    plt.yticks([])

    plt.savefig('C:/Users/14767/Desktop/expriment/'+str(num)+'.png') #保存图片的路径,自行修改

调用运行

#从第一行开始逐行放置皇后，将皇后的列坐标放入列表中

queen_list=[]

#当前的方案数

num=1

Queen_set(0)