Big congratulations to everyone who worked on problem set 9! It was definitely a very good test of designing a short, but still complex program.
Whether the design you worked on worked a lot, a little, or less than a little, this will have been a very good learning experience leading up to the end of the term. Just 10 weeks ago we were designing programs that multiplied a given number by 2. Now you have tackled this much more complex problem, which even if you could not completely solve you were able to understand it and have a sense of how to attack it systematically. Please take the time to feel good about that now.
Our solution is now available. We present it in two parts. First is the figure of the search tree. We actually drew it on a board, but we converted it to this form so it would be easier to read.
As you can see, we modeled the search state as consisting of the filled slots (pairs of slot name and ta name) and the unfilled slots (the slot names). At each step with made n new search states by filling the first slot with each ta that can still work that slot. The solved? test is simply whether the remaining slots to fill is empty. We only add valid states to the tree, so if solved? is ever true then that's a solution.
The solution for this problem set is:
