时间戳

首页 > 解决方案 > 我对这个 python 编程练习感到非常困惑，谁能告诉我有什么问题吗？

python - 我对这个 python 编程练习感到非常困惑，谁能告诉我有什么问题吗？

问题描述

我目前正在做一个python练习，当给定一个大小为 的棋盘时n，它是返回一个具有最大皇后数的解决方案，以便没有两个皇后相互攻击。因此，一个解决方案要求没有两个皇后共享相同的行、列或对角线。

我目前能够生成板，但问题出现在我的代码的第 20 行，其中if bd not in soln. 由于某种我无法识别的原因，该代码行无法正确执行，并且正确地将正确的板附加到我的解决方案集中。

如果有人可以帮助确定问题，我将不胜感激。

import random

def queensol(n):
    """Find the number of solutions to placing Queens on a chessboard of size n"""
    size = n
    rng = random.Random()
    tries = 0
    bd = list(range(size))
    soln = []

    while True:
        tries += 1
        rng.shuffle(bd)
        correct = 0
        for queen_index in range(size):
            if queen_noclash(bd, queen_index):
                correct += 1
        board_valid = correct == size
        if board_valid:
            if bd not in soln:
                soln.append(bd)
                print(soln)

def no_diagonal(x1, y1, x2, y2):
    dx = abs(x1-x2)
    dy = abs(y1-y2)
    # print('dx',dx)
    # print('dy',dy)
    if dx == dy:
        return False
    else:
        return True


def queen_noclash(bd, queen):
    correct = 0
    for left_queen in range(queen):
        left_queen_x = left_queen
        left_queen_y = bd[left_queen]
        queen_x = queen
        queen_y = bd[queen]
        if no_diagonal(left_queen_x, left_queen_y, queen_x, queen_y):
            correct += 1
    if correct == queen:
        return True
    else:
        return False


queensol(4)

标签： pythonalgorithmgraph-algorithmn-queens

解决方案

问题是 bd 是一个对象。您正在将相同的对象附加到板上。因此，即使 bd 更改bd not in soln总是会给出 False ，因为您正在比较同一个对象。每次附加到 soln 数组时，都应该使用 list(bd) 创建一个新对象。我已经在下面的代码中解决了这个问题。

import random

def queensol(n):
    """Find the number of solutions to placing Queens on a chessboard of size n"""
    size = n
    rng = random.Random()
    tries = 0
    bd = list(range(size))
    soln = []

    while True:
        tries += 1
        rng.shuffle(bd)
        correct = 0
        for queen_index in range(size):
            if queen_noclash(bd, queen_index):
                correct += 1
        board_valid = correct == size
        if board_valid:
            if bd not in soln:
                soln.append(list(bd))
                print(soln)

def no_diagonal(x1, y1, x2, y2):
    dx = abs(x1-x2)
    dy = abs(y1-y2)
    # print('dx',dx)
    # print('dy',dy)
    if dx == dy:
        return False
    else:
        return True


def queen_noclash(bd, queen):
    correct = 0
    for left_queen in range(queen):
        left_queen_x = left_queen
        left_queen_y = bd[left_queen]
        queen_x = queen
        queen_y = bd[queen]
        if no_diagonal(left_queen_x, left_queen_y, queen_x, queen_y):
            correct += 1
    if correct == queen:
        return True
    else:
        return False


queensol(4)

推荐阅读