FUNDAMENTALS OF ARTIFICIAL INTELLIGENCE
The task is to 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. 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, return nil. Treat this problem as a constraint satisfaction problem (CSP) and solve it using depthfirst-search while detecting states that violate constraints. Try to minimize the number of functions that you write, and make each one meaningful. Along with your code named hw4.lsp, turn in the time required and the values returned by your top-level function at least for every value of N from 1 to 10 in a file named test.txt. Be sure to check all of your solutions.
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 algorithms submitted by your fellow students. The top 3 fastest algorithms will receive recognition!
As usual, you are not allowed to look at any code that relates to solving N-Queen problem. However you are allowed to play this game (e.g by finding this challenge online) to gain more intuition . If you discuss the solution with anyone in class, please include their name and student id in the header of your hw4.lsp.
NOTE: Please write your code using good lisp style. You can use any lisp functions, predicates or operators introduced in class or in past assignments. You may also use any auxiliary functions you wish to write. Do not, however, use global variables.
