棋盘上的皇后在 Python 中随机解出

Question

想法是通过完全随机地将皇后完全随机地放置在棋盘的每一行中来尝试解决 "queen problem" 问题，然后看看解决它需要多少次重复。棋盘可以任意大小

我的想法是创建 s 个列表，每个列表包含 s "empty" 个字符（下划线）。然后每行随机选择一个位置插入皇后（"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

这次尝试不同的行失败后，您必须创建一个新的空板，如果成功为 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

您可以按照相同的逻辑来实现对角线案例。

Answer 2

一些问题：

range 函数的第二个参数表示将不访问的第一个数字，所以大多数时候你有一个短的。
您需要在尝试失败时在 y 退出循环：您不想继续下一行，但会重新启动
您需要在每次尝试失败后重置棋盘，或者以其他方式放置：在每次尝试之前
如果在多次迭代后仍未找到解决方案，您应该建立一些安全退出机制，否则您将面临卡住的风险。对于输入 1、2 或 3，没有解决方案。
试验次数永不增加
与其盲目地选择一个位置，您最好只从可用位置中选择 select（未被阻止），否则您将进行惊人数量的试验：对于尺寸 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)

在 repl.it

上查看运行

Answer 3

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

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 次失败。

棋盘上的皇后在 Python 中随机解出

Queens on chessboard solved randomly in Python

python

random

n-queens