Python 中的 N-Queens 计划
N-Queens program in Python
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'' 被证明是错误的退出循环并打印。在 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 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()
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'' 被证明是错误的退出循环并打印。在 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 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()