Method for finding solutions to the Eight Queens Puzzle First, you can implement this in a several ways. - Write a program
- Do it by hand
- Get your little brother to do it for you
- Just look at the answer
An algorithm to find the solutions is simple, and relies on the following fact: since there are eight rows and eight columns, and also eight queens, each row and each column must contain one and only one queen. So, by placing a single queen on the b oard, and then another, and another, making sure each is legal, you can develop an algorithm to find any and all correct answers. If you are doing this manually, you can just look to see. If you are letting a computer do the boring work (this is an OK but wimpy solution) you can have the chessboard be represented by an 8x8 array, and a queen will be illegally placed if it: - Has the same column number as another piece already placed
- Has the same row number as another piece already placed
- The slope between it and another placed piece is ± 1
So, since each column must have one queen, you can algorithmically choose a place for the queen in column 1, then column 2, etc. When you can not place the next queen, (when none of the spaces in its column are free) you can move back to the previous column and find the next square that works. This could probably be coded recursively in about 5 lines. By using this algorithm, you will find all possible combinations that will work. Additionally, you only need to go through the first four rows of the first queen, because the last four will only give the solutions you arrived at initially, although pe rhaps reflected or reversed. Solving in this manner will give all 12 solutions, with most solutions being found eight different times, because there are four directions the solution can be in, and each of these can be reflected. Link to Shane's Home Page | Return to the Eight Queens Page Shane Mueller <smueller@obereed.net> http://obereed.net/queens/method.html |