For this project, you need to implement one graph algorithm to solve a puzzle. For this puzzle game, the GUI (graphical user interface) framework is provided that is developed by JavaFX. Below is a highlight of the structure.
1. Main - This class deals with the GUI and interactivity, including user mouse/keyboard interface, etc. (You do not need to modify this class).
2. RandomGenerator - This class is also defined inside the "Main.java". This class is used to generate a random sequence of numbers (from 0-8). Each number represents one piece of image. So if the number are in sequential order, you will see the pattern of the original image. (You do not need to modify this class).
3. Solution - This is the class that provides a solution for a given puzzle. There is only one static function member inside it "breadthFirstSearch()" which requires you to implement.
1. Download the "framework.zip" and unzip it. You will see two folders application and image underneath the framework folder.
2. Create a JavaFX project, then copy all the files from the "framework/application/.." to your newly created JavaFX corresponding application folder by replacing the default Main.cpp.
3. Use the Eclipse to create another package called "image" that is in the same level as application package underneath Src: see image.
4. As step 2, copy all the image files from "framework/image/.." folder to the project image package.
5. Run the project:
a. Now you can run the project and see a GUI window pop up as below: see image.
b. The left image shows the "puzzle" you need to solve; the right image shows the goal or sequentially ordered image pieces. There are three buttons: the open button allows you to load different images. You can also load your own image. But make sure it is close to square shape. Otherwise, only part of the image will be loaded. The reset button allow you to regenerate different random orders of the input puzzle, which trigger the functions defined in the RandomGenerator class.
c. The "solution" button is the only thing you will implement, which will trigger the breadthFirstSearch() function. The details are explained in the following section.
d. In the "image" package, you can use the image5.jpg to facilitate your debug process. see image.
You only need to implement one functions in the "Solution.cpp" file:
public static void breadthFirstSearch(int[] num, int m, Vector solution)
{
}
The input parameters are as blow:
int[] num - the input array represents the combination of numbers (0, 1, , 8) that is not in sequential order, e.g. "3", 0, 1, 6, 4, 5, 7, 8, 2. Your job is starting from this order and make it in sequential order by swapping between numbers for several times.
int m - the number represents the empty space or missing piece on the image. Taking the above example, if m = 6, then "6" represents the missing piece. When you do the swapping, you can only let the direct neighbors of 6 to swap with them. For example, 6 is swapped with 4; or 6 is swapped with 3; or 6 is swapped with 7: see image.
As such, the above three possible swapping will produce three possible new sequences or subsequent patterns by updating the array int[] num
Vector solution - it represents the "path" how the input sequence (int[] num) will go through by swapping numbers multiple times to finally become a sequential order. In fact, this third parameter is the output of the function instead of an input. Initially, this parameter is passed to the function as an empty vector. Now the question is what is the path. Here is an example:
Num[] = {0, 4, 1, 3, 8, 2, 6, 7, 5 };
Let's this time make "8" as the missing piece (m = 8). Then below shows how you will do the swapping to achieve the goal of sequential order: see image.
So from this example, the right path should be {1, 2, 5, 8}.
"Why? Should it be {4, 1, 2, 5}, since the number 8 has swapped with them in this order?"
That is true. However, we do not care which number it swapped with, but which position the number 8has gone through. As the numbers can be in any positions during different time, which give no hint about where the number 8 is. In contrast, the positions are fixed. So we assume the positions are in the same order as an increasing sequence: see image.
Here "[]" is used to distinguish the positions from the numbers. So now you can see, the number 8 starts from position [4], then swaps with number 4, which goes to the position [1]; then swaps with number 1, which goes to the position [2]; then swaps with number 2, which goes to the position [5]; finally, swaps with number 5, which goes to the position [8]. So the path you should assign to the parameter "&solution" with the path sequence {1, 2, 5, 8} (ignore the starting position [4]).
So as long as this "breadthFirstSearch()" function finally output the right vector (the third parameter) successfully, it means you accomplish this project. You will see the process of automatic piece moving after the solution button is clicked.