Prepared by Surendra Singhi

The project specification may have few minor modifications. So, please keep looking on this page and myASU for the changes.

Please note: The highest standards of academic integrity are expected of all students. The failure of any student to meet these standards may result in suspension or expulsion from the university and other sanctions as specified in the academic integrity policies of the individual colleges. Violations of academic integrity include, but are no limited to, cheating, fabrication, tampering, plagiarism, or facilitating such activities. If you are not sure of something or in doubt then please contact the TA or the professor.

In this project you are required to find a solution for the generalized 8-puzzle problem.

Generalized 8-puzzle problem

Please refer to the text book page 64-65 for a description of the problem. You are required to solve a generalized form of the problem (say 15-puzzle, or 24-puzzle etc.). Your lisp program would be given a n*n - 2d-array containing the initial state. You are required to return a list of intermediate configuration containing the solution. The example below will make it clearer.
Besides taking the initial configuration your program should also take the heuristic function as the second input parameter. The driver function should be called `n-puzzle'. Your program is expected to use A* algorithm to find the solution.

You are supposed to write three heuristic functions.The first two functions should implement the heuristics h1 and h2 described in the top of page 106. These heuristic functions should be called `simple-heuristic' and `Manhattan-heuristic' and take a single input argument a 2d-array containing the puzzle's current state. The third function called `Nilsson-heuristic' should be as follows:

Nilsson's Sequence Score: h(n) = P(n) + 3 S(n)

P(n) is the Manhattan distance of each tile from its proper position.

"The quantity S(n) is a sequence score obtained by checking around the non-central squares in turn, allotting 2 for every tile not followed by its proper successor and 0 for every other tile, except that a piece in the center scores 1."

This might be easier to understand if you know that the goal state that Nilsson uses is represented by: (#2A(1 2 3) (8 0 4) (7 6 5)). This heuristic is not admissible.

Nilsson, N. (1971) Problem-Solving Methods in Artificial Intelligence. New York, NY: McGraw Hill.

A sample initial state to the program may look like this one (0 denotes a blank/space position).

1	3	0
8	2	4
7	6	5

Your program should return a list containing the following:

1	3	0
8	2	4
7	6	5

1	0	3
8	2	4
7	6	5

1	2	3
8	0	4
7	6	5

CL-USER> (n-puzzle (make-array '(3 3) :initial-contents '(( 1 3 0)(8 2 4)(7 6 5)))
                   #'Nilsson-heuristic)
(#2A((1 3 0) (8 2 4) (7 6 5)) #2A((1 0 3) (8 2 4) (7 6 5))
 #2A((1 2 3) (8 0 4) (7 6 5)))
CL-USER> 

Project Submission Guidelines

You need to submit the soft copy of the project via myASU Assignments section.

• You should submit "one" LISP file named {last name}-{first-name}.lisp
• Submit the file through Assignment section in myASU.
• Please make sure that the file is in simple text format and not in document (Microsoft Word or some other document) format.
• The first line in the file should be your name. Please comment it.
• If you want to label portions of your code as solution to part one, part two, etc., or you want to write the problem statement in the lisp file(it is not needed, you can do it if you feel it is convenient for you), please make sure that they are all commented.
• There should be no syntax errors in the program(like forgotten closing brackets, misplaced semicolon unmatched double quotes, etc.,)
• Please try to comment whatever code you have written for debugging purpose. The function execution calls like (n-puzzle ....) should all be commented.
• Make sure your program executes in clisp (ideally it should execute in Allegro too).
• Don't use #t it is something from Scheme and not part of ANSI Lisp. Allegro Lisp supports it but clisp doesn't.
• Please don't change the package name or create functions in different package.
• Please follow the lisp style guide available at http://www.lisp.org/table/style.htm

Also, you are supposed to turn in a hard-copy report either in class or at the CSE department office. The report should be brief and contain a discussion on any one aspect of the project of your interest. It could be like other heuristics for the problem, advantage/disadvantage of using A* as the search algorithm, any other better search strategy for the problem. the report should be analytical and should also contain the difficulties you encountered, interesting observations, etc.

Grading

The distribution of grades for the project is :

Project Report  20%