"""
 brute_force.py

 A brute force solution of the n-queens problem, checking each of the
 rougnly 40,000 permutation of the board representations with one queen in
 each row and one in each column.

       $ python brute_force.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 valid, board_string
from heaps_permute import heaps_permute

def search(n):
    """ Search for a solution to the n-queens problem """
    for board in heaps_permute(list(range(n))):
        if valid(board):
            return board

def count_solutions(n):
    """ Count the number of solutions to the n-queens problem """
    count = 0
    for board in heaps_permute(list(range(n))):
        if valid(board):
            count += 1
    return count
        
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()