********************************************************************** Homework Assignment 1 CSE 150, UCSD Fall 2002 Due: Thursday, October 17th, midnight ********************************************************************** >>> SUMMARY: This assignment is the first in a series of three which will introduce you to the notion of "state space search" in AI. In this assignment, we will define various "helper" functions that will be used in a program to solve the 8-puzzle. Note that at the end of this assignment, we will not have done anything to actually *solve* the 8-puzzle yet! The 8-Puzzle is a problem involving 8 numbered, movable tiles set in a 3 x 3 frame. One cell of the frame is always empty thus making it possible to move an adjacent tile into the empty cell. For example, when you buy it at the store, the puzzle may have the configuration on the left below. The problem is to find a series of moves that leads you to the goal on the right, no matter what the initial configuration. (Actually, some faulty puzzles make the problem impossible! Fortunately for you, we will not give you any such faulty puzzles!) ; +---+---+---+ +---+---+---+ ; | 2 | 8 | 3 | | 1 | 2 | 3 | ; +---+---+---+ +---+---+---+ ; Initial: | 1 | 6 | 4 | Goal: | 8 | | 4 | ; +---+---+---+ +---+---+---+ ; | 7 | | 5 | | 7 | 6 | 5 | ; +---+---+---+ +---+---+---+ Our representation of the 8-puzzle will simply be a list of elements, read from left-to-right, top-to-bottom. We will use "e" to represent the empty square in the list. So our representation of the initial state above would be: (2 8 3 1 6 4 7 e 5) and the goal state is: (1 2 3 8 e 4 7 6 5) >>> RULES: In writing your function definitions, you may use any built-in LISP function, special form, or macro introduced in Chapters 1 through 6 in the Winston and Horn text, except for SET, SETF, and SETQ. Also, you may not use any iteration constructs such as DO, DOTIMES, DOLIST, or LOOP --- so you will be writing recursive function definitions without assignment statements: real functional programming! SETQ and SETF will, however, be useful while you are *developing* your code, to define test arguments. For example: USER: (setq test-arg '(2 8 3 1 6 4 7 e 5)) (2 8 3 1 6 4 7 E 5) USER: (goal-state test-arg) NIL MAKE SURE SUCH "TESTING" CODE IS NOT IN YOUR TURNED IN HOMEWORK FILE! You may discuss your program with other students or the TA or the professor. However, you may not copy anybody else's program. In writing your code, you are on your own. >>> ASSIGNMENT: This assignment has six parts, described below. Each part involves defining a function with a specified name. (You may find it useful to define some other functions too, if you wish.) All these function definitions should be put in a file named "hw1.cl" so that when that file is loaded into LISP, evaluating calls to the functions will work as required. Make sure the file name and function names are spelled correctly; your assignment will be graded in part by a computer program, and computer programs don't handle misspellings very well. Make sure your programs are commented in acceptable LISP style! Your file "hw1.cl" must be submitted using the "turnin" utility no later than the due time deadline specified above. Once you have done a "prep cs150f", just type "turnin hw1.cl" to submit your solution file. ---------------------------------------------------------------------- Part I. Define a function named GOAL-STATE. GOAL-STATE takes one argument, a list representing a state of the 8-puzzle, and returns T if the argument is the goal state, and NIL otherwise. For example: USER: (goal-state '(2 8 3 1 6 4 7 e 5)) NIL USER: (goal-state '(1 2 3 8 e 4 7 6 5)) T You do not have to check whether the state handed to this function is a legal state of the board. Hint: This is incredibly simple! ---------------------------------------------------------------------- Part II. Define a function named GET-DIRECTION. GET-DIRECTION takes one argument, a list consisting of a move, and the resulting state of the board. Moves are most efficiently represented in terms of moving the empty square. Depending on the position of the empty square, it could move in 2, 3 or 4 directions, labeled U, D, L, and R, for up, down, left and right, respectively. For us, moves will then be represented by the template: ( ) For example, USER: (get-direction '(U (1 2 3 8 e 4 7 6 5))) U Simple, right? This is called an access function. Usually, things like this are done with macros, rather than functions. We will learn about macros in LISP later. ---------------------------------------------------------------------- Part III. Define a function named GET-STATE. GET-STATE is the second access function for moves, returning the resulting state from a move. For example, USER: (get-state '(U (1 2 3 8 e 4 7 6 5))) (1 2 3 8 E 4 7 6 5) ---------------------------------------------------------------------- Part IV. Define a function named SAME-STATE. SAME-STATE takes two arguments, each one a move as represented above, and returns T if the two states are the same, and NIL otherwise. Note that it matters not how the state is reached. Thus: USER: (same-state '(u (1 2 3 8 e 4 7 6 5)) '(d (1 2 3 8 e 4 7 6 5))) should return T. Be sure to use GET-STATE in the definition of SAME-STATE. This makes your code more modular. If you change the representation of moves, all you should need to change are the access functions. ---------------------------------------------------------------------- Part V. Define a function named PATH. PATH takes one argument, which is a list of moves. Assume the list is in reverse order, with the first move at the end of the list, and the last move at the beginning of the list. PATH should return the list of move directions in the correct order. I.e., USER: (path '((r (1 2 3 8 e 4 7 6 5)) (d (1 2 3 e 8 4 7 6 5)) (l (e 2 3 1 8 4 7 6 5)) (u (2 e 3 1 8 4 7 6 5)) (u (2 8 3 1 e 4 7 6 5)) )) (U U L D R) which is one path from the initial state given in the SUMMARY above to the goal state. Hint: You should use your access function GET-DIRECTION, and you will find the built-in functions MAPCAR and REVERSE helpful. ---------------------------------------------------------------------- Part VI. Define a function named REMOVE-REDUNDANT. REMOVE-REDUNDANT takes two arguments, both of them lists of moves. REMOVE-REDUNDANT should return the first list, with any moves with states in the second list removed. For example: USER: (REMOVE-REDUNDANT '((R (1 2 3 8 e 4 7 6 5)) (U (e 2 3 1 8 4 7 6 5)) (D (1 2 3 7 8 4 e 6 5))) '((D (1 2 3 e 8 4 7 6 5)) (L (e 2 3 1 8 4 7 6 5)) (U (2 e 3 1 8 4 7 6 5)) (U (2 8 3 1 e 4 7 6 5)))) ((R (1 2 3 8 E 4 7 6 5)) (D (1 2 3 7 8 4 E 6 5))) USER: (REMOVE-REDUNDANT '((R (1 2 3 8 e 4 7 6 5)) (U (e 2 3 1 8 4 7 6 5)) (D (1 2 3 7 8 4 e 6 5))) nil) ((R (1 2 3 8 E 4 7 6 5)) (U (E 2 3 1 8 4 7 6 5)) (D (1 2 3 7 8 4 E 6 5))) This function will be useful in our search routine to avoid paths that return to the same state again - a lot of work for nothing! Hint: REMOVE REDUNDANT will be recursive. You may find the builtin predicate MEMBER useful, when the :TEST used is your function SAME-STATE.