from random import *
class NQueens:
"""
This class can be used to represent instances of the N-Queens
problem. In this problem N Queens must be placed on an NxN board
in such a way that no Queen can attack another. Queens can move
horizontally, vertically, or diagonally.
The board is represented as an NxN array of booleans, where True
indicates the location of a Queen. The Queens are initially
placed in unique rows.
"""
def __init__(self, colPosition=None, n=8):
"""
Use the given column positions for each row to generate a board.
Or generate a randomly configured board with one queen in each row.
"""
if colPosition != None:
self.n = len(colPosition)
self.board = [[False for c in range(self.n)] for r in range(self.n)]
for r in range(self.n):
self.board[r][colPosition[r]] = True
else:
self.n = n
self.board = [[False for c in range(n)] for r in range(n)]
for i in range(n):
self.board[i][randint(0,n-1)] = True
def __str__(self):
result = ""
result += ("-" * ((self.n*2)+1)) + "\n"
for i in range(self.n):
result += "|"
for j in range(self.n):
if self.board[i][j] == True:
result += 'Q|'
else:
result += ' |'
result += "\n"
result += ("-" * ((self.n*2)+1)) + "\n"
return result
def safeDirection(self, r, c, deltaR, deltaC):
"""
Starting from the current row r and the current column c, look
in one direction defined by deltaR and deltaC. If another queen
is encountered return False, otherwise return True.
"""
r += deltaR
c += deltaC
while r>=0 and r=0 and c