Saturday, January 15, 2011

8 Queens Puzzle

The 8 Queens puzzle is one of the oldest problems. First proposed by the chess player Max Bezzel in 1848, this puzzle has been a favourite of both chess players and mathematicians. Franz Nauck in 1850 extended the puzzle to a n-queens problem on an nxn chessboard. Later in 1972, Edsger Dijkstra used this problem to explain the basics of structured programming using the depth-first backtracking algorithm.

Eight chess queens need to be placed on a 8x8 chessboard in such a way that each of them cannot capture any other queen. Thus, no two queens should be on the same row, column or diagonal.

The puzzle has 92 different solutions which includes 12 unique solutions.

More Details on Wiki
A mathematical solution
Recursive solution in Java
Detailed Algorithmic approach

No comments:

Post a Comment