"""
 recursive_descent.py

 A recursive descent tree search solution of the n-queens problem.

   $ python recursive_descent.py
   A solution to the 8 queens problem is 
    * . . . . . . . 
    . . . . * . . . 
    . . . . . . . * 
    . . . . . * . . 
    . . * . . . . . 
    . . . . . . * . 
    . * . . . . . . 
    . . . * . . . . 
   The number of solutions for n=8 is 92.

 Jim Mahoney | cs.bennington.college | May 2022 | MIT License
"""

from utilities import invalid_below, board_string

def search_recursive(board, row):
    """ search for a valid board using recursive descent """
    n = len(board)
    if row == n: return board           # Did all rows, so this is a solution.
    for column in range(n):
        board[row] = column
        if not invalid_below(board, row):
            result = search_recursive(board, row + 1)
            if result: return result    # If we found one, just return it.
    return False                        # Dead end on this branch.

counter = {'total': 0}
def count_recursive(board, row):
    """ search for a valid board using recursive descent """
    n = len(board)
    if row == n:
        counter['total'] += 1  # solution found; increment counter
        return
    for column in range(n):
        board[row] = column
        if not invalid_below(board, row):
            count_recursive(board, row + 1)

def count_solutions(n):
    """ return total number of solutions for n-queens """
    counter['total'] = 0
    count_recursive([None]*n, 0)
    return counter['total']

def search(n):
    """ search for and return one solution to the n-queens problem """
    return search_recursive([None]*n, 0)

def main():
    print(f"A solution to the 8 queens problem is {board_string(search(8))}")
    print(f"The number of solutions for n=8 is {count_solutions(8)}.")
    
main()