我正在尝试暴力解决 N 皇后国际象棋问题https://en.wikipedia.org/wiki/Eight_queens_puzzle
我的代码正在工作,但是当我尝试返回解决方案数据结构时,会出现异常行为。
包含解决方案的列表在某些时候被覆盖或损坏。
我尝试过使用多种不同的数据结构列表、字典、集合,并且都具有相同的结果。
输出应该是
[[1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2], [1, 3, 0, 2]]
但目前正在返回
[[3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3], [3, 3, 3, 3]]
import numpy as np
# Validation Functions
def checkRows(state):
"""
Check only 1 queen per row
"""
for row in state:
if sum(row) > 1:
return False
return True
def checkCols(state):
"""
Check only 1 queen exists in a column
"""
for i in range(0,len(state)):
count = 0
for j in range(0,len(state)):
#print(state[j][i])
count = count + state[j][i]
if count > 1: return False
return True
def checkDiag(state):
"""
Checks only 1 queen exists per diagonal
https://stackoverflow.com/questions/6313308/get-all-the-diagonals-in-a-matrix-list-of-lists-in-python
"""
# Alter dimensions as needed
n = len(state)
x,y = n,n
# incoming state list
a = np.array(state)
diags = [a[::-1,:].diagonal(i) for i in range(-a.shape[0]+1,a.shape[1])]
diags.extend(a.diagonal(i) for i in range(a.shape[1]-1,-a.shape[0],-1))
for n in diags:
if sum(n) > 1: #if any of the diagonals sums to more than 1 there must be more than 1 queen in that diagonal
return False
return True
def checkState(state):
"""
Returns false on one or more failures
"""
return checkRows(state) and checkCols(state) and checkDiag(state)
海绵宝宝撒