I have the following code for solving the n-queens problem and I am supposed to count the number of recursive calls made. I have a function called ConstructCandidates to get the candidate solutions and I am trying to count the number of recursive calls it makes. I was wondering if I am counting the recursive calls correctly as I am not sure if I am doing this correctly.
def createChessBoard(boardSize):
chessBoard = [0]*boardSize
for index in range(boardSize):
chessBoard[index] = [0]*boardSize
return chessBoard
def isSolution(results, numberOfQueens):
if numberOfQueens==n:
for r in results:
for row in r:
print(row)
print()
return numberOfQueens>len(results)
def safeToPlaceQueen(chessBoard, boardRow, boardColumn, boardSize):
for indexColumn in range(boardColumn):
if chessBoard[boardRow][indexColumn] == 1:
return False
indexRow, indexColumn = boardRow, boardColumn
while indexRow >= 0 and indexColumn >= 0:
if chessBoard[indexRow][indexColumn] == 1:
return False
indexRow-=1
indexColumn-=1
diagonalRow, diagonalColumn = boardRow,boardColumn
while diagonalRow < boardSize and diagonalColumn >= 0:
if chessBoard[diagonalRow][diagonalColumn] == 1:
return False
diagonalRow+=1
diagonalColumn-=1
return True
def ConstructCandidates(chessBoard, columnLength, boardSize):
global recursionCounter
if columnLength >= boardSize:
return
for row in range(boardSize):
if safeToPlaceQueen(chessBoard, row, columnLength, boardSize):
chessBoard[row][columnLength] = 1
if columnLength == boardSize-1:
Process(chessBoard)
chessBoard[row][columnLength] = 0
return
#recursively call ConstructCandidates to find more candidate solutions
ConstructCandidates(chessBoard, columnLength+1, boardSize)
chessBoard[row][columnLength] = 0
recursionCounter+=1
def Process(chessBoard):
global results
solutions = copy.deepcopy(chessBoard)
results.append(solutions)
global count
count= len(results)
def isFinished():
if count >0:
return False
n = 8
chessBoard = createChessBoard(n)
results = []
recursionCounter =0
ConstructCandidates(chessBoard, 0, n)
isSolution(results, n)
if isFinished() is False:
print("All possible solutions without the Queen being in danger have been found")
print("The total number of possible solutions for",n,"Queens is:",len(results))
print("The total number of recursive calls to solve the problem of",n,"Queens is:",recursionCounter)
If I am not doing this correctly would someone be able to show me how? The current result I get for 8-queens is 1964
global results
. You're changing the object in place, not replacing the value. – Tim Roberts