Puzzle 2 involves a 3x3 pendent of jewels which can be changed to different jewels with a magic spell. Given a starting pendent, the goal is to find the shortest sequence of spells that will turn the pendent into one containing 9 of the same jewel. BEAUTIFUL! A straightforward search problem where at each node in the search you have 9 possible next moves (9 possible spell locations). The challenge is picking which of the 5 search strategies we might use. We will talk about this in class, but I think there are two which make the most sense.
For this homework you should write a Java program (other language POSSIBLE upon pre-approval) that fits the following requirements
Your code must provide an easy way for me to indicate the "starting state" of the puzzle. You have three choices for this. You may design your code to ask the user for some input at startup time, you may require it as command line input at runtime, or you can provide a data structure at the top of your main class.
public class JewelGame {
public static void main(String[] args) {
byte[] start = {0,0,1, 0,0,0, 0,0,0 }
....
}
}
You must devise a solution which uses the concept of a search tree. That is, you need to develop a data structure which knows its state, its parent, its depth, etc... You also need to maintain the queue of unexpanded nodes remaining.
You must use one of the five uninformed search techniques we studied in session 8 or session 9 to find an optimal solution.
When a solution is found you need to print out the sequence of moves that will get you from the initial state to the goal state.
Your code must also print the number of nodes expanded so far (gives us an idea of time) and the number of nodes still stored in memory (gives us an idea of memory usage).
For a few bonus points, you may implement more than one search strategy (again, I think that only two of these REALLY make sense).
and here is a link to how it should look like http://www.math.uni.edu/~shaw/doctore/Wrong2/
thank you so much