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 [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. r_i = r₀ 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],...]

Download code