Remember last time when I said that I'd show you how to use the IntegerSet datatype in an application? Well.. today is the day where I make good on my word. We're going to solve the 8 Queens Problem pretty easily with IntegerSets.
The 8 Queens Problem is simple to define - try to place 8 queens on a chess board in such a way that no queen is threatening another. This is a classic problem that is usually assigned for homework to Computer Science majors. It's a wonderful thought experiment. College is funny like that.. they teach you how to think. In some cases, that's a good thing.. especially in programming when you get a chance to flex your problem solving muslces.
Anyway, as a freshman in college (almost 5 years ago now), I was required to write a solution for it. Back then, I wrote my solution in C++, but I thought it would be another good ActionScript 2.0 example, as well as another good recursion demonstration... so I decided to show an ActionScript 2 implementation of this classic problem.
Before you download my code and just follow along, I highly encourage you to try the problem for yourself. You can download the code here.
Read on...
The algorithm itself, on a high level, is basically a brute force approach. Put down a queen in the first location, figure out which spots are taken up (threatened), and place a queen in the next available location. If you can't place 8 queens, remove a queen and try it in a different location. Lather, rinse, repeat.
.. and finally, here's the finished product... Enjoy!
Oh man, this does remind me of school - I was always a fan of the "Knight's Tour" problem, which I ended up coding in C++ "just for fun" my freshman year.
"8 queens problem" code in c++?