Friday, April 06, 2007

8 Queens and BBDs (Updated)

As I wrote before, I have finished with my Master Thesis.
I have also defended it.
So, it seems that I have plenty of time to write new posts, to have fun, to go out for beers, etc..

The reality is far from this.. :(

One of the things that keep me occupied these days, is that I am working as a Teacher Assistant at the Efficient Artificial Intelligence Programming course. So, instead of enjoying Easter holidays, I will have to implement this in java.

The problem is well known to the community, and it's about placing 8 queens on a chess board. The queens have to be placed in valid positions (not attacking each other) and the algorithm have to check and show to the user only the positions that will lead to a solution. One way to solve the problem is to use Binary Decision Diagrams. That's how we are going to solve it.

So, I have to create the UI and the Logic of the problem, then hide some code from the Logic and let the students figure out how to implement the missing code..

Maybe I was not very clear..
The problem is NOT ONLY to restrict the row, column and diagonal of the last inserted queen, but to restrict all the board positions that don't lead to a solution. What I mean by that, could easily be seen at this image. If you place a queen at A5, then E6 should be restricted, because irrespective of where the user will put the other queens, the problem doesn't have a solution.
Brute force cannot help much here, because of the complexity of the problem. We have to calculate the permutations of 8 queens on the 64 positions of the board. That means 64!/(8!*56!) permutations.

Actually, it can be done with brute force, but since the algorithm has to be able to solve the n-queens problem efficiently, there are more efficient algorithms and data structures :)


Zaf said...

you do know about this, I hope...

Stavros said...

Actually, I hadn't seen it.

But, it's not the same thing. Ksymeon is not trying to help the user by disabling the board positions that don't lead to solution.

You can see what I mean if you see this screenshot. If you place a queen at A5, then it's impossible to place a queen at E6 and solve the problem. Ksymeon's implementation doesn't take this into account.

vpapanik said...

try brute force with ksymeon's app...

for i := 1 to 8 do
for j := 1 to 8 do

etc etc


Stavros said...

check the update ;)