/ Algorithms

N-Queens - Go

Alright, if you've read any of my recent posts you already know what this is all about If you aren't familiar with the Go syntax definitely make a quick read of that last one, it will get you up to speed enough real quick. Otherwise let's get into some code!

Dispatching Routines

Let me start by saying this was a lot of fun. I tried a couple different ways of organizing my go routines and in the end the model that worked best was very similar to the one I used for web workers.

The key difference here is that communication between go routines is much easier. The language is just built for it.

This gives a general idea of the flow of the program. Just like last time I launch an independent routine for each potential placement of the first piece. This time each of those routines is launched from the main thread.

func Count(n int) int {
	solutionCount := 0
        // Starts done channel
	doneCh := make(chan bool)
        // Starts count channel
	countCh := make(chan int)
	for i := 0; i < n; i++ {
        // Launch a routine with 1 piece on the next option in row 1
		go pathSupervisor(makeBoardWithPiece(n, i), 1, makeColsWithPiece(n, i), doneCh, countCh)
	}
        // while there are outstanding routines
	for n > 0 {
        // receive any incoming messages
		select {
        // if a count, increment count
		case _ = <-countCh:
			solutionCount++
        // if a done, decrement routines
		case _ = <-doneCh:
			n--
		}
	}

	return solutionCount
}

For anyone coming from Javascript you can look at that for loop as if it was a while loop, and that select like a switch, and it should be pretty straight forward. Firing off a concurrent routine simply placing go in front of the function could not be simpler. Even the channels are readable with the 'to' <- 'from' syntax.

You might be wondering about those two function calls being passed into the routine. Let's look.

func makeBoardWithPiece(n int, first int) (board [][]int) {
	board = make([][]int, n)
	for i := 0; i < n; i++ {
		board[i] = make([]int, n)
	}
	board[0][first] = 1
	return
}

This function makeBoardWithPiece does just that. It builds a board and places the first piece on it. You might remember that the web workers solution didn't require me to make a new board for each worker. That was because when you send data to a worker it is sent as a copy by default.

In go slices are sent by reference. Only array's are copied when passed as parameters and there is no way to programmatically create an array of some arbitrary length, n. You have to use a slice. So in order to prevent all the routines from working on the same board at the same time this function must make a new board for each.

func makeColsWithPiece(n int, first int) (cols []int) {
	for i := 0; i < n; i++ {
		if i != first {
			cols = append(cols, i)
		}
	}

	return
}

This one just makes the column array like normal but skips the column that will be already used when the board was created.

The Routines

func pathSupervisor(board [][]int, row int, cols []int, doneCh chan bool, countCh chan int) {
	search(board, row, cols, countCh)
	doneCh <- true
}

The supervisor in this one really does nothing except wait for the actual search to finish. This was just necessary because if each call to search sent back a done message the program would end to early. I could have used richer messages to also increment the count of outstanding calls on each search call and this would solve the problem but it introduces a lot of unnecessary operations.

In fact I tried to do that and make each recursive call a go routine. The performance was atrocious. You can read my notes in the readme if you would like to see a little more about what I found. Basically after some testing the speed drop seemed to be in part due to having to create a copy of the table for each call and simply the weight of either the routines or the message channels

func search(board [][]int, row int, cols []int, countCh chan int) {
	if len(cols) == 0 {
		countCh <- 1
		return
	}

	for _, col := range cols {
		if !hasMajorDiagonalConflitctAt(board, row, col) && !hasMinorDiagonalConflictAt(board, row, col) {
			board[row][col] = 1
			search(board, row+1, filterCols(cols, col), countCh)
			board[row][col] = 0
		}
	}

	return
}

After the supervisor the search function is really just business as usual. I won't even post the hasMajor, hasMinor and filterCols functions since they are identically to those used in the Javascript implementations.(plus some type declarations obviously)

Final Notes

That's it! Overall this was an incredibly enjoyable experience. Go definitely has some peculiarities that aren't my favorite but I imagine every language will. Sometime soon I will make a post and dig into some of my thoughts and preferences. For now I'll leave you with the benchmarks.

Sequential (s) Web Workers (s)
N = 8 .006 .006
N = 9 .009 .007
N = 10 .015 .010
N = 11 .064 .028
N = 12 .273 .108
N = 13 1.496 .563
N = 14 9.063 2.952
N = 15 58.394 19.233
N = 16 400.215 134.070
N = 17 N/A > 600