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.
3 comments:
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.
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 :-)
How i can solved the queen problem in bdd by c++ ????
Post a Comment