©iCarnegie - Distribution or copying without permission is prohibited.
APPLICATION DESIGN CHOICES
nQueens Puzzle Overview
©iCarnegie - Distribution or copying without permission is prohibited.
NQUEENS PUZZLE OVERVIEW
APPLICATION DESIGN CHOICES
Consider a chess board with just Queens on it. To simplify, let's use a small board to describe the problem
space, as pictured below. A Queen can move in up-down, right-left, and diagonal directions. This limits the
safe places for other Queens on the board. Our problem, for a given chess board, is to figure out all the
safe places where Queens can reside. The objective of the game is to place a Queen on each row; if that is
not possible, then the arrangement has failed and a new set of placements must be tried. Figure 1
illustrates a completed board once a solution is found.
Figure1: A Completed Board
Are there other solutions for that board? Once you have completed this exercise, you can answer that
question by specifying a board of size 4 (4 by 4) and ask for "all" solutions.
There are subtle differences between the Maze problem and its use of recursion, and the NQueens
problem and its use of recursion. Consider this: in the Maze problem, you want the program to return the
single Maze board that has the solution path from start to goal. In the NQueens problem, you want the
program to return all boards which have correct solutions. That means you will look for solutions inside a
loop structure that runs until no further solutions are found.
If you follow the narrative above, you see that an algorithm to solve the NQueens problem is available. It is
an algorithm that places one queen in each row, but only where it is safe to do so. Obviously, the top row,
where the algorithm begins, is wide open. Any cell is safe. After that, all bets are off.
