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: Puzzle-5BQ-3WQ

A queen attacks along rank, file, and diagonal, leaving triangles between them un-attacked. The square corresponding to one knight’s move corresponds to 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.

So 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. I hope to write about that later, especially if there’s interest.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s