# Eight-Queens Puzzle and Type System

03 Feb 2020

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)
}

trait Oracle[F[_]] {
}

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 {
var i = 0
while (i < n) {
val res = op(i)
if (res.nonEmpty) return res
i += 1
}
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] {
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 {
(0 until n).foldLeft(List.empty) {  (acc, c) => acc ++ op(c) }


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.