EECS 843

Programming Langauge Foundation II


Project 1

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:

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