Saturday, May 12, 2007

Solving NQueens using Reduced Ordered Binary Decisision Diagrams

Here's one of the things I've been too busy to post:
At my AI course we've completed our last 2 assignments. The one that I'll post here is the N-Queens problem solver, that helps solving the n-queens problem using BDD's.
BDD's is a really clever technique that can help solve some satisfiability problems quite fast.

The N-Queens problem is a classic problem, described lots of places. The derives from the 8-queens problem, thats how to fit 8-queens onto an 8x8 chess board without any of them threatening the others (according to the rules of chess).
It can be solved in many ways, but BDD's is a quite efficient way of doing it.
The basic idea is to build a binary decision diagram, where every node corresponds to a variable in the problem, construct the diagram according to the rules (constraints) that apply to the specific problem and along the way reduce the diagram according to a couple of rules (and to avoid duplicate node-childnode patterns).
How we choose to assign the nodes can be found in our report (as always written with Thomas Gravgaard and Peter Thygesen). Also, a final web-version of our solution can be tried out here.


Stavros said...

If the problem size is 12, then you run out of memory..

Still, very good solution, keeping in mind that you were supposed to solve the 8-queens problem only.

Allan Thræn said...

Oh yeah..I see that might happen sometimes.
The web-version uses precompiled BDD's, but the one for 12-queens takes up 8-9 MB, and that might be too much for my hosting provider to handle :-)