Assignment 3 Electronic sumbission information

The policy and procedure for electronic submission is basically the same as it was for Assignment 1. (See below for differences.) The syntax checker has become slightly more liberal --- it now permits map and apply. Also note that procedures that take a variable number of arguments will not pass the syntax checker.
This assignment has three independent web testers. You must submit your code to each web tester in order to receive points for the respective problem(s).
You can put all your code in one file and submit the same file to all three web testers; however, you only need to submit code for the respective problems for each web tester. That code however, must stand alone ---- any procedures it needs (that are not in the support code) must be included in that file.
You have three submissions allowed for each of the first two web testers (the one for Problems 1-4 and 6 and the one for Problem 8). Late penalties and third-sumbission discounts are independent for these two web testers. The maximum score of your submissions on each web tester is taken to be your score for the respective problem(s).

The 18 points for Problem 8 are split up into 2 parts:

6 points for some basic tests
12 points based on CPU time and optimality

The manhattan distance heuristic is being used as a baseline for this test. You should have no trouble devising some heuristic that is better than the manhattan distance heuristic for this class of sliding block puzzles (where only the position of a few pieces are specified in the goal state).

Keep in mind that the manhattan distance heuristic can be part of your heuristic, even though it is not a particularly good heuristic for this class of puzzles. In fact, you do not have any excuse not to return a heuristic value that is less than the manhattan distance to the goal, because you can simply take the maximum between it and your heuristic.

Here's how the web tester will determine you score for this problem:

Basic tests: your heuristic is given a number of states for which we know the optinal solution length.

  Heuristic generates an error: 0 points
  Heuristic returns ANY values less than the Manhattan Distance heuristic: 2 points
  Heuristic returns most values very close to the Manhattan Distance heuristic: 4 points
  Heuristic is significantly different than the Manhattan Distance heuristic: 6 points

Performance tests: your heuristic is run on four test problems. Performance is graded based on both optimality and CPU time consumed, as follows:

 OPTIMALITY
  Puzzle 1: 24 moves = 3 points, 28 moves = 2 points, 32 moves = 1 point, >32 moves = 0 points
  Puzzle 2: 14 moves = 3 points, 18 moves = 2 points, 22 moves = 1 point, >22 moves = 0 points
  Puzzle 3: 33 moves = 3 points, 38 moves = 2 points, 43 moves = 1 point, >43 moves = 0 points
  Puzzle 4: 31 moves = 3 points, 36 moves = 2 points, 41 moves = 1 point, >41 moves = 0 points
 CPU TIME
  Puzzle 1: 4 seconds or less = 9 points, 6 sec = 6 points, 9 sec = 3 points, >9 sec = 0 points
  Puzzle 2: 9 seconds or less = 9 points, 10.5 sec = 6 points, 12 sec = 3 points, >12 sec = 0 points
  Puzzle 3: 54 seconds or less = 9 points, 56 sec = 6 points, 57 sec = 3 points, >57 sec = 0 points
  Puzzle 4: 47 seconds or less = 9 points, 65 sec = 6 points, 83 sec = 3 points, >83 sec = 0 points

Problem 10 testing will be done offline; the webtester will simply run the syntax checker and the pretester. We will only test the most recent submission.
Submit your code for this assignment:
If you find some error or have some problem with the web tester, let us know by sending email to aistaff@cs.rpi.edu. You do not need to send us any code that you uploaded --- we already have it.