CMPU-365, Spring 2013 Asmt. 4 Due: Thursday, March 7 @ 5:00 p.m. ========> You are encouraged to work in *pairs* on this assignment. There are plenty of *independent* tasks that need to be done for this assignment. So be sure to use a divide-and-conquer strategy within your group. For this assignment, you will implement a SUDOKU solver using the constraint-satisfaction techniques covered in class. In particular, you will: * set up a sudoku game as a constraint satisfaction problem involving 81 variables and 27 constraints * write a sudoku solver that does depth-first backtracking search using the following: o Select the next variable using the MINIMUM REMAINING VALUES (MRV) heuristic; and the DEGREE heuristic as a tie-breaker. (The SELECT-VAR function will implement the MRV heuristic. Another function, BAD-SELECT-VAR, is provided to you for comparison.) o Keep track of the domains of remaining slots/variables. Each time a slot is assigned a value V, then V should be removed from the domains of any other slot in the same row, column or box. ------------------------------------------------------------ REPRESENTING THE GAME OF SUDOKU AS CONSTRAINT SATISFACTION ------------------------------------------------------------ I have written solvers that use a variety of underlying representations for the game. I have found the following to be a good representation and I encourage you to use it. However, if you want to come up with a better representation, go for it! SUDOKU STRUCT The SUDOKU struct should have two fields: SLOTS and DOMAINS. Each should be a VECTOR containing 81 entries, each entry corresponding to one of the little boxes in a sudoku game board. Each "slot" will be either *BLANK* (a global variable) or one of the numbers from 1 to 9. Each "domain" will be a list of the possible values for that slot. So, for example, a completely blank sudoku game would have each "slot" being *BLANK* and each "domain" being a list such as (1 2 3 4 5 6 7 8 9). With this representation, you can easily walk through all the slots in the game using DOTIMES: (dotimes (i 81) ;; do something with ith slot (aref (sudoku-slots game) i)) On the other hand, if you want to simulate a 9x9 walk-through, you can use nested DOTIMES: (dotimes (row 9) (dotimes (col 9) ;; of course, you'll have to convert the pair ;; of numbers (row,col) into the corresponding ;; index: (+ col (* row 9)) should do the trick. )) REPRESENTING CONSTRAINTS Each slot in a sudoku game is governed by three constraints: a ROW constraint, a COLUMN constraint, and a BOX constraint. To avoid having to treat these three kinds of constraints in different ways---which would result in lots of redundant code---the constraints will be represented *uniformly*. The key is to notice that, regardless of its type (i.e., ROW, COLUMN or BOX), each constraint governs 9 slots. Thus, each constraint can be specified by saying which 9 (of the 81) slots it governs. Since each slot corresponds to a numerical index, each constraint can be specified by saying which INDICES (i.e., slots) it governs. For example, the constraint corresponding to the top row involves the indices: 0, 1, 2, 3, 4, 5, 6, 7 and 8. Similarly, the constraint corresponding to the leftmost column involves the indices: 0, 9, 18, 27, 36, 45, 54, 63 and 72. And the constraint corresponding to the top-left BOX involves the indices: 0, 1, 2, 9, 10, 11, 18, 19 and 20. Okay, now there are 9 row constraints, 9 column constraints, and 9 box constraints, for a total of 27 constraints. Since we need to specify 9 indices for each constraint, we can specify the 27 constraints in a 27-by-9 array, which we shall call *CS* (for "constraints"). Each "row" of the *CS* array contains the indices of the 9 slots that it governs in the sudoku game. (Do not confuse a "row" of the *CS* array with a "row" in the sudoko game.) Although it is a bit annoying to initialize the *CS* array, it only has to be done *once*. (The indices governed by a given constraint do not change.) After the *CS* array is initialized, look at what you will be able to do: PROCESS EACH CONSTRAINT: ;; There are 27 constraints, one for each "row" of the ;; *CS* array. Each time through the following DOTIMES, ;; the value of C corresponds to a "row" of the *CS* array. (dotimes (c 27) ;; In the body of the above DOTIMES, you can process ;; the Cth constraint. Since each constraint involves ;; 9 indices, you can use DOTIMES, below, to walk through ;; the 9 indice that are governed by the Cth constraint. (dotimes (i 9) ;; The value of (aref *cs* c i) is one of the 81 slots ;; in the sudoku game. In particular, it is one of the ;; slots that are governed by the Cth constraint. (let (;; INDY is an index from 0 to 80 ;; that is governed by the Cth constraint (indy (aref *cs* c i))) ;; print out the index INDY (format t "indy = ~A, " indy) ;; show the contents of the corresponding slot in ;; the sudoku struct (format t "slot = ~A, " (aref (sudoku-slots game) indy)) ;; fetch the remaining values for that slot (format t "domain = ~A~%" (aref (sudoku-domains game) indy))) )) Notice that in the above code, you don't really care whether you're dealing with a row, column or box constraint. That's the beauty of this representation. ------------------------------------------------- TO DO ------------------------------------------------- * Define your SUDOKU struct as indicated above. You should include a print function that prints out the slots in a 9x9 fashion. It should not print out the domains... that would get a bit cumbersome. * The *CS* array should be a global parameter. It needs to be initialized before it is used. Then it never changes. Since it never changes, you need only do the initialization ONCE. Just once! ==> Please let the computer do most of the work of initializing the *CS* array!! Also: note that you only need one *CS* array. * During the game, you may be interested in a particular slot on the sudoku board. Suppose INDY is the slot (an integer between 0 and 80, inclusive) that you are interested in. Now, there are three constraints that govern that slot: a row constraint, a column constraint, and a box constraint. It can be useful to get your hands on the three constraints that affect INDY. So... Define a function, called GET-CONSTRAINT-INDICES, that takes a single input, INDY, which is an integer between 0 and 80, inclusive. This function should return the three constraints that govern INDY. Well, since each constraint is represented as a row of the *CS* array, this function will actually return (a list of) three indices into the *CS* array. For example, suppose INDY has a value of 1. In that case, INDY refers to the second slot in the top row of the sudoku board. This slot is governed by three constraints: the top row, the second column, and the upper-left box. Suppose that these three constraints are represented in rows 0, 10 and 18 of the *CS* array. (These particular numbers will depend upon how you initialize the *CS* array.) Thus, (GET-CONSTRAINT-INDICES 1) should return the list (0 10 18). NOTE: One way of implementing GET-CONSTRAINT-INDICES is to store eighty-one 3-element lists in an 81-element vector. When you call the function with some index, INDY, you just return the corresponding 3-element list from that vector. Of course, you'll need to initialize that 81-element vector. (ONCE!) ----------------------------------------------------------------- It is very important to get the *CS* array correctly initialized and the GET-CONSTRAINT-INDICES function working correctly. These two jobs can be done independently from the rest of your code and should be thoroughly tested before using them within other functions. ----------------------------------------------------------------- * By the way: (defconstant *blank* '_) (defparameter *num-nodes* 0) * Define a function, called INIT-GAME, that takes a list-of-lists representation of an initial sudoku game. Each entry in the list-of-lists representation is either a number from 1 to 9, or an underscore (i.e., a "blank"). INIT-GAME should create a SUDOKU struct and then walk through the list-of-lists. For each numerical entry in the list-of-lists, it should SETF the corresponding "slot" to the specified number, and SETF the corresponding "domain" to a singleton list. For example, if the numerical entry is 3, then the corresponding slot should have the value 3, and the corresponding domain should be set to (3). (Since this slot is pre-determined to be 3, its list of possible values is just (3).) For each BLANK entry, the corresponding slot should be *BLANK*, and the corresponding "domain" entry should be a list containing all the numbers from 1 to 9. NOTE: The list-of-lists representation of the initial sudoku game is for the user interface only. It is only used to initialize the SUDOKU struct. NOTE: If no grid is given to INIT-GAME, then all slots should default to blank; and all domain lists should default to lists containing the numbers from 1 to 9. Here are some sample list-of-lists sudoku games that you may find useful for testing: (defparameter *s0* ;; change a few entries to _ '((6 2 1 8 5 3 9 4 7) ;; to create an easy sudoku problem (3 7 8 9 6 4 2 1 5) ;; for initial tests of your solver (9 4 5 2 7 1 6 3 8) (1 8 4 6 3 5 7 9 2) (7 6 3 4 9 2 8 5 1) (2 5 9 7 1 8 3 6 4) (5 1 2 3 8 6 4 7 9) (8 3 7 1 4 9 5 2 6) (4 9 6 5 2 7 1 8 3))) (defparameter *s1* '((_ _ 2 _ 9 _ 1 _ 7) (_ 3 8 6 _ _ _ _ _) (4 _ _ _ _ _ _ _ _) (_ _ _ _ _ 5 _ _ _) (_ _ 9 _ 1 _ 3 _ _) (_ _ _ 4 _ _ _ _ _) (_ _ _ _ _ _ _ _ 4) (_ _ _ _ _ 7 9 2 _) (8 _ 6 _ 3 _ 7 _ _))) (defparameter *s2* '((_ _ 5 3 _ _ _ _ _) (8 _ _ _ _ _ _ 2 _) (_ 7 _ _ 1 _ 5 _ _) (4 _ _ _ _ 5 3 _ _) (_ 1 _ _ 7 _ _ _ 6) (_ _ 3 2 _ _ _ 8 _) (_ 6 _ 5 _ _ _ _ 9) (_ _ 4 _ _ _ _ 3 _) (_ _ _ _ _ 9 7 _ _))) More test games are given at the end of this file. * Define a function, called SUDOKU-COPY, that takes an instance of a sudoku struct as its input and returns a copy of that struct as its output. Note that you can use DOTIMES to walk through the "SLOTS" and "DOMAINS" vectors. ==> And you need *not* create copies of the individual domain lists; instead, you can simply use the *same* lists. Why? Because whenever you subsequently modify the domain for some slot, you will SETF the appropriate entry to a *new* list; you will not destructively modify the pre-existing list. * Define a NON-DESTRUCTIVE function, called DO-MOVE, that takes three inputs: a sudoku struct, an index, and a value (i.e., one of the 9 numbers from 1 to 9). It should return a NEW sudoku struct that is the same as the input struct except that the indicated slot has been given the indicated value. (You might want to print out an error message if someone attempts to call do-move on a slot that is not currently blank!) * Define a DESTRUCTIVE function, called REDUCE-DOMAINS!, that takes three inputs: a sudoku struct, an index I, and a value VAL. This function should walk through all the slots that share a constraint with the given slot. (See the GET-CONSTRAINT-INDICES function.) For each such slot, it should remove VAL from that slot's domain. For example, (reduce-domains! sudo 0 3) should remove the value 3 from the domains of all slots in the top row, leftmost column, and upper-left box. It should not affect the domains of any other slots. NOTE: It should *not* remove 3 from the domain of slot 0, because 3 is the value for slot 0! NOTE: The built-in REMOVE function is non-destructive---which is a good thing. You will need to SETF the appropriate element of the DOMAINS vector to the list returned by the remove function. Recall that the SUDOKU-COPY function assumed we wouldn't be destructively modifying the domain lists---which we are not! We are only changing which list a particular element of the DOMAINS vector refers to. * Consider the following, very dumb function: ;;; BAD-SELECT-VAR ;;; ----------------------------------------------------- ;;; INPUT: G, a sudoku GAME struct ;;; OUTPUT: An index i for a currently blank slot; or NIL if ;;; all slots are filled. (defun bad-select-var (g) (let ((slots (game-slots g))) (dotimes (i 81) ;; If a blank slot is found... (when (not (numberp (aref slots i))) ;; Return it ... no matter what! (return-from bad-select-var i))) ;; If got here, then didn't find a blank slot nil)) Copy that function into your lisp file. Next, define a function, called SELECT-VAR, that takes a sudoku struct as its only input. It should return an index, I, for a BLANK slot whose domain has the fewest entries of any blank slot. NOTE: You can do testing with this version of the SELECT-VAR function. Later on, you'll expand it to use the DEGREE heuristic for breaking ties. For convenience, SELECT-VAR should return NIL if there are no blank slots (i.e., if the sudoku puzzle is already completely filled). * Define a pair of functions, called SOLVE-WRAPPER and SOLVE. Each should take a sudoku struct as its only input. The wrapper function should begin by calling the REDUCE-DOMAIN! function for each NON-BLANK entry in the initial sudoku struct. It's okay to use the destructive REDUCE-DOMAIN! function here because there is no possibility of backtracking at this point. (All these moves are forced.) Then it should call the SOLVE function. The SOLVE function should implement the recursive backtracking algorithm for constraint satisfaction. In particular, it should: * use SELECT-VAR (or BAD-SELECT-VAR) to determine which variable to assign a value to next * iteratively walk through the list of values in the domain for that variable, trying to use that value in a potential solution (obtained by recursive function call). * return the completely filled in sudoku puzzle or NIL if no solution found. Remember to call REDUCE-DOMAINS! whenever you assign a value to a variable. Since you are creating new structs for each "move", there is no need to "undo" moves. Be sure to keep track of the number of nodes (i.e., sudoku structs) created. You can use a global *NUM-NODES* variable as in previous assignments. ------------------ INITIAL TESTING ------------------ At this point, you have a sudoku solver that should be able to solve a variety of sudoku puzzles. Start with an easy puzzle (i.e., one that has only a few blanks). To facilitate testing, define a function, SUD, that takes a single input: a list-of-lists representation of an initial sudoku puzzle. SUD should call INIT-GAME to generate the initial sudoku struct, then call SOLVE-WRAPPER and print out the result (either NIL or a solved puzzle). It should also print out the number of "nodes" (i.e., sudoku structs) created. ---------------------------------- IMPROVING THE SOLVER ---------------------------------- * Modify your solver functions to take a keyword argument called USE-SELECT-VAR? The idea is that if this argument is T, then your solver will use the SELECT-VAR function to select the next variable; if NIL, it will use the BAD-SELECT-VAR function. Here's how... (defun solve-wrapper (g &key (use-select-var? t)) ... ) (See Graham for further info on keyword arguments.) Notice that the default value of USE-SELECT-VAR? is T. So, the SELECT-VAR function will be used by default. Note that your SOLVE function will also need a USE-SELECT-VAR? keyword argument, because your SOLVE-WRAPPER function needs to tell the SOLVE function whether to use the SELECT-VAR or BAD-SELECT-VAR. (In fact, that's the only thing that the wrapper function does with this keyword argument!) You'll need to modify the body of your SOLVE function to use either the SELECT-VAR or BAD-SELECT-VAR function, depending on the value of USE-SELECT-VAR? * Use the DEGREE HEURISTIC to break ties in SELECT-VAR. ==> Before proceeding, make sure to keep a backup copy of your SELECT-VAR function! Modify the first line of your SELECT-VAR function to enable it to take an extra keyword argument called USE-DEGREE?. Assuming the first input is called SUDO, here's how you do it: (defun select-var (sudo &key (use-degree? nil)) ... ) Notice that the default value of USE-DEGREE? is NIL, in which case, the function will not use the degree heuristic to break ties. Modify the body of your SELECT-VAR function so that it collects a LIST of *ALL* the indices whose corresponding slots have the smallest domains. If USE-DEGREE? is NIL, then you'll just return the first element of this list (or any randomly selected element). But if USE-DEGREE? is T, then you want to select the variable having the most constraints on remaining variables. What does this mean? Well, for each index INDY, you need to look at the three constraints governing INDY. Walk through the slots governed by these three constraints and figure out how many are currently blank. You want the index INDY that has the most. Incidentally, you'll need to augment the definitions of SOLVE-WRAPPER, SOLVE and SUD to include the USE-DEGREE? keyword argument. For example, if SUD was called with USE-DEGREE? set to true, then it should call SOLVE-WRAPPER (and SOLVE and SELECT-VAR) with USE-DEGREE? set to true. Once you get the degree heuristic working, you should be able to compare your solver's performance with and without the degree heuristic (on the same puzzle). ------------------------------------ FINAL TESTING ------------------------------------ Once all the above is working, test your sudoku solver on (at least the first four) of the games listed at the end of this document. For each game, you should run your solver THREE times: once using SELECT-VAR and the degree heuristic, once using SELECT-VAR without the degree heuristic, and once using BAD-SELECT-VAR. In each case, your wrapper function should print out the number of SUDOKU structs created during the solving process, as well as the final solved puzzle. That way, you can easily compare the performance of the various select-var functions. ===> Be sure to PRINT OUT the values of the USE-SELECT-VAR? and USE-DEGREE? keyword arguments so you can easily tell (in the interactions window) which results go with which variants of select-var. ===> Be sure that your solver is actually finding a bona fide solution to the puzzle in each case! ===> You are encouraged to find "hard" sudoku puzzles on the web. However you are *NOT* allowed to use any algorithms, etc. from the web. ===> If you find any puzzles that your solver doesn't seem to be able to solve, feel free to email it to me. I'd like to collect a bunch of sudoku puzzles that are challenging for our algorithms. IDEAS Use DOLIST or DOTIMES for iterative loops. See Graham's book for details. You can use RETURN-FROM to break out of a loop and immediately terminate a function. For example, if you are in a loop in the body of a function named MYFUNC, then (return-from myfunc 333) would cause the MYFUNC to immediately terminate, with the output value 333. Remember that your code will work best if you compile it first, then load it. Oh, and be sure to set the compiler flags to optimize tail-recursive function calls as in previous assignments. TO SUBMIT Your sudoku code should fit within one file. Your interactions should be saved in a separate text file. As usual, turn in printouts (one per group) and use submit365 (one per group). ---------------------- TEST GAMES ---------------------- Make sure to test your solver THREE times on EACH of the games *T1*, *T2*, *T3* and *T4*, below. (That's a total of 12 tests.) Additional games are given below for your amusement. (See instructions given earlier RE: why you're running your solver three times on each game.) (defparameter *t1* '((_ _ 2 _ 9 _ 1 _ 7) (_ 3 8 6 _ _ _ _ _) (4 _ _ _ _ _ _ _ _) (_ _ _ _ _ 5 _ _ _) (_ _ 9 _ 1 _ 3 _ _) (_ _ _ 4 _ _ _ _ _) (_ _ _ _ _ _ _ _ 4) (_ _ _ _ _ 7 9 2 _) (8 _ 6 _ 3 _ 7 _ _))) (defparameter *t2* '((_ _ 5 3 _ _ _ _ _) (8 _ _ _ _ _ _ 2 _) (_ 7 _ _ 1 _ 5 _ _) (4 _ _ _ _ 5 3 _ _) (_ 1 _ _ 7 _ _ _ 6) (_ _ 3 2 _ _ _ 8 _) (_ 6 _ 5 _ _ _ _ 9) (_ _ 4 _ _ _ _ 3 _) (_ _ _ _ _ 9 7 _ _))) (defparameter *t3* '((8 5 _ _ _ 2 4 _ _) (7 2 _ _ _ _ _ _ 9) (_ _ 4 _ _ _ _ _ _) (_ _ _ 1 _ 7 _ _ 2) (3 _ 5 _ _ _ 9 _ _) (_ 4 _ _ _ _ _ _ _) (_ _ _ _ 8 _ _ 7 _) (_ 1 7 _ _ _ _ _ _) (_ _ _ _ 3 6 _ 4 _))) (defparameter *t4* '((_ _ _ _ _ 3 _ 6 _) (_ _ _ _ _ _ _ 1 _) (_ 9 7 5 _ _ _ 8 _) (_ _ _ _ 9 _ 2 _ _) (_ _ 8 _ 7 _ 4 _ _) (_ _ 3 _ 6 _ _ _ _) (_ 1 _ _ _ 2 8 9 _) (_ 4 _ _ _ _ _ _ _) (_ 5 _ 1 _ _ _ _ _))) (defparameter *t5* '((_ _ 6 _ _ _ _ 9 _) (_ _ _ 5 _ 1 7 _ _) (2 _ _ 9 _ _ 3 _ _) (_ 7 _ _ 3 _ _ 5 _) (_ 2 _ _ 9 _ _ 6 _) (_ 4 _ _ 8 _ _ 2 _) (_ _ 1 _ _ 3 _ _ 4) (_ _ 5 2 _ 7 _ _ _) (_ 3 _ _ _ _ 8 _ _))) (defparameter *t6* '((_ _ _ 2 _ _ _ 6 3) (3 _ _ _ _ 5 4 _ 1) (_ _ 1 _ _ 3 9 8 _) (_ _ _ _ _ _ _ 9 _) (_ _ _ 5 3 8 _ _ _) (_ 3 _ _ _ _ _ _ _) (_ 2 6 3 _ _ 5 _ _) (5 _ 3 7 _ _ _ _ 8) (4 7 _ _ _ 1 _ _ _))) (defparameter *t7* '((1 _ _ _ 7 _ _ 3 _) (8 3 _ 6 _ _ _ _ _) (_ _ 2 9 _ _ 6 _ 8) (6 _ _ _ _ 4 9 _ 7) (_ 9 _ _ _ _ _ 5 _) (3 _ 7 5 _ _ _ _ 4) (2 _ 3 _ _ 9 1 _ _) (_ _ _ _ _ 2 _ 4 3) (_ 4 _ _ 8 _ _ _ 9))) (defparameter *t8* '((_ 2 _ _ _ _ _ _ 7) (_ 7 _ _ _ 4 _ 1 _) (9 _ 5 _ _ _ _ _ _) (_ 8 _ 6 3 _ _ _ 2) (7 _ _ _ _ _ _ _ 1) (2 _ _ _ 1 8 _ 6 _) (_ _ _ _ _ _ 4 _ 9) (_ 3 _ 1 _ _ _ 2 _) (4 _ _ _ _ _ _ 8 _)))