Lisp is a functional language: everything and anything can be expressed as a function. One way of defining a constant is to use a constant function, that is, a function whose value is a constant. For example,

(defun five ( ) 5)

Then you can call this function with no arguments:

CL-USER 23 > (five)
5

The mazes you need to solve can be expressed as constant functions. For the Lisp assignment, I'll ask you to solve three mazes. Here they are:

(defun maze1 ()
   '( (1 2 4) (2 1 3) (3 2 6)
      (4 1 5) (5 4 8) (6 3 9)
      (7 8) (8 5 7 9) (9 6 8) ) )


(defun maze2 ()
  '( (1 6) (2 3) (3 2 4 8 23) (4 3 24) (5 10)
    (6 1 7) (7 6 8) (8 3 7 13) (9 14) (10 5 15)
    (11 16) (12 13) (13 8 12) (14 9 15 19) (15 10 14)
    (16 11 20 17) (17 16 18 22) (18 17 19 23) (19 14 18) (20 16)
    (21 25 22) (22 17 21) (23 18 3) (24 4) (25 21) ) )


(defun maze3 ()
  '( (1 11) (2 1 12 3) (3 2 13 4) (4 3 14 5) (5 4 15 6)
    (6 5 16 7) (7 6 17 8) (8 7 18 9) (9 8 19 10) (10 9 20)
    (11 1 21) (12 11 2 22 13) (13 12 3 23 14) (14 13 4 24 15) (15 14 5 25 16)
    (16 15 6 26 17) (17 16 7 27 18) (18 17 8 28 19) (19 9 18 29) (20 19 10 30)
    (21 11 22) (22 21 12 23) (23 22 13 24) (24 23 14 25) (25 24 15 26)
    (26 25 16 27) (27 26 17 28) (28 27 18 29) (29 28 19) (30 29 20) ) )

I suggest that you cut and paste these three constant functions into your own program. Once you have these functions defined, you can use calls such as (for instance):

(solve (maze1) 2 5)

Assignment: Use the above mazes to find the following six paths:

Comments:

• Don't try to write complicated functions. I cannot emphasize this enough. If you see a way to break a function into simpler functions, do it. My solution to the maze problem consists of 11 functions, averaging less than four lines each.
  
  
• It's a good idea to test each function by itself. Lisp does not have the concept of a main program--you can call any function, any time. Use this fact to your advantage.
  
  
• You will probably have some functions that do similar things. It's a good idea to name each function carefully, to help you remember what it does--and to put a comment at the top of each one.
  
  
• Maze 1 is the same maze that I used as an example in the assignment.
  
  
• Maze 2 isn't exactly rectangular.
  
  
• Maze 3 has some one-way paths in it. For example, you can go from 2 to 1, but you can't go from 1 to 2.
  
  
• The optimizations that I talked about on the assignment page (getting rid of duplicate nodes) are necessary. You will not be able to solve these mazes unless you do the optimizations.
  
  
• You will probably need to use the maze as an argument to almost every function you write.
  
  
• The algorithm that I outlined separates the problem into two parts: finding a list of lists containing a path--((5 9) (4 2 6) (1 3) (2)) in my example--and extracting the actual path from this list of lists. I found the second part to be shorter but harder.

Getting Started:

You need to start with a list (which I called paths in the assignment) and add to this list as you go along. However, the function call (solve (maze1) 2 5) above does not mention a paths variable. Where does it come from?

Several people have now tried to use (defun paths () ()), analogous to the way I have defined the maze constant functions above. The problem is that this makes paths into a constant function, and you need a variable.

The correct solution is to create an extra function, and pass it a null list as a parameter.Like so:

(defun solve (maze start finish)
    (solve-2 maze start finish ()) )


(defun solve-2 (maze start finish paths)
    ...