Another thing that keeps me busy these days, is my last course at ITU. The course name is Multimedia Production for the Internet, and mainly it covers animation and programming with Flash.
I have to find something nice to make in flash for my final project(or exam).
I was thinking to implement a small adventure game, but it will require too much time(which I don't have (or I want to spend it elsewhere))..
I am also considering to create a website for Ellas, which is a Greek restaurant situated at Copenhagen..
The back-up solution is to make a useless website with no subject and nothing to say, where I will implement all the techniques that we learned, just to illustrate that I know what I have been taught :)
The deadline/exam is the 22nd of May.
Thursday, April 19, 2007
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..
--Update
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 :)
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..
--Update
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 :)
Subscribe to:
Posts (Atom)
