Programming Assignment 4 - Solution

In this assignment, you will write a pure LISP program to solve the N queens problem. The problem is to place N queens on an NxN chessboard so that no two queens are in the same row, column, or diagonal.  If you place each queen in a separate row, then a solution can be described by giving the column numbers of each of the queens in order by row.  For example, the list (3 1 4 2) represents a solution to the four queens problem. Note that the numbering of columns starts at 1. Your top-level function, called QUEENS, should take a single argument N, and return a single solution to the N-Queens problem.  If there is no solution, it should return nil. Treat this problem as a constraint satisfaction problem (CSP) and solve it using depth- first-search while detecting states that violate constraints. Note that you are not allowed to use local search algorithms to solve this problem. Also, you cannot use any closed-form solution (i.e., using an equation to solve the N queens problem). Submit your commented LISP program in a file named hw4.lsp via CCLE

 

 

Your algorithm will be evaluated by two measures: correctness and speed.  80% of the grade will be based

on correctness.  20% will be based on the rank of your algorithm's speed with respect to the other correct

a!lgorithms submitted by your fellow students.

NOTE: Please write your code using good lisp style. You can use any lisp functions, predicates or opera-

tors introduced in class or in past assignments. You may also use any auxiliary functions you wish to write.  Do not, however, use global variables.