# Eight Queens puzzle (Haskell)

### From LiteratePrograms

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 `[r`

represents _{1},...,r_{n}]`n`

queens in the positions:
`[(1,r`

.
_{1}),...,(n,r_{n})]

## A safe set of queens

We start by defining a function `safeAddition`

that determines whether adding a queen at `(0,r`

is safe. We do this by checking the list _{0})`[r`

to determine if:
_{1},...,r_{n}]

- r
_{i}= r_{0}or -
`abs (r`

_{0}- r_{i}) = 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, `r`

. If either of these conditions is true the addition is not safe.
_{i} - r_{0}

<<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]wheref 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],...]

Download code |