Divine Lunacy

There are ninety-two ways to place eight queens on a standard chess board such that no queen can take any other queen, but what are they? This is the question that I have spent the last three days pondering. I surely could have ran to google crying, but what fun is in that? Being the weirdo that I am, I took it upon myself to think up a fairly good algorithm and then put it to code. If you value your sanity, you should skip reading the rest of this post…

The algorithm I decided to use is a simple breadth-first search algorithm. It begins in the first column of the chessboard, by placing a queen in the first available row. In each subsequent column, a queen is placed in the first available row. When a column that doesn’t have any ‘available’ spaces is encountered, the queen in the previous column is moved to the next available row. When a queen is successfuly placed in the eigth column, the column is cleared and the queen in the (n-1)th column is moved to the next available row. When the first column is reached, and a queen cannot be placed (because there are no rows left to test), all of the solutions have been found. The bit of PHP I threw together to do this for me can successfuly find all ninety-two solutions to the eight queens problem in .27 seconds. It took me five periods to find the first one by hand…

And now for that anecdote I said I might include. Josephus and forty other jewish people were trapped in a cave surrounded by romans. Rather than give themselves up to the romans, all but Josephus and one other man resolved to committ suicide. Josephus proposed that this be done in an orderly fashion: they were to stand in a circle and kill every third person. The remaining person would then committ suicide. Josephus lived to tell the story…

This entry was posted on Saturday, January 14th, 2006 at 2028:35 and is filed under Mathematical. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.