The algorithm for queens.hs is to place a queen in each column of the chess board, starting on one side of the board and working towards the other side.

Specifically, we want to solve the "8 Queens Problem" by solving the "n Queens Problem" for n starting with 1 and going up to 8.

Start by placing a queen in each position of the first column. These are all "safe" from attack because there are no other queens on the board. Remember these 8 board layouts as our set of solutions to the "1 Queen Problem".

To solve the "n Queens Problem", take the list of board layouts from solutions to the "n-1 Queens Problem" and for each board, try adding a queen to each of the rows in the n-th column. If the new queen is "safe", add this board to the set of solutions to the "n Queens Problem".

Haskell's excellent support for recursive lazy stream definitions makes this efficient.

To make it (a little) faster, I recognize that any chess board layout with any number of queens on it that are all safe from each other can be flipped horizontally, vertically or both and still be a solution. So for the first column, we only need to consider the queens in the first 4 rows.

Valid XHTML 1.0 Transitional