1

我最近参加了一个编程比赛，我能够及时回答七道题中的六道题。最后一个问题是：“从用户那里取一个数字，用给定数字的幂做一个棋盘，放置尽可能多的皇后，并以某种方式排列皇后，使它们不会在水平、垂直方向上相互威胁和对角线。” 因此，例如，如果用户输入4 ，那么4x4 (16)棋盘中将有4 个皇后。好吧，对于垂直和水平部分，我能够检查它们是否在同一列中，对于对角线部分，我使用了非常糟糕的 while 循环组合，然后将国际象棋游戏中的所有保留位置添加到列表中。问题是我使用随机生成索引的模块，然后检查它们是否在保留数字中，然后再试一次，直到它不存在，所以发生的情况是这个国际象棋游戏只有少数组合，如果开始索引错误，程序会变得漂亮永远停留在while循环中。我曾想过从最后一行到第一行，但即便如此，我仍在使用随机索引。如何让程序计算皇后的位置，而不是随机输入一个数字并查看它是否有效？我的代码：（如果我的代码有其他问题，请指出）： num=4 的唯一可能组合

import random

# in the program you had to put '1' as the position of the queens and put '0' as the empty places on the board
# and also, if the user entered a number less than 4 the combination would not have been possible

num = int(input("Enter number: "))
if num >= 4:
    arr = [[0 for _ in range(num)] for _ in range(num)]
    reserved_num = []
    oblique = []
    for i in range(num):
        j = random.randint(0, num - 1)
        while [i, j] in reserved_num:
            j = random.randint(0, num - 1)
        arr[i][j] = 1
        for rows in range(num):
            reserved_num.append([rows, j])
        if i < num-1:
            inc = 0
            if j == num-1:
                while j-inc > 0 and i+inc < num-1:
                    inc += 1
                    oblique.append([i+inc, j-inc])
                else:
                    inc = 0
            elif j == 0:
                while j+inc < num-1 and i+inc < num-1:
                    inc+= 1
                    oblique.append([i+inc, j+inc])
                else:
                    inc = 0
            else:
                while j+inc < num-1 and i+inc < num-1:
                    inc+= 1
                    oblique.append([i+inc, j+inc])
                else:
                    inc = 0
                while j-inc > 0 and i+inc < num-1:
                    inc += 1
                    oblique.append([i+inc, j-inc])
                else:
                    inc = 0
        for res in oblique:
            reserved_num.append(res)

    for items in arr:
        print(items)
else:
    print("Not Possible! ")
4

1 回答 1

3

这是一个非常有名的难题，被称为 N 皇后问题。这是八皇后之谜的一般情况。

在 Python on Rosetta Code 上有一些解决方案，包括Raymond Hettinger的这个非常优雅的解决方案：

from itertools import permutations
 
n = 8
cols = range(n)
for vec in permutations(cols):
    if n == len(set(vec[i]+i for i in cols)) \
         == len(set(vec[i]-i for i in cols)):
        print ( vec )

雷蒙德解释了这是如何工作的：

将解决方案表示为每行有一个皇后的向量，我们不必检查两个皇后是否在同一行。通过使用置换生成器，我们知道向量中没有重复的值，因此我们不必检查两个皇后是否在同一列上。由于不需要检查车的移动，我们只需要检查象的移动。

检查对角线的技术是从每个条目中添加或减去列号，因此同一对角线上的任何两个条目将具有相同的值（换句话说，每个对角线的和或差都是唯一的）。现在我们要做的就是确保八个皇后中每一个的对角线都是不同的。因此，我们将它们放在一个集合中（这消除了重复项）并检查集合长度是否为 8（没有删除重复项）。

任何具有非重叠对角线的排列都是一种解决方案。因此，我们打印它并继续检查其他排列。

于 2020-12-27T12:14:24.270 回答