Blog

For Project 1 you should use the state transition system concepts from
Chapter 5 in *Formal Reasoning About Programs* to design a solution to
the $n$-queens problem. Your solution should take a non-negative
integer, $n$, and output the first solution found for the $n$-queens
problem. If there is no solution either return nothing or an empty
board, whichever you find easier. Recall that a solution to the
n-queens problem places $n$ queens on an $n\times n$ chess board so
that no queen can attack any other queen.

A couple of hints that might prove useful. You can represent the chess board as an $n\times n$ list. However, it is simpler to use a list of length $n$ where each entry represents a column. Because every column contains exactly one queen, each list entry contains the position in the column of the queen residing in it.

When thinking about state transitions and the accumulator model consider the input being the number of unplaced queens and the accumulator being the board completed so far. Place a queen in column 0, then in column 1, and so forth through column $n-1$.

Demonstrate your solution by:

- Proving/finding a solution to the $4$-queens problem.
- Proving/finding there is no solution for the $2$-queens problem.