8 queens puzzle - recursion using python

Question

I’m trying to solve the 8-queens puzzle, also known as n-queens algorithm.

My function should count how many legal ways are there to place N queens on NxN board.

I almost got it, but had to do some ugly patch to make it work. Can you help me fix it?

A brief on What I did: Trying to find out how many legal ways are there to set N queens in NxN table, I was trying to solve using recursion on a (N-1)xN case (Removing first column) As for the fact no two queens are allowed on the same column, I use a list length of N. Each cell represents a column and in each column I set the row number of where the queen is set.

For example,

[0, 4, 7, 5, 2, 6, 1, 3]

Means that:

• Column 0 – queen placed in row 0
• Column 1 – queen placed in row 4
• Column 2 – queen placed in row 7
• Column 3 – queen placed in row 5
• Column 4 – queen placed in row 2
• Column 5 – queen placed in row 6
• Column 6 – queen placed in row 1
• Column 7 – queen placed in row 3

The thing that bothers me is that I have no idea how to omit the illegal queen placing. So to make it work, I uses a global variable named sum, increment it only when recursion reaches a fully placed arrangement of queens which is legal.

def is_available(n, table, column, N):
    return not any(t in (n, n - i, n + i)
                   for t, i in zip(table, range(column, 0, -1)))

def queens_sum(N):
    table = [0]*N
    global sum
    sum = 0
    solve(N, table, 0, len(table))
    return sum

def solve(N, table, column, end):

    global sum

    if column == end:
        sum += 1
        return None

    for n in range(N):
        # if no other queen can attack here, place a queen in this row 
        if is_available(n, table, column, N):
            table[column] = n
            # Omit the current column at the start
            solve(N, table, column+1, end)
        #else: we can't place queen here, we should abort this direction
            # do nothing

For N = 8 I get sum = 92.. therefore I know it works, but I want to avoid this global counter.

can you help?

Answer 1

You can use the return value of solve to keep track of the sum:

def queens_sum(N):
    return solve(N, [0]*N, 0, N)

def solve(N, table, column, end):
    if column == end:
        return 1

    sum = 0
    for n in range(N):
        # if no other queen can attack here, place a queen in this row 
        if is_available(n, table, column, N):
            table[column] = n
            # Omit the current column at the start
            sum += solve(N, table, column+1, end)
        #else: we can't place queen here, we should abort this direction
            # do nothing

    return sum