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?
You can use the return value of solve to keep track of the sum: