Queens Puzzle Breadth first

Question

I've been told to make a program that solves the eight queens puzzle using breadth first search. This is what i've got so far:

def n_queens(n, width):
if n == 0:
    return [[]
else:
    return add_queen(n-1, width, n_queens(n-1, width))


def add_queen(new_row, width, previous_solutions):
solutions = []
for sol in previous_solutions:
    for new_col in range(width):
        if safe_queen(new_row, new_col, sol):
            solutions.append(sol + [new_col])
return solutions


def safe_queen(new_row, new_col, sol):
for row in range(new_row):
    if (sol[row] == new_col or                  
        sol[row] + row == new_col + new_row or
        sol[row] - row == new_col - new_row):
            return 0
return 1

for sol in n_queens(8, 8):
print sol

Is there any way to improve this?

Answer 1

I don't think BFS is quite the way I'd reason about this problem. Rather, focus on recursively generating the possible placements. For each queen placed, there are only a certain number of possible placements in next row down that can't be attacked. "Place" a queen and recurse on each of those locations, and terminate when you've placed your total number of queens. Hopefully you'll recognize that a for loop mixed in with some recursive calls seems to be like a decent idea. Also remember to "pick up" the queens you placed as your recursion returns.

Answer 2

Agreed with previous entry. The algorithm described above is 'depth-first' search instead of 'breadth-first' search and is much more efficient for this type of problems.