Re: Trying to solve N-Queens

[Helter]

I doubt you have the time to research this path, but while taking a Genetic algorithms class, along with a parallel computing class I was given 2 final projects.

1. Solve one of these problems using a GA( I picked N Queens)
2. Solve a problem using a MP module (in a lab with 8 machines dedicated to running our code).

If you have never heard of GA's, they are quite nifty. The basic flow goes like this:

1. Create a random population. This population is some sort of representation of a possible solution. In this case it is a N^2 string of 0's and 1's. The 1's represent a queen, the 0's no-queen. For speed you can generate by lines such that there is only 1 queen per row, but this is done randomly.
So for N=4 one possible population member is: 0010 1000 0100 0010
This looks like this on the chessboard:
00Q0
Q000
0Q00
00Q0

2. Rank each member using a fitness function, this is usually the most difficult code to generate. If I remember correctly I took a large number, and subtracted off for each queen that collided with another. As an optimization I started in the upper left, and only looked down and down-right, this works because we chose the population to only have a single queen per row. (but no guarantee on columns).

3. The tournament begins. Using the fitness as a weight choose 2 members of the population, with the goal of picking 2 "good" members (higher fitness). Invert the weight and pick 2 of the "worst" members. Cross the 2 "good" members and replace the 2 "worst" members.
Crossing involves picking a random break in the string (on row boundaries so we can still ensure that we only have 1 queen per row.)
Continue for some number of iterations.

4. I added a bail-out for speed, such that if we ever found a solution stop looking, (max fitness value). If we have not hit that condition loop back to 2.

5. To further diversify the population (and attempt to avoid the population converging on a single, possibly bad, solution, you can add "mutations". After the tournaments/crossover (3) pick a few random members, and with a probibility randomly re-generate a portion of the member.

Where this shines is the fact that you can split the work up into many threads to get more work done. I split it up such that I had 1 master, 8 slaves. Each slave would generate it's own population, and do tournaments within it's own population. After each pass each member would take it's best member and send it to a neighbor (thinking of the slaves as a ring), the neighbor would replace it's worst with this new best.

If we found a "perfect" solution the master was notified and it would shut down all the other threads.

While running with this code I was able to solve a N=70 in about an hour, didn't have time to try bigger numbers, had to write the reports for both classes :)

Just another way to think about the problem instead of using brute force.

Helter