The Eight Queens Problem is one of the most famous challenges in computer science and mathematics. The goal is simple to state yet surprisingly rich in structure: Place eight queens on a chessboard so that no two queens threaten each other.
In practice, that means ensuring that no two queens share the same row, column, or diagonal. It’s a classical example of a constraint satisfaction problem — and an elegant one to tackle using Haskell’s declarative and recursive strengths.
We must place 8 queens on an 8×8 chessboard so that:
We’ll represent each solution as a list of 8 integers, where the index of the list corresponds to the column, and the value at that index is the row of the queen.
For example: [4,2,7,3,6,8,5,1]
means:
This representation makes the problem much easier to model with Haskell lists and recursion.
I implemented a solution using the generate-and-test approach: generate all possible queen placements, and recursively test which ones are valid.
queens :: [[Int]]
queens =
let outxs = map (\[c, r] -> (c, r)) (sequence [[1..8], [1..8]])
in subQueens (zip outxs (replicate 64 False)) []
subQueens :: [((Int, Int), Bool)] -> [Int] -> [[Int]]
subQueens xs outval =
let col = length outval + 1
outxs = filter (\((c, r), alrd) -> c == col && not alrd && not (r `elem` outval)) xs
in if col > 8
then [outval]
else concat [ subQueens (updateChess c r xs) (outval ++ [r])
| ((c,r),_) <- outxs ]
updateChess :: Int -> Int -> [((Int, Int), Bool)]
-> [((Int, Int), Bool)]
updateChess c r xs =
let newxs1 = map (\((v1, v2), alrd) -> if v1 == c || v2 == r
then ((v1, v2), True)
else ((v1, v2), alrd)) xs
newxs2 = upperLeft newxs1 (c - 1) (r - 1)
newxs3 = upperRight newxs2 (c + 1) (r - 1)
newxs4 = lowerLeft newxs3 (c - 1) (r + 1)
newxs5 = lowerRight newxs4 (c + 1) (r + 1)
in newxs5
-- mark diagonals recursively
upperLeft, upperRight, lowerLeft, lowerRight :: [((Int, Int), Bool)] -> Int -> Int -> [((Int, Int), Bool)]
upperLeft xs 0 _ = xs
upperLeft xs _ 0 = xs
upperLeft xs c r =
let newxs = map (\((x, y), alrd) -> if x == c && y == r
then ((x, y), True)
else ((x, y), alrd)) xs
in upperLeft newxs (c - 1) (r - 1)
upperRight xs 9 _ = xs
upperRight xs _ 0 = xs
upperRight xs c r =
let newxs = map (\((x, y), alrd) -> if x == c && y == r
then ((x, y), True)
else ((x, y), alrd)) xs
in upperRight newxs (c + 1) (r - 1)
lowerLeft xs 0 _ = xs
lowerLeft xs _ 9 = xs
lowerLeft xs c r =
let newxs = map (\((x, y), alrd) -> if x == c && y == r
then ((x, y), True)
else ((x, y), alrd)) xs
in lowerLeft newxs (c - 1) (r + 1)
lowerRight xs 9 _ = xs
lowerRight xs _ 9 = xs
lowerRight xs c r =
let newxs = map (\((x, y), alrd) -> if x == c && y == r
then ((x, y), True)
else ((x, y), alrd)) xs
in lowerRight newxs (c + 1) (r + 1)
The board is represented as a list of all 64 possible positions, each paired with a Boolean flag indicating whether it’s available:
[((col, row), isTaken)]
Initially, all squares are free (all flags are False
).
The function subQueens
tries to place a queen column by column:
not (r `elem` outval)
).
Once a queen is placed, the updateChess
function marks:
The recursion stops once all 8 queens are placed, producing a valid configuration.
Running the function:
λ> length queens
92
λ> head queens
[1,5,8,6,3,7,2,4]
Haskell finds all 92 valid solutions to the classic 8-Queens problem. Each list represents a unique arrangement of queens that do not attack each other.
This implementation is a pure and explicit exploration of how backtracking works. Unlike higher-level libraries that hide the recursion, here we clearly see:
The updateChess
logic mimics how a human would reason about threats on a board —
marking attacked zones before moving on.
Writing this in Haskell emphasizes how recursion, immutability, and list comprehensions combine to form a natural framework for solving constraint-based problems.
The eight queens problem is not just a puzzle — it’s a microcosm of search problems in computer science, from optimization to AI planning.
With a few elegant recursive functions, Haskell transforms a complex constraint system into a readable and mathematical solution.