The Boxes and Balls problem is to put n balls labelled {1,...n} into 3 boxes so that for any triple of balls (x,y,z) with x+y=z, they are not all in the same box.
The problem can be formulated as an 0-1 problem using the variables, Mij (i in [1,n], j in [1,3]) with Mij true iff ball i is in box j. The constraints are that a ball must be in exactly one box, Mi1 + Mi2 + Mi3 = 1 for all i in [1,n]. And for each x+y=z and j in [1,3], not (Mxj and Myj and Mzj). This converts to, (1-Mxj) + (1-Myj) + (1-Mzj) ≥ 1 or, Mxj + Myj + Mzj ≤ 2.
Your job is to solve the Boxes and Balls problem (also known as Schur's lemma) by creating a function ASSIGN that takes a single argument N and returns a list of N elements, each element i (1 to N) has a value j (1 to 3) representing that ball i is in box j. The function should return nil if there is no valid assignment.
Note, for 3 boxes, the problem has a solution for 13 or less balls.
For example, if your program is invoked with:
(assign 9)
A possible output of your program may be:
(1 1 2 1 2 2 3 3 3)
This means that box 1 has balls 1, 2, and 4; box 2 has balls 3, 5, and 6; and box 3 has balls 7, 8, and 9.
Besides conforming to the input and output guidelines mentioned above, your program must implement a depth first search with forward checking after each variable assignment. Remember that forward checking looks at the variables that have already been assigned values, and by examining the constraints, shrinks the domain on the remaining unassigned variables. If any variable domain becomes empty, you should backtrack.
Do not use any heuristics at this time.
Test your program on all values of N up to 13 and show the trace in your homework's output file.
Answer the following questions in comment blocks at the very end of your lisp file:
What is the best choice for the variables and their domain values for this CSP? Justify the use of this encoding of the problem over other choices for variables and domain values.
Name two heuristics that might speed up the search process.
For partial credit on a non-functioning program, make sure you clearly describe the exact inputs and outputs of each function, and what the function is supposed to do.