Eight-Queens Puzzle and Type System

The eight-queens puzzle is commonly used as a pedagogical example to teach recursion in programming. For example, E. W. Dijkstra used it in his famous Notes on Structured Programming (1972, in Structured Programming but not EWD249).

In this post, I want reuse the example to show why expressive type systems, such as higher-kinded types, matter for code reuse.

The Puzzle

The puzzle is well-known: place 8 queens on a 8x8 chess board, such that

• No two queens are in the same row
• No two queens are in the same column
• No two queens are in the same diagonal

Algorithmically, the problem can be solved easily with a recursive function:

  def conflict(p: Array[Int], n: Int): Boolean =
    (0 until n).exists { i =>
      p(i) == p(n)
      || n - i == p(n) - p(i)
      || n - i == p(i) - p(n)
    }

  def queens(n: Int, p: Array[Int], N: Int): List[Array[Int]] =
    if (n >= N) p.clone :: Nil
    else (0 until N).foldLeft(List.empty) { (acc, i) =>
      p(n) = i
      if (conflict(p, n)) acc
      else acc ++ queens(n + 1, p, N)
    }

  def queens(N: Int): List[Array[Int]] =
    queens(0, new Array(N), N)

The algorithm is basically a depth-first search. The usage of the higher-order function foldLeft makes the function queens easy to understand:

(1) If current column n to place the next queen is bigger than the board size N, then the placement is a solution, thus we make a copy of the placement as a valid result.

(2) Otherwise, try place the queen at column n from row 0 until row N. For each such placement, if it does not conflict with existing placement, call the function queens to place the next column recursively. Finally, accumulate all valid solutions for different choices at the current column.

It is also possible to perform breadth-first search, as implemented below:

  def conflict(p: List[Int], c: Int, d: Int): Boolean =
    p match {
      case Nil => false
      case x :: xs =>
        c == x || c == x + d || c == x - d || conflict(xs, c, d + 1)
    }

  def queens(N: Int): List[List[Int]] =
    (0 until N).foldLeft(Nil :: List.empty[List[Int]]) { (acc, i) =>
      for (p <- acc; i <- 0 until N if !conflict(p, i, 1)) yield i :: p
    }

This algorithm simply accumulates all valid partial solutions. Initially, the solution set is empty. After the first column, there are 8 valid partial solutions. It repeatedly extends the partial solutions to the next column and only keep valid ones until it reaches the last column. After the last column, the valid partial solutions become valid full solutions.

So far, nothing new.

New Challenge

To serve my purpose of showing the importance of higher-kinded types in code reuse, I’d like to raise the following challenge:

How to write a queens function such that the user can specify the placement strategy and the container that holds the result?

For example:

• If the user only cares whether any solution exists or not, then the natural return type is Boolean.
• If the user wants to find the first solution if it exists, the natural return type is Option[T].
• The user might want to use an fixed-size Array to find at most k solutions.

In programming languages without higher-kinded types, the challenge is out of reach. With higher-kinded types, the solution is easy:

  def conflict(p: Array[Int], n: Int): Boolean =
    (0 until n).exists { i =>
      p(i) == p(n)
      || n - i == p(n) - p(i)
      || n - i == p(i) - p(n)
    }

  type Answer = Array[Int]

  trait Oracle[F[_]] {
    def choose(n: Int)(op: Int => F[Answer]): F[Answer]
    def succeed(ans: Answer): F[Answer]
    def fail: F[Answer]
  }

  def queens[F[_]](n: Int, p: Array[Int], N: Int)(oracle: Oracle[F]): F[Answer] =
    if (n >= N) oracle.succeed(p.clone)
    else oracle.choose(N) { i =>
      p(n) = i
      if (conflict(p, n)) oracle.fail
      else queens(n + 1, p, N)(oracle)
    }

  def queens[F[_]](N: Int)(oracle: Oracle[F]): F[Answer] =
    queens(0, new Array(N), N)(oracle)

In the code above, the type parameter F is a higher-kinded type, which has the kind * => *. We can think it as a type-level function that takes a proper type and returns another proper type.

Now, if a user only cares about whether a solution exists with a given strategy, it suffices to do the following:

  type BooleanF[T] = Boolean
  val exists: Oracle[BooleanF] = new {
    def choose(n: Int)(op: Int => Boolean): Boolean = {
      var i = 0
      while (i < n) {
        val res = op(i)
        if (res) return true
        i += 1
      }
      false
    }

    def succeed(ans: Answer): Boolean = true
    def fail: Boolean = false
  }

  queens(8)(exists) == true

If the user only cares one solution, it can be done as well:

  val one: Oracle[Option] = new {
    def choose(n: Int)(op: Int => Option[Answer]): Option[Answer] = {
      var i = 0
      while (i < n) {
        val res = op(i)
        if (res.nonEmpty) return res
        i += 1
      }
      None
    }

    def succeed(ans: Answer): Option[Answer] = Some(ans)
    def fail: Option[Answer] = None
  }

  queens(8)(one)

If the user wants to store at most k solutions in an Array, the solution comes naturally:

  type UnitF[T] = Unit
  val k = 5

  val arr = new Oracle[UnitF] {
    val res = new Array[Answer](k)
    var cnt = 0

    def choose(n: Int)(op: Int => Unit): Unit = {
      var i = 0
      while (i < n && cnt < k) {
        op(i)
        i += 1
      }
    }

    def succeed(ans: Answer): Unit = {
      res(cnt) = ans
      cnt += 1
    }

    def fail: Unit = ()
  }

  queens(8)(arr)

Of course, it is not a problem if the user wants all solutions:

  val all: Oracle[List] = new {
    def choose(n: Int)(op: Int => List[Answer]): List[Answer] =
      (0 until n).foldLeft(List.empty) {  (acc, c) => acc ++ op(c) }

    def succeed(ans: Answer): List[Answer] = ans :: Nil

    def fail: List[Answer] = Nil
  }

  queens(8)(all)

In a language without higher-kinded types, either we have to duplicate the code, or we need to resort to type casts; neither is ideal.

The simplest theoretical model for higher-kinded types is System \(F_\omega\), which is an extension of System F with first-class type operators. The book Types and Programming Languages contains a good introduction to both.

As a final word, I want to clarify my position to avoid misunderstanding. While this pedagogical example shows sometimes we need to resort to more complex types to achieve safety and code reuse, I’m not advocating wide usage of higher-kinded types. In contrast, I think we need to defend against abuse of complex types and unnecessary abstractions in programs. As engineers, we need to have a large reserve in our toolbox. However, good engineers always choose the simplest tool appropriate to the problem and the scenario.