Skip to content

Instantly share code, notes, and snippets.

@xavierskip
Last active May 20, 2023 07:48
Show Gist options
  • Save xavierskip/55d275713b436a953c4688483a3df7aa to your computer and use it in GitHub Desktop.
Save xavierskip/55d275713b436a953c4688483a3df7aa to your computer and use it in GitHub Desktop.
Eight queens
# https://leetcode.com/problems/n-queens/submissions/
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
queen = [0]*(n+1)
# print(queen)
result = []
def Place(y):
for x in range(1,y):
if queen[x] == queen[y] or (abs(queen[x]-queen[y]) == (y-x)):
return 0
return 1
def Nqueen(y):
for x in range(1,n+1):
# print(y,queen)
queen[y] = x
if Place(y) and y<=n:
if y==n:
result.append(Show())
else:
Nqueen(y+1)
def Show():
rlt = []
print('(',end='')
for q in queen[1:]:
print(q,end=',')
e = ['.']*n
e[q-1] = 'Q'
rlt.append(''.join(e))
print(')\n')
return rlt
Nqueen(1)
return result
# generator_iterator.ipynb
def solve(n):
solutions = []
columns = []
diagonals1 = []
diagonals2 = []
def backtrack(row, columns, diagonals1, diagonals2, board):
if row == n:
solutions.append(board)
return
for col in range(n):
if col in columns or row+col in diagonals1 or row-col in diagonals2:
continue
backtrack(row+1, columns+[col], diagonals1+[row+col], diagonals2+[row-col], board+[col])
backtrack(0, [], [], [], [])
return solutions
solutions = solve(8)
for i in solutions:
for e in i:
l = [" - "]*8
l[e] = ' # '
print(''.join(l))
print(i)
print("\n")
print(len(solutions))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment