Project I - Requirement Specifications
Solving Generalized 8-puzzle(n-puzzle) problem.
Deadline: October 12, 2005
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.
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 :
Code 80%Project Report 20%