用Python随机解决棋盘上的皇后

Question

这个想法是尝试通过将皇后完全随机地放置在棋盘的每一行中来尝试解决“皇后问题”，并看看需要重复多少次才能解决它。棋盘可以是任何尺寸。

我的想法是创建 s 个列表，每个列表包含 s 个“空”字符（下划线）。然后为每一行随机选择一个位置来插入皇后（“I”值），然后标记下面和对角线向下的所有位置（我将逐行进行，因此我不必担心上面的行）与 X。如果在任何迭代中随机选择的皇后位置与该行中任何 X 的位置匹配，我从头开始新的棋盘。

我有这样的东西，但它似乎卡在第 19 行（用注释标记），但它没有给我任何错误。有什么问题吗？另外，我的解决方案（除了该行）正确吗？

from random import *


#Success flag
success = 0

#Trials counter
trials = 0


s = input ("enter board size\n")
s = int(s)
block = 1 #blockade
queen = 2 #queen
board = [[0 for x in range(s)] for y in range(s)] 

while success == 0:
    for y in range (0, s-1):
        pos = randint(0,s-1)    #line 19
        if board[y][pos] != block:
            board[y][pos] = queen
            a = 1
            for z in range (y, s-2):
                board[z + 1][pos] = block
                if pos - a >= 0:
                    board[z + 1][pos - a] = block
                if pos + a <= s-1:
                    board[z + 1][pos + a] = block
                a = a + 1
            success = 1
        else:
            success = 0


#Printing board
for y in range (0, s-1):
    print (board[y])

print ("Number of trials:\n")
print (trials)

Answer 1

一些问题：

• range

  函数的第二个参数代表将不会访问的第一个数字，所以大多数时候你都会有一个短的时间。
• 尝试失败时，您需要在 y 上退出循环：您不想继续下一行，而是重新启动
• 您需要在每次失败的尝试后重置主板，或者在每次尝试之前添加：
如果经过多次迭代后仍未找到解决方案，您应该建立一些安全退出机制，否则您将面临陷入困境的风险。对于输入1、2或3，无解。
试验次数永远不会增加
不要盲目选择位置，最好只从可用位置中选择（不要被封锁），否则你将进行惊人的试验次数：对于 8 号，需要 100 000 次试验并不罕见没有这个过滤！

查看更正后的代码，以及我所做更改的注释：

import random

s = input ("enter board size\n")
s = int(s)
trials = 0
block = 1
queen = 2
# add some maximum to the number of attempts
max_trials = 100000 
success = 0

# add safety measure to avoid infinite looping
while success == 0 and trials <= max_trials:
    # initialise board before every trial
    board = [[0 for x in range(s)] for y in range(s)]
    # assume success until failure
    success = 1
    # count trials
    trials += 1 
    for y in range (0, s): # use correct range
        # get the fields that are still available in this row
        available = [x for x, i in enumerate(board[y]) if i == 0]
        if len(available) == 0:
            success = 0
            # exit for loop, you want to start a next trial
            break
        # choose a random position among available spots only
        pos = available[random.randint(0, len(available)-1)]    
        board[y][pos] = queen
        a = 1
        for z in range (y+1, s): # use correct range
            board[z][pos] = block
            if pos - a >= 0:
                board[z][pos - a] = block
            if pos + a < s:
                board[z][pos + a] = block
            a = a + 1

for y in range (0, s): # use correct range
    print (board[y])

print ("Number of trials:", trials)

Answer 2

这是一个基于对放置的皇后坐标进行算术运算的简短解决方案：

import random, itertools

def clashes(p,q):
    a,b = p
    c,d = q
    return a == c or b == d or abs(a-c) == abs(b-d)

def solution(queens):
    #assumes len(queens) == 8
    return not any(clashes(p,q) for p,q in itertools.combinations(queens,2)) 

def randSolve():
    counter = 0
    while True:
        counter += 1
        queens = [(i,random.randint(1,8)) for i in range(1,9)]
        if solution(queens): return counter, queens

print(randSolve())

上次运行时我得到：

(263528, [(1, 4), (2, 7), (3, 3), (4, 8), (5, 2), (6, 5), (7, 1), (8, 6)]) 意味着在263527次失败后遇到了第一个解决方案。平均而言，在获得成功之前，您预计会经历 182360 次失败。

Answer 3

当你尝试不同的行并这次失败后，你必须创建一个新的空板，如果成功为0，你应该打破for循环，如下所示。

while success == 0:
    board = [[0 for x in range(s)] for y in range(s)]
    for y in range (0, s):
        pos = randint(0,s-1)    #line 19
        if board[y][pos] != block:
            board[y][pos] = queen
            for i in range(y+1, s):
                board[i][pos] = block
            success = 1
        else:
            success = 0
            break
    trials += 1

您可以遵循相同的逻辑来实现对角线情况。