0
votes

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

Are you looking for the total number of calls, or the maximum recursion depth?Tim Roberts
BTW, you don't need global results. You're changing the object in place, not replacing the value.Tim Roberts
I'm looking for the number of recursive calls for 8-queens. It's not specific, so I think that is the total number of calls. Also, thanks for the tip.pythonNoob