In this programming part you are asked to implement a game called MagicBoard.
MagicBoard is a 1-player game using a chess-like board consisting of d x d squares with d between 5 and 20, and each square contains an integer between 0 and d - 1. The rules of the game are simple. The circle marks the start position on the board. The integer (n) in the circled square indicates that the circle can move n squares on the board. In one step the circle can move either n squares east or west or noth or south. At each step the chosen direction is fixed. The circle cannot move off the board. The only legal start positions are the four corner squares. The board must contain exactly one goal square with zero as value that can be located anywhere on the board, but its position cannot be identical to the start position.
| 4 | 2 | 1 | 3 | 1 |
| 2 | 3 | 2 | 1 | 4 |
| 3 | 2 | 3 | 1 | 4 |
| 1 | 3 | 4 | 2 | 3 |
| 3 | 3 | 1 | 2 | 0 |
For instance, in the above example the circle can move either 4 squares east or south. All other moves are illegal. The objective of the game is to move the circle to the goal square containing the zero value. In the configuration given below, you can solve the game by making the following sequence of steps:
1. Step Move south
| 4 | 2 | 1 | 3 | 1 |
| 2 | 3 | 2 | 1 | 4 |
| 3 | 2 | 3 | 1 | 4 |
| 1 | 3 | 4 | 2 | 3 |
| 3 | 3 | 1 | 2 | 0 |
2. Step Move east
| 4 | 2 | 1 | 3 | 1 |
| 2 | 3 | 2 | 1 | 4 |
| 3 | 2 | 3 | 1 | 4 |
| 1 | 3 | 4 | 2 | 3 |
| 3 | 3 | 1 | 2 | 0 |
3. Step Move west
| 4 | 2 | 1 | 3 | 1 |
| 2 | 3 | 2 | 1 | 4 |
| 3 | 2 | 3 | 1 | 4 |
| 1 | 3 | 4 | 2 | 3 |
| 3 | 3 | 1 | 2 | 0 |
4. Step Move east
| 4 | 2 | 1 | 3 | 1 |
| 2 | 3 | 2 | 1 | 4 |
| 3 | 2 | 3 | 1 | 4 |
| 1 | 3 | 4 | 2 | 3 |
| 3 | 3 | 1 | 2 | 0 |
Although the given example is solvable, actually with more than one solution, some board configurations may be unsolvable, i.e., the goal square cannot be reached from the given start position. Below is a saimple example.
| 1 | 4 | 1 | 3 | 1 |
| 4 | 3 | 2 | 1 | 4 |
| 3 | 2 | 3 | 1 | 4 |
| 1 | 3 | 4 | 2 | 3 |
| 3 | 4 | 1 | 2 | 0 |
In this configuration, the circle can only move to its two adjacent squares with value 4. If it moves to its eastern neighbor, it will bounce south-north between two 4's, and if it moves to its southern neighbor it will bounce east-west between two 4's.
1. In this programming assignment, you will develop two verions of the MagicBoard game. For both versions you have to design an algorithm in pseudo code and develop a corresponding Java implementation.
2. Your solution takes a legal start position of the circle along with a d x d array of square values. Your solution should return true if it is possible to solve the game from the start position and false if it is impossible. Your solution should work for any d x d board with d between 5 and 20, and all squares should contain a random integer value between 1 and d-1 with the exception of the goal square that contains the only zero value. You are not allowed to modify the values on the board at any time.
a) Briefly explain the time and memory complexity for both versions of your game. You can write your answer in a separate file and submit it together with other programming submissions.
b) For the first version of your solution describe the type of recursion used in your implementation. Does the particular type of recursion have an impact on the time and memory complexity? Justify your answer. Also explain whether tail-recursive version is possible. If yes, you can earn bonus marks by submitting such a version.
c) For the second part of your solution, justify why you choose that particular data structure (e.g. why you choose a stack and not a queue, etc.). Explain whether your chosen data structures have an impact on the time and memory complexity.
d) For each version provide test logs for at least 20 different game configurations. They must be sufficiently complete to show that your solution works for various board dimensions and square values.
e) Explain how one can detect unsolvable board configurations and whether there exists a way to speed up the execution time.
For each version you are required to submit your pseudo code, the corresponding fully commented Java source files, the compiled files (.class files), the log and text files.