# Eight-Queens Puzzle and Type System

03 Feb 2020The 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.