AMC 153/CS 195.C2 (Second Semester, 2001-2002)

This is the website for the class "Parallel and Distributed Computing".

Statement of the Problem

In chess, a queen can move as far as she pleases, horizontally, vertically, or diagonally. A chess board has 8 rows and 8 columns. The standard 8 by 8 Queen's problem asks how to place 8 queens on an ordinary chess board so that none of them can hit any other in one move. The size of the chess board can be increase to add complexity to the problem.

The Algorithm

The program finds solutions by starting with a queen in the top left corner of the chess board. It then places a queen in the second column and moves it until it finds a place where it cannot be hit by the queen in the first column. It then places a queen in the third column and moves it until it cannot be hit by either of the first two queens. Then it continues this process with the remaining columns. If there is no place for a queen in the current column the program goes back to the preceding column and moves the queen in that column. If the queen there is at the end of the column it removes that queen as well and goes to the preceding column. If the current column is the last column and a safe place has been found for the last queen, then a solution of the puzzle has been found. If the current column is the first column and its queen is being moved off the board then all possible configurations have been examined, all solutions have been found, and the algorithm terminates.

Complexity

A measure of the difficulty of the problem is given by the number of moves the above algorithm takes to find the first solution. This number of course tends to go up as as N increases, but it does not increase monotonically. The Table nearby gives the required number of steps. It is ordered by increasing difficulty. So the easiest board to find a solution on is the 5 by 5 board, and the 22 by 22 board is about 65 times as hard as the 23 by 23 board, and about 41,000 times as hard as the 8 by 8 board.