# N-Queens in Python

After reading aphyr - Typing the Technical Interview , I wondered how quickly I could solve a similar problem without the aid of type-level magic.

Here's what I came up with after around 10 minutes.

The idea is to recursively solve the problem by adding queens to a (initially empty) partial solution. This partial solution keeps track of the position of the queen in each row.

To find a position for the queen in row ``` i ``` , we compute ``` available ``` (non-attacked) positions for it by starting with a set of all positions and removing ones attacked by queens in previous rows.

For example, a queen in column ``` c ``` of row 0 attacks columns ``` {c-1, c, c+1} ``` in row 1, columns ``` {c-2, c, c+2} ``` in row 2 and so on.

We can then iterate over all available columns and try place the next queens based on the new partial solution. If this does not yield a solution, we continue with the next available column.

One downside of this approach is that large values of ``` n ``` will exhaust the recursion limit.

```def search(n, partial, i):
if i == n:
return partial

available = set(range(0, n))

for j in range(0, i):
delta = i - j
c = partial[j]
available -= {c - delta, c, c + delta}

for a in available:
partial[i] = a
res = search(n, partial, i + 1)

if res is not None:
return res

def prettyprint(solution):
n = len(solution)
for r in range(0, n):
row = ['_'] * n
row[solution[r]] = 'Q'
print(''.join(row))

if __name__ == '__main__':
n = 8
partial = [None] * n
solution = search(n, partial, 0)
print(solution)
print()
prettyprint(solution)
```
```[0, 4, 7, 5, 2, 6, 1, 3]

Q_______
____Q___
_______Q
_____Q__
__Q_____
______Q_
_Q______
___Q____
```

If you have an idea how this page could be improved or a comment send me a mail.