Assignment 3 Problems 7, 9, and 10
Here are the details for tests you should run for problems 7 and 9,
and details for the bonus problem 10.
Problem 7
Run your Manhattan distance heuristic and the squared Manhattan
distance heuristic on the following puzzles from
a3puzzles.scm
- 8-puzzle #5, using (ep5) and (ep5^2)
- 8-puzzle #6, using (ep6) and (ep6^2)
- 15-puzzle #2, using (fp2) and (fp2^2)
- Hughes, using (hughes) and (hughes^2)
Turn in a table detailing your results. Include the following in your
table:
- the length of the path found
- whether this path is optimal
- number of states evaluated
- running time
Problem 9
Run your heuristic function on the following puzzles included in
a3puzzles.scm
- Hughes, using the (my-hughes) procedure
- The "w1" puzzle, using the (my-w1) procedure
- The "w2" puzzle, using the (my-w2) procedure
- The "w3" puzzle, using the (my-w3) procedure
- Ma's puzzle, using the (my-mas) procedure
You can abort a run that takes more than 3 minutes.
In addition to the clear (prose) description of your heuristic and
whether it is admissible and monotonic or not (with a justification),
include a table detailing:
- the length of the path found
- number of states evaluated
- running time
(Note that "whether the path found is optimal or not" is not part of
the table for this problem.)
Problem 10
For this bonus problem, devise a heuristic that can solve one or more of the
following puzzles in 5 minutes or less of running time (and without
running out of memory using the -heap 4000 option to
Scheme). These puzzles are all included in a3puzzles.scm.
- The Ten Block puzzle --- write the ten-block-heuristic
- Any of the "p" puzzles (p[1-6]) ---
write any of the p[1-6]-heuristic procedures
- The Century Puzzle --- write the century-heuristic procedure
- Either of the Piano Moving puzzles --- write the
piano-moving-1-heuristic or the piano-moving-2-heuristic
Although you will submit your code electronically, we will run a test
to verify your heuristic offline, so you will not receive results immediately.
Don't forget to turn in written information about your heuristic as
for Problem 9.