Homework 1

Implementing Search to solve a "Challenge"

Due: Monday, September 17th, 10:00 AM


[Note: This problem was inspired by Dr. Shaw in the mathematics department.]

Adulthood has been much more laid back for Harry Potter.  Now that he has defeated Voldemort and settled into raising his family he has accepted a fairly banal job - that of a jewelry smith.  His specialty is creating customized pendants consisting of a 3x3 arrangement of jewels.  Each of the 9 jewels is either a diamond, a ruby, or an emerald.  These jewels can be changed by casting a spell at a particular jewel.  This spell will change a diamond into a ruby, a ruby into an emerald, or an emerald into a diamond. Unfortunately, you may recall that Harry, while being "the chosen one" wasn't necessarily the greatest spell caster - in particular with simple spells.  So unfortunately for Harry, any time he casts a spell at a particular jewel he not only modifies that jewel, but he also modifies the jewels touching that jewel orthogonally (that's a fancy word meaning both horizontally and vertically! )

Thus, if Harry started with the pendent described by the string "EDRDREDDE"  or :

and cast a spell at the center ruby (jewel #5),


he would end up with the pendent described by the string "ERRREDDRE" or :


The "goal" of this puzzle is, given a starting pendent, find the shortest sequence of spells that will turn the pendent into one containing 9 of the same jewel. 

If you want to try this out you can play this game at:  http://scratch.mit.edu/projects/26515800/


BEAUTIFUL!  A straightforward search problem where at each node in the search you have 9 possible next moves - a single spell at each of the 9 jewels/possible spell locations:


A search problem for this game would attempt to find a goal state (9 matching jewels of any type) in as few moves as possible.





For this homework you should write a program that fits the following requirements:


Hints from past experience with this assignment...

Be careful when you "copy" your data structures. This is true in both python and java.

Remember what happens when you "copy" a referential data type in Java... you only get a copy of the reference, not a copy of the object.  This means that if you have a node that you want to copy several times and modify to create the children nodes, you need to be careful what you do to copy the node.  Students have a habit of saying something like:

    //Assume that Node parent was created elsewhere
    Node child1 = parent;
    Node child2 = parent;
    Node child3 = parent;

This just gives you FOUR variables all of which point to the same single instant.  Students end up forgetting this and then being surprised when child1, child2, and child3 are identical and TOTALLY screwed up (in essence, they just cast 3 different spells on the same single object.

You will need to write code which produces a true, second copy of whatever data structure you use in your tree.

Similar "copy by value" vs. "copy by reference" problems exist in Python.  Make sure you pay attention to this issue.




2)  When it gets to be time to test your code, start with simple problems.  For example,


can EASILY be turned into a pendent of all diamonds by casting the spell on the center emerald.  Shortest solution is ONE move.  If your code can't solve this, than you have a significant problem.  Similarly, your code should detect that


is already a solution and requires no moves at all.


Submitting Your Work

Prior to the deadline, use the homework submission system


to upload any files you have produced. 

In addition to online copies, please submit hard copies of this lab at the start of class on the day this lab is due.