如何在国际象棋比赛中猜出皇后的位置

Question

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

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! ")

Answer 1

这是一个很有名的谜题，被称为N皇后问题。这是 Eight queens puzzle.

的一般情况

有几个solutions in Python on Rosetta Code, including this very elegant one from 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 )

Raymond explains how this works:

With the solution represented as a vector with one queen in each row, we don't have to check to see if two queens are on the same row. By using a permutation generator, we know that no value in the vector is repeated, so we don't have to check to see if two queens are on the same column. Since rook moves don't need to be checked, we only need to check bishop moves.

The technique for checking the diagonals is to add or subtract the column number from each entry, so any two entries on the same diagonal will have the same value (in other words, the sum or difference is unique for each diagnonal). Now all we have to do is make sure that the diagonals for each of the eight queens are distinct. So, we put them in a set (which eliminates duplicates) and check that the set length is eight (no duplicates were removed).

Any permutation with non-overlapping diagonals is a solution. So, we print it and continue checking other permutations.

如何在国际象棋比赛中猜出皇后的位置

How to guess the positions of the queens in a chess game

python

chess

n-queens

python-3.x

python-chess