python - Python中的N-Queens程序
问题描述
N皇后是在N×N棋盘上放置N个棋后的问题,这样没有两个皇后相互攻击。我之前已经解决了这个程序,但我试图重新编写我的代码以反映我用来制作数独求解器的代码。我似乎找不到逻辑错误,但是当我运行代码时,什么也没有打印。我的程序附在下面,如果有人能找到我的错误,那将非常有帮助!
import numpy as np
def main():
global n
n = input("Enter N")
n = int(n)
global board
board = np.zeros((n,n), dtype=int)
solve_board()
def solve_board():
for row in range(n):
for col in range(n):
if board[row][col] == 0: #no queen
if (is_valid (board,row,col,n)):
board[row][col] = 1 #Assigning 1 for queen
solve_board()
board[row][col] = 0
return False
print('-'*n)
for row in board:
for col in row:
if col == 1:
print ("Q", end = " ")
else:
print (".", end = " ")
def is_valid(board,i,j,n):
if 1 in board[i]: #Checking row
return False
for row in range(0,i): #Checking column
if (board[row][j]==1):
return False
x,y = i,j
while (x>=0 and y>=0): #left diagonal
if (board[x][y]==1):
return False
x-=1
y-=1
x,y = i,j
while (x>=0 and y<n): #right diagonal
if (board[x][y]==1):
return False
x-=1
y+=1
return True
if __name__ == "__main__":
main()
这就是我之前解决此代码的方式,并按照以下方式更改了solve_board。
def solve_board(row):
if(row == n):
print('-'*n)
for row in board:
for col in row:
if col == 1:
print ("Q", end = " ")
else:
print (".", end = " ")
print("")
else:
for col in range(n):
if (is_valid (board,row,col,n)):
board[row][col]=1
solve_board(row+1)
board[row][col] = 0
return False
这是我当前代码的灵感来源,我设计的一个数独求解器,我使用了 2 个嵌套的 for 循环;一个用于行,一个用于列。基于此,我将原始 n-queens 代码中的 solve_board(row) 更改为没有参数的当前函数。这个数独代码完美运行。
def solve_board():
global board
for rowno in range(9):
#print ("row",rowno)
for colno in range(9):
#print("col",colno)
if board[rowno][colno] == 0:
for i in range(1,10):
#print(i)
if (is_valid(board,rowno,colno,i)):
board[rowno][colno]=i
solve_board()
board[rowno][colno]=0
return False
print (np.matrix(board))
我认为问题可能在于,在 N-Queens 问题中,棋盘没有填满,即仍然有 0,而对于数独来说,整个棋盘都填满了,因此当 ''if board[row][col] == 0'' 被证明为 false 退出循环并打印。在 N-Queens 问题中,因为零总是存在的,所以它成为一个问题。
解决方案
尝试这个
import numpy as np
def main():
global n
n = input("Enter N: ")
n = int(n)
global board
board = np.zeros((n,n), dtype=int)
solve_board()
def print_board():
print('-'*n)
for row in board:
for col in row:
if col == 1:
print ("Q", end = " ")
else:
print (".", end = " ")
print()
def is_valid(board,i,j,n):
if 1 in board[i]: #Checking row
return False
for row in range(0, n): #Checking column
if (board[row][j]==1):
return False
for k in range(0,n):
for l in range(0,n):
if (k+l==i+j) or (k-l==i-j):
if board[k][l]==1:
return False
return True
def solve_board():
for row in range(n):
for col in range(n):
if board[row][col] == 0: #no queen
if (is_valid (board,row,col,n)):
board[row][col] = 1 #Assigning 1 for queen
if np.count_nonzero(board) == n:
print_board()
return True
solve_board()
board[row][col] = 0
else:
return False
if __name__ == "__main__":
main()
推荐阅读
- python - Windows Azure 管道中的 python setup.py build_ext
- vue.js - Buefy:如何在单独注册组件时设置图标包
- python - 无法在 Python 中使用 CSV 打印数据
- css - SVG CSS 动画平滑过渡和原点
- javascript - 我想改进这个通过 ''value=" 过滤 CheckBoxes 列表的 JavaScript 代码
- python - For-loop 只返回最后一个值
- html - 专业人员如何发送 HTML 电子邮件?
- java - 在不知道绝对路径的情况下访问文件,只知道文件名
- xamarin.forms - 在 CollectionView 中横向填充项目,每个项目都以 xamarin 形式呈现屏幕宽度
- python - 通过使用列值反转列名称来重塑数据框