# Queen Problems

Can you place three white queens and five black queens on a 5×5 chessboard so that no queen of one color attacks a queen of the other? The solution is unique, except rotations and reflections.

It took me longer than I first expected to solve this problem. The solution is:

Since a queen attacks along rank, file, and diagonal, it leaving triangles between them unattacked, with a knight-move as the closest vertex of each triangle. While that is immediately obvious to anyone familiar with chess, I was able to solve the problem by thinking about placing white queens in such a way as to allow the largest triangles. Before searching for a solution in that manner, I tried other methods unsuccessfully: hit-and-miss attempts (having at first underestimated the problem); placing queens at knight-moves as one might do for the classic eight-queen problem (see below); utilizing symmetry by placing queens at, say, each corner and at the center; and so on.

How would a computer solve the problem? Well, a wikipedia article suggests, among other methods, a genetic algorithm, which struck my fancy. So I started writing one.

After the skeleton of the algorithm was written and I started tinkering with parameters and the fitness function, I realized this problem would make a great introduction to genetic algorithms and also provide a simple platform for various discussions about the nuances of GAs.

### Leave a Comment

Be the first to comment!

## Leave a Reply