Tuesday, September 25, 2007

Eight Queens Puzzle

Recently, my wife decided to re-visit some of our old games and was playing The 7th Guest.  Several of the puzzles in that games are chess based, and one is the Eight Queens Puzzle.

I decided it would be a fun and fairly simple task to build a JavaScript implementation of that game which would also attempt to solve it.

My first pass merely randomly placed queens on the board (and subsequently removed the conflicting pieces) as a brut force method to stumble upon the solution.  I let that version run all day and it never found a solution -- which according to the Wikipedia entry, there are 92 of.

Then I added the logic she used to solve the puzzle which was to only add a new queen if it either didn't remove any others, or only removed one other queen.  That technique worked surprisingly well usually only requires the program to take from the 10s to the low 100s of attempts before it has a solution and it much less complex that the solution described in the Wikipedia entry.

In only took a couple hours to build, and in the end, I have a very simple program which will allow you to try your hand at solving the puzzle yourself, or can quickly figure out a solution from whatever you have on the board when you give up.


No comments: