Home

N Queens

Sunday 03 March 2013

Place n queens on an n×n chessboard so that no two queens can attack each other.
The eight queens puzzle (and its n queens generalisation) has been studied in great detail. Implementing a solution can teach you a several techniques for general programming problem solving. I'm going to highlight a few of the key lessons you can get from solving this.
As usual, I'm going to use Go, but most of the lessons apply to any language.

Data structures

One of the first things to think about is how you're going to represent your data. Getting the datastructures right is a critical step in the design of any program.
A first approach might be to represent the chessboard as a two-dimensional array of booleans, representing the presence of a queen. But thinking carefully about the problem will tell you that you can only have one queen on each row. Therefore we can just record the column that each queen is in.
type board []int
We're going to use a slice to represent the board, with the length representing the number of queens (or rows) placed so far, and the capacity representing the total number of rows (n). Go slices are explained here. As we'll see later, we're going to place queens on each row successively, so we need to determine if a given column in the next row is free:
//A column in a new row is free if it is not
//being attacked by any queen in the previous rows
func (b board) colFree(col int) bool {
	for i := range b {
		if b[i] == col {
			//queen in same column
			return false
		}
		//check diagonals
		dist := len(b) - i
		if b[i]+dist == col {
			return false
		}
		if b[i]-dist == col {
			return false
		}
	}
	return true
}
It's obvious when there's a queen in the same column as we're testing. Queens on the same diagonal are the same distance apart in rows as in columns. So we can test both diagonals easily. The next row is simply len(b), as len(b)-1 queens have already been placed.

Backtracking

A backtracking algorithm is one that guesses a partial solution and checks if it satisfies the constraints. If it does, it recurses. If it doesn't, it undoes that guess and guesses again.
We're going to find all the places that a queen could go in the next row, place each one and recurse. If we can't fit any queens we'll return to the row above. We can simplify our code if we adjust the above colFree to return a list of all the columns we could potentially put a queen on, instead of testing one at a time:
//Which columns of the next row are being attacked?
func (b board) colsAttacked() []bool {
	attacked := make([]bool, cap(b))
	for i := range b {
		//queen in same column
		attacked[b[i]] = true
		//check diagonals
		dist := len(b) - i
		if b[i]+dist >= 0 && b[i]+dist < cap(b) {
			attacked[b[i]+dist] = true
		}
		if b[i]-dist >= 0 && b[i]-dist < cap(b) {
			attacked[b[i]-dist] = true
		}
	}
	return attacked
}
We return the columns we can't put a queen on to simplify things further. The actual backtracking is straightforward; we append to the board when we add a new queen, and reslice when we remove it:
func (b *board) Solve() {
	if len(*b) == cap(*b) {
		fmt.Println(b)
		return
	}
	cols := b.colsAttacked()
	for i := range cols {
		if !cols[i] {
			*b = append(*b, i)
			b.Solve()
			*b = (*b)[:len(*b)-1]
		}
	}
}
And that's it! Add a print method to the board and call it once we've placed as many queens as there are rows (the capacity). Note that Solve has to be defined on a *board since it modifies its length.

Board size

We may branch multiple times at every level of recursion, leading to an exponentially growing runtime. The number of solutions is also exponential.

Concurrency

Go is designed with tools to help concurrent programming and this problem is quite well-suited to it. Each problem is composed of many subproblems (one for each guess we make). We can solve those subproblems concurrently, since they don't depend on each other.
var jobs = make(chan *board)
var done = make(chan struct{})
var splitDepth int
func (b *board) Solve() {
	if len(*b) == cap(*b) {
		done <- struct{}{}
		return
	}
	cols := b.colsAttacked()
	for i := range cols {
		if !cols[i] {
			if len(*b) == splitDepth {
				b2 := b.Copy()
				*b2 = append(*b2, i)
				jobs <- b2
			} else {
				*b = append(*b, i)
				b.Solve()
				*b = (*b)[:len(*b)-1]
			}
		}
	}
}
func (b board) Copy() *board {
	b2 := make(board, len(b), cap(b))
	for i := range b {
		b2[i] = b[i]
	}
	return &b2
}
Instead of solving every subproblem in order, we can do them asynchronously by passing a copy of the board to a goroutine. We choose a level (number of rows) at which to distribute tasks. This is fairly arbitrary, but we want a good balance between large enough and enough tasks. We pass copied boards to the jobs channel. Once a board is completed and a solution found we notify the done channel. This channel doesn't pass a value we're interested in (like an int), so we just pass an empty struct. We could pass a copy of the board so that the goroutine receiving from done can print it, but that would add too much overhead.
var exit = make(chan bool)
var wg sync.WaitGroup
func init() {
	//start workers
	for i := 0; i < runtime.NumCPU(); i++ {
		wg.Add(1)
		go worker()
	}
	//when workers are all finished
	go func() {
		wg.Wait()
		close(done)
	}()
	//count solutions
	go func() {
		i := 0
		for _ = range done {
			fmt.Println(i)
			i++
		}
		exit <- true
	}()
}
func worker() {
	for b := range jobs{
		b.Solve()
	}
	wg.Done()
}
All init functions are called before main. We set up a goroutine for each CPU we have available. These workers solve boards coming from the jobs channel. Once that channel closes the goroutines will exit, which means no more boards can be completed. The first function literal will then close the done channel. The second function literal prints the number of boards it receives, and signals on the exit channel once all have been counted.
func main() {
	n := 8
	splitDepth = n/3
	b := make(board, 0, n)
	b.Solve()
	close(jobs)
	<-exit
}
To kick it off we just call b.Solve synchronously. Once this completes it means it's dispatched all subproblems to the goroutine workers, so we close the jobs channel. Then we wait for all the boards to be counted.
See the whole thing in action here.

Parallelism

Parallelism is not the same as concurrency. Making the number of workers equal to the number of CPUs available seems reasonable, but we do not achieve linear speedup:
$ pgrep multi | xargs -- top -bn 1 -p 
...
  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
18195 peter     20   0  263m 1252  660 S  737  0.0   2:02.48 multi 
I chose splitDepth pretty arbitrarily, but the thought was that you can easily place n/3 queens by spacing them apart by more than one column.
It turns out that splitDepth around 2 is best in almost all cases. Increasing it further just increases the overhead of copying boards, until the point where most solutions are discarded before we get to that level. At that point most of the processing was being done by a single goroutine. So that's a nice, negative result to publish :). I was concerned that if we had x workers and the number of jobs created was mx+1, then a single worker would have to process the job on its own. By making the jobs smaller I thought the overall runtime could be reduced. Whilst plausible, it appears the variation in time taken for the jobs evens this out enough for it not to matter.

Symmetry

Although there are 92 solutions to the 8x8 problem, only 12 of them are distinct. The others are rotations or reflections. Generating only the distinct solutions requires some careful thought about group-theory, but a simple method to take advantage of symmetry is to restrict the queen of the first row to be in the left half. The other solutions can be found by reflecting the board in the vertical axis. If n is odd then the queen could be in the central column, and would not need to be counted twice.
func (b *board) Solve() {
    if len(*b) == cap(*b) {
        //don't count queen in center column of first row twice
        if (*b)[0] == cap(*b)/2 {
            done <- 1
        }else {
            done <- 2
        }
        return
    }
    cols := b.colsAttacked()
    for i := range cols {
        if len(*b) == 0 && i >= (cap(*b)+1)/2{
            break
        }
...

Heuristics

Sometimes a problem is more easily solved by looking for signs that you may be on the right path to a solution. Such signals are called heuristics. As we've seen, the larger the board gets, the longer it takes to find all the solutions. But the time taken to find a single solution also increases (small yellow line on the left):
If we're just interested in finding any solution, not the first lexicographically, we can use an "iterative repair" approach. The idea is to take an arrangement of queens that doesn't solve the problem, and move the queens about until you find one that does. We use the heuristic that the queen that's under attack the most should be moved to the column that's under attack the least. We still constrain it to one queen per row, and we can now run multiple boards completely independently, returning the first found solution to much larger boards very quickly.
The graph above shows that iterative repair is hundreds of times faster than backtracking for even small boards. The number of iterations is also shown. It took half a second to place 1000 queens.
The code for the iterative repair involves some consideration of detecting local minima, so I'll go over it in a later post.

Conclusion

Simple puzzles can demonstrate a wide variety of programming techniques. And that's part of why they're fun...

Previous (Go's sort performance)
Next (Word Count)