python non recursive solution to n queen problem
- 2021-10-13 07:51:00
- OfStack
The complexity may be a little high-and I didn't pay much attention to it
I've been thinking for a long time and looking for a long time, but I don't see anything that can solve the n queen problem with python and don't call recursion because I don't quite understand recursion (especially when it comes to n layer). IQ is limited-
import copy
def check(A,x,y):
B=[]
flag=True
for i in range(len(A)):
for j in range(len(A)):
if A[i][j]==1:
B.append([i,j])
for m in range(len(B)):
p = B[m][0]
q = B[m][1]
if y == q or (x-p)==abs(y-q):
flag=False
return flag
def queen(n):
A=[[0 for __ in range(n)] for _ in range(n)]
answer=[]
for _ in range(n):
stack=[[0,_,A]]
while stack:
judge = 0
obj=stack.pop(-1)
x=obj[0]
y=obj[1]
array=obj[2]
flag=check(array,x,y)
if not flag:
while 1:
if check(array, x, y):
break
else:
if stack:
b=stack.pop(-1)
x=b[0]
y=b[1]
array=b[2]
else:
judge=1
break
if judge==1:
break
array=copy.deepcopy(array)
array[x][y]=1
for m in range(n):
if m!=y and m!=y-1 and m!=y+1 and x+1<n :
stack.append([x+1,m,array])
# print(array)
for j in range(len(array[n-1])):
if array[n-1][j]==1:
answer.append(array)
print(len(answer))
queen(8)
What is stored in answer is all the last feasible combinations
The current solution is the 8 queens problem
My idea is to use dfs to bring along each search position x, y and the chessboard to be placed, i.e. [x, y, A]
This does not cause all operations to be performed on one matrix