# Eight Queens puzzle (Haskell)

The n-Queens is the extension of the 8-Queens problem to an n by n chessboard. The challenge is to place n queens on an n by n chessboard such that no two queens are attacking each other.

We represent solutions by a list of integers, `[Int]`. The list `[r1,...,rn]` represents `n` queens in the positions: `[(1,r1),...,(n,rn)]`.

## A safe set of queens

We start by defining a function `safeAddition` that determines whether adding a queen at `(0,r0)` is safe. We do this by checking the list `[r1,...,rn]` to determine if:

1. ri = r0 or
2. `abs (r0 - ri) = i`

for any `i` in `[1..n]`.

The first condition determines whether two queens are in the same row. The corresponding condition for columns is satisfied as a result of our data-structure: a list of `n` queens represents `n` queens in adjacent columns. The second condition determines whether queen `0` is attacking queen `i` on the diagonal: whether their horizontal separation, `i - 0`, is equal to their vertical separation, `ri - r0`. If either of these conditions is true the addition is not safe.

```<<safeAddition>>=
safeAddition :: [Int] -> Int -> Int -> Bool
safeAddition [] _ _ = True
safeAddition (r:rows) row i =
row /= r &&
abs (row - r) /= i &&
safeAddition rows row (i + 1)
```

This function is therefore called as `safeAddition currentRows newRow 1` to determine whether the addition is safe.

## Finding solutions

We find solutions by placing queens on the board, one at a time, from right to left. In the following code, we perform a fold over the number of queens from 1 to `n`. At each step, the function `f` returns all solutions that can be safely created by adding a queen in `row` to a previous solution for `k - 1` queens. This is performed using a simple list comprehension:

```<<queens>>=
queens :: Int -> [[Int]]
queens n = foldM f [] [1..n] where
f rows _ = [row : rows |
row <- [1..n],
safeAddition rows row 1]
```

## Running

The code then performs as follows:

```   *Main> queens 8
[[4,2,7,3,6,8,5,1],[5,2,4,7,3,8,6,1],
[3,5,2,8,6,4,7,1],[3,6,4,2,8,5,7,1],
[5,7,1,3,8,6,4,2],...]
```