# nQueens example
# Last updated 11/7/22

def nQueens(n):
    # Set up an empty board and call our recursive solver
    board = [['_']*n for row in range(n)]
    return nQueensSolver(board, 0)

def nQueensSolver(board, newQueenRow):
    rows, cols = len(board), len(board[0])
    if newQueenRow >= rows: # If we are trying to place beyond the board...
        return board        #  ...we're all done! Return the solution.
    else:
        # For each column in newQueenRow...
        for newQueenCol in range(cols):
            if isLegalMove(board, newQueenRow, newQueenCol):
                # Make the move if it is legal.
                board[newQueenRow][newQueenCol] = 'Q'

                # Recursively try to solve from this point
                result = nQueensSolver(board, newQueenRow + 1)
                if result != None: # Return the solution if we found one
                    return result

                # Undo the move if we did not find a solution
                board[newQueenRow][newQueenCol] = '_'
        
        return None # Return None if no moves lead to a solution

def isLegalMove(board, newQueenRow, newQueenCol):
    # Assuming we have only made legal moves so far, we only need
    # to check that our new queen in the new row does not cause conflicts.
    rows, cols = len(board), len(board[0])
    for row in range(newQueenRow):
        # For each prior row, check up, up-left, and up-right from new queen
        rowDifference = newQueenRow - row
        upLeftCol = newQueenCol - rowDifference
        upRightCol = newQueenCol + rowDifference
        if ((board[row][newQueenCol] == 'Q')                           #up
            or (upLeftCol >= 0 and board[row][upLeftCol] == 'Q')       #up-left
            or (upRightCol < cols and board[row][upRightCol] == 'Q')): #up-right
            return False
    return True

#----------------------------------------------------------------

def printSimple2dList(L):
    for row in L:
        print(row)

for n in range(1,10):
    print("n =", n)
    result = nQueens(n)
    if result != None:
        printSimple2dList(result)
    else:
        print(None)
    print("******************************")