Lambros Petrou
"We are what we repeatedly do. Excellence then, is not an act, but a habit!" — Aristotle

Solve the eight queens problem with Elixir


While I was learning Elixir I wanted something to use the for-comprehension to solve a problem. I remembered the Eight queens puzzle back from my college courses so I decided to give it a go.

I adapted the problem a bit, so my solution takes as inputs the following:

n: number of queens to position on the board
m: size of the board side

List of all the solutions (List[List[int]])

Naive Solution

The solution is simple, and uses backtracking to iterate over all possibilities and select the valid ones.

defmodule Queens do

  @doc """
  Given n number of queens and m the size of the checkerboard, find all solutions to 
  position each queen so that it does not collide with any other queen vertically, 
  horizontally or diagonally.
  def solve(0, _m), do: [[]]
  def solve(n, m) do
    for done_queens <- solve(n-1, m),
        avail_pos <- (Enum.to_list(1..m) -- done_queens),
        safe_pos(avail_pos, done_queens, 1), 
      do: [avail_pos | done_queens]

  defp safe_pos(_, [], _), do: true
  defp safe_pos(pos, [queen | queens], distance) do
    (pos != queen + distance) and 
    (pos != queen - distance) and 
    safe_pos(pos, queens, distance+1)


Obviously, this is not the fastest algorithm to solve this problem (exponential complexity), but it shows how elegant the solution can be using Elixir’s comprehensions.

Sample output in iex:

iex(47)> c("queens.ex")
iex(48)> :io.write Queens.solve(4, 4)
iex(49)> :io.write Queens.solve(3, 4)
iex(50)> :io.write Queens.solve(5, 5)
iex(51)> :io.write Queens.solve(1, 5)



Every day I learn more and more Elixir (and Erlang) and I can say that it’s among the few languages that managed to keep me interested and excited for more than 3-4 months (looking at you Scala and Python).