Solving N-Queens problems with Aqueduct

One of the more interesting and rewarding things I've been doing during my 'time off' is to watch the lectures for the classic MIT course  "Structure and Interpretation of Computer Programs", or "SICP". The lectures are online, and are fascinating -- it makes you long for a better day when a programmer could get a job matching parentheses. At any rate, they spend a long time on streams, and well, streams are something I kinda dig.  One of the examples they attacked using streams intrigued me -- solving the n-queens problem.

For those who aren't familiar with chess arcana or intro to AI problem sets, the n-queens problem is "how do you arrange N queens on an N by N chessboard such that none of the queens can take one another... that is, none of them are in the same row, column, or diagonal. 

As it turns out, this is a pretty easy problem to solve using aqueduct, the stream processing tool I've been working on. I've checked in the code as a sample (it is about 70 lines of F# code barring comments and whitespace). Basically, it works by treating each queen as an independent actor. We thread the current board through the N queens, and each queen decides where it can go among the possible spaces. For each candidate space, it sends a new board to the next queen. Thus every queen gets only valid boards, and passes on all valid boards that are possible given the input valid boards.

One would imagine that this would cause a search space explosion -- after all, there are about 64!/(64-8)! or 178 trillion ways to place 8 queens on a board. However, in practice, we can reduce the number significantly out of hand ... by restricting each queen to a single row (since any solution will have one queen per row) we get a search space of 8^8, or 16 million. If placement is done sequentially, the actual search space is again much smaller, since once a queen is placed it limits the placement possibilities for other queens. In practice (I didn't do the math on this, just the ran it and counted) you only need to look at 17,000 states to exhaustively search.

Streams can implement a kind of backtracking search without any backtracking. For the n-queens problem, for each queen, each board passes through three stages -- 'join' which creates a new record for each combination of queen position and input board state (i.e. for n queens and m input boards it will produce n * m boards), 'filter', which filters out all invalid moves, and 'accept' which adds a move to the board. The result is then passed to the next queen. Anything that passes all n queens is a valid board state. 

While this is not really the type of problem aqueduct was designed to solve, it does a pretty decent job of it. Because each stream runs in parallel, it should get good speedup on a multi-core machine (I'm running on a dual-core laptop).

For 8 queens, it computes all 92 possible boards in under a second. Here is one of them:

-----------------

|Q| | | | | | | |

-----------------

| | | | |Q| | | |

-----------------

| | | | | | | |Q|

-----------------

| | | | | |Q| | |

-----------------

| | |Q| | | | | |

-----------------

| | | | | | |Q| |

-----------------

| |Q| | | | | | |

-----------------

| | | |Q| | | | |

-----------------

For 16 queens, the state space is much larger, but we still get results within a few seconds. Not bad for brute force!