Python: N-Queen拼图检查对角线的解决方案
Python: N-Queen拼图检查对角线的解决方案
提问于 2017-07-30 11:19:06
在这里，我必须编写N-Queens问题的代码，用户将输入棋盘的尺寸和Queens的位置。
Enter the dimension of the Chessboard: 4
Enter position of the Queen: 10
Enter position of the Queen: 31
Enter position of the Queen: 02
Enter position of the Queen: 23根据用户输入，我已经生成了候选解决方案(这是一个列表)，其中候选解决方案的索引表示皇后的列，值表示皇后的行位置。
候选解决方案如下：[1, 3, 0, 2]
由此，我制作了一个矩阵来表示皇后的位置：
0, 0, 1, 0
1, 0, 0, 0
0, 0, 0, 1
0, 1, 0, 0我的问题是，我必须通过检查对角线来检查候选解决方案是否为真，如果解决方案为真，则打印一条消息。
到目前为止，这是我的代码，它将打印候选解和显示Queens位置的矩阵：
#Ask the user to input the dimension of the Chessboard(N)
N=int(input("Enter the dimension of the Chessboard: "))
#Creating a list of list with zeros in the dimension N*N
list_0=[0 for m in range(N)]
#Iterating for the length of N
for t in range(N):
#Creating a list for the input position values
position=[int(i) for i in input("Enter position of the Queen: ")]
x,y = position[0],position[1]
#The y position is the index of the list_0, where x is the value at the index position
list_0[y] = x
#Printing the list_0
print(list_0)
#Creating a list of list with zeros
list_matrix = [[0 for m in range(len(list_0))] for n in range(len(list_0))]
#Iterating through the list_0 to find the index and the value of the list_0
for element in range(len(list_0)):
x,y = element, list_0[element]
list_matrix[y][x] = 1
#Defining a list to print the candidate solution for N-Queen problen in matrix format
def printListInTableFormat(list_default):
#Looping through length of the list_default
for row in range(len(list_default)):
new_row=''.join(str(list_matrix[row]))
matrix=print(new_row.strip('[]'))
return matrix
#Printing the matrix
matrix = printListInTableFormat(list_matrix)因为我是Python的新手，所以非常感谢您的帮助。提前谢谢。
回答 3
Stack Overflow用户
发布于 2017-07-30 13:06:04
提示
(p, q)的皇后和(r, s) on when abs(p - r) == abs(q - s)的皇后处于同一对角线上。
Stack Overflow用户
发布于 2017-07-30 13:21:37
关于这一点，请参阅@Raymond Hettinger的提示，但基本上，对于N = [1, 3, 0, 2]的输入列表中的每个x(列是x坐标，也是N数组的索引值)，检查所有其他棋子，看看它们的x(列)和y(行)坐标如何比较。
def is_valid(N):
size = len(N)
for x in range(size):
for col in range(x + 1, size):
if abs(x - col) == abs(N[x] - N[col]):
return False
return True或lil位清理器，这将检查是否所有值都为真，检查差异检查：
def is_valid(N):
for x in range(size):
return all(abs(x - row) != abs(N[x] - N[row]) for row in range(x + 1, size)然而，对角线不应该是唯一的有效性测试。您还应该添加此检查，len(N) == len(set(N))。这样可以确保在同一行中没有queens。
Stack Overflow用户
发布于 2019-06-04 03:06:59
一个简单的变奏
import random
global maX
global maY
global mostAttacks
global posInVector
#1.
def GenM(N):
p=[[" " for x in range(0,N)]for x in range(0,N)]
#print(p)
return p;
def fillPos():
p=[[[] for x in range(0,2)]for x in range(0,N)]
#print(p)
return p;
N=4
matrix=GenM(N)
places = fillPos()
posInVector = 0
def randomPlace(N):
for x in range(0,N):
xpos = random.randint(0,N-1)
ypos = random.randint(0,N-1)
matrix[xpos][ypos]='R'
places[x][0] = xpos
places[x][1] = ypos
randomPlace(N)
print(places)
def printMatrix():
print("---------------------------------\n")
for i in matrix:
print(i)
print("\n")
printMatrix()
# == Generate random position , geterate random pos for N queens
# and display the matrix and the array for the queen's positions
def VerifLine(L):
queens = 0
line=matrix[L]
for element in line:
if(element=='R'):
queens+=1
if(queens == 2):
return 1;
return 0;
#print(VerifLine(0))
def VerifCol(C):
queens = 0
for element in range(0,N):
if(matrix[element][C]=='R'):
queens+=1
if(queens == 2):
return 1;
return 0;
def VerifDiagonalStg(L,C):
#print("down left")
j = C-1
for i in range(L+1,N):
if j < N and j >= 0:
if matrix[i][j] == 'R':
return 1
j-=1
#print("---")
#print("up right")
j = C+1
for i in range(L-1,-1,-1):
if j < N and j >= 0:
if matrix[i][j] == 'R':
return 1
j+=1
#print("---")
return 0
def VerifDiagonalDr(L,C):
#print("down right")
j = C+1
for i in range(L+1,N):
if j < N and j >= 0:
if matrix[i][j] == 'R':
return 1
j+=1
#print("---")
#print("up left")
j = C-1
for i in range(L-1,-1,-1):
if j < N and j >= 0:
if matrix[i][j] == 'R':
return 1
j-=1
#print("---")
return 0
maX = -1
maY = -1
def countAttacks(qx, qy):
'''print("queen: ", qx, " ", qy)
print("pe line: ",VerifLine(qx))
print("pe col: ", VerifCol(qy))
print("pe diagonal: ", VerifDiagonalDr(qx,qy) + VerifDiagonalStg(qx,qy))
print("\n=============\n")'''
attacks = VerifLine(qx) + VerifCol(qy) + VerifDiagonalDr(qx,qy) + VerifDiagonalStg(qx,qy)
return attacks
def findMostAttacked(places):
global maX
global maY
global mostAttacks
global posInVector
mX = places[0][0]
mY = places[0][1]
maxAttacks = countAttacks(places[0][0], places[0][1])
for i in range(1,N):
if maxAttacks < countAttacks(places[i][0], places[i][1]):
mX = places[i][0]
mY = places[i][1]
maxAttacks = countAttacks(places[i][0], places[i][1])
posInVector = i
print("most attacked: ", mX, " ", mY)
maX = mX
maY = mY
mostAttacks = maxAttacks
print("attacks: ", maxAttacks)
if mostAttacks == 0:
return 0
else:
return 1
def moveMostAttacked():
global maX
global maY
global mostAttacks
global posInVector
for i in range(0,N):
for j in range(0,N):
if(matrix[i][j] == " "):
attacksForThisPos = countAttacks(i,j)
if(attacksForThisPos < mostAttacks):
matrix[maX][maY] = " "
matrix[i][j] = 'R'
places[posInVector][0] = i
places[posInVector][1] = j
print('poz in vector: ', posInVector)
print(matrix[maX][maY], "->", matrix[i][j])
print('mutata de pe ',maX, ' ',maY, ' pe ', i,' ',j)
print('nr vechi de atacuri: ', mostAttacks)
print('nr nou de atacuri: ', attacksForThisPos)
return 0
while(findMostAttacked(places) == 1):
findMostAttacked(places)
moveMostAttacked()
printMatrix()
input("Press Enter to continue...")
print(" ========== ")页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/45396020
复制相关文章
相似问题