随机重启爬山法实现八皇后问题的python实现

以下是随机重启爬山法实现八皇后问题的Python代码：

import random

def generate_board():
    board = [0] * 8
    for i in range(8):
        board[i] = random.randint(0, 7)
    return board

def count_attacks(board):
    attacks = 0
    for i in range(8):
        for j in range(i+1, 8):
            if board[i] == board[j]:
                attacks += 1
            elif abs(board[i] - board[j]) == j - i:
                attacks += 1
    return attacks

def random_restart_hill_climbing():
    best_board = generate_board()
    while True:
        board = generate_board()
        while True:
            attacks = count_attacks(board)
            if attacks == 0:
                return board
            next_board = list(board)
            min_attacks = attacks
            for i in range(8):
                for j in range(8):
                    if j != board[i]:
                        next_board[i] = j
                        new_attacks = count_attacks(next_board)
                        if new_attacks < min_attacks:
                            min_attacks = new_attacks
                            board = list(next_board)
            if min_attacks >= attacks:
                break
        if count_attacks(board) < count_attacks(best_board):
            best_board = list(board)
            
board = random_restart_hill_climbing()
print("Solution: ")
for i in range(8):
    for j in range(8):
        if board[i] == j:
            print("Q ", end="")
        else:
            print(". ", end="")
    print()

该代码首先定义了三个函数：

- `generate_board`：生成一个随机的棋盘布局；
- `count_attacks`：计算棋盘中皇后之间的攻击数；
- `random_restart_hill_climbing`：随机重启爬山法求解八皇后问题。

`random_restart_hill_climbing` 函数首先生成一个随机的棋盘布局，然后进行爬山求解。如果得到一个局面，其攻击数为 0，则说明已经找到了一个解，直接返回该棋盘布局。否则，就在当前局面的邻居中，选择一个攻击数最小的邻居，并将其作为下一次迭代的起点。如果没有比当前局面更优的邻居，则说明已经达到了局部最优解，需要重新开始一次随机搜索。在所有的随机搜索中，记录下攻击数最小的棋盘布局，作为最终的解。

最后，程序输出找到的八皇后解。每行输出一个棋子位置，用 "Q" 表示皇后，用 "." 表示空位。