The ring-shaped sliding tile puzzle consists of N red tiles (R), N green tiles (

Question

The ring-shaped sliding tile puzzle consists of N red tiles (R), N green tiles (G), and two blank spaces (*). N > 1. They are placed on a ring with 2N+2 slots. The slots are numbered as in Figure 1. In the initial configuration, the tiles can be in any position, and an example for N=3 is shown in Figure 2. The goal state is any configuration where no two red and green tiles are next to each other. In other words, the state contains no consecutive pairs of red tiles or consecutive pairs of green tiles. See examples in Figure 3, and 4. Obviously rotating a goal state results in another goal state.

The puzzle has two kinds of legal moves with respective associated costs: 1. A tile may move into either of the blanks (*) provided that it is adjacent to the blank on the ring. This makes the tile’s original location a blank. The cost of this move is 1. 2. A tile can jump over one other slot into either of the blanks (*), incurring a cost of 2. This also makes the tile’s original location a blank. Note a tile can jump over a blank to get into another blank.

1. Fix N=3. Pick one uninformed search algorithm among the following: breadth-first (graphsearch version), uniform-cost (graph-search version), depth-first (tree-search), iterative-deepening. Randomly generate three initial states and run both A* algorithm (graph-search version) and your picked algorithm on the three problems. In principle, you should use seeds 1, 2, 3, ... and skip a value if and only if it results in a state that is 0~2 steps away from a goal state.

(a) In your PDF report, show all the following results (3*2=6 sets of results), and comment on them. i. the number of nodes expanded; ii. the cost of the solution.

(b) Compare the results of A* and your picked algorithm. Also mention the value of the three seeds used to invoke the random initializer in Question 2, so that the TA can reproduce your results. (c) For each of the 6 sets of test, dump to a plain text file the sequence of actions that lead to the returned solution. The filenames should be Astar_1.dat, X_1.dat, Astar_2.dat, X_2.dat, Astar_3.dat, X_3.dat, where X {breadth, uniform, depth, iterative}, depending on the algorithm you pick. The file content should employ the following format, exemplified with the initial state given by Figure 2:

R * G G R R * G

2 1 1

4 6 2

….

The first line encodes the initial configuration: the slots #0, #1, #2, #3, … have (respectively) a red tile, a blank, a green tile, a green tile, etc. From line 2, each line

x y z

means moving a tile from slot x to slot y, with the cost z. Slot y must be a blank before the move. In the above snippet based on Figure 2, it first moves the green tile from slot #2 to slot #1 with cost 1, then moves a red tile from slot #4 to slot #6 with cost 2 (jumping over a red tile in slot #5). There is a single space between all characters and numbers.

Explanation / Answer

public class Puzzle { public static void main(String[] args) { int [][] board = new int [4][4]; board [1][1] = 1; board [2][1] = 2; board [3][1] = 3; board [4][1] = 4; board [1][2] = 5; board [2][2] = 6; board [3][2] = 7; board [4][2] = 8; board [1][3] = 9; board [2][3] = 10; board [3][3] = 11; board [4][3] = 12; board [1][4] = 13; board [2][4] = 14; board [3][4] = 15; board [4][4] = -1; // -1 is just a temporary placeholder for the blank space. String lineSeparator = "+---+---+---+---+"; String row1 = "| " + board[1][1] + " | " + board[2][1] + " | " + board[3][1] + " | " + board[4][1] + " |"; String row2 = "| " + board[1][3] + " | " + board[2][2] + " | " + board[3][2] + " | " + board[4][2] + " |"; String row3 = "| " + board[1][3] + " | " + board[2][3] + " | " + board[3][3] + " | " + board[4][3] + " |"; String row4 = "| " + board[1][4] + " | " + board[2][4] + " | " + board[3][4] + " | " + board[4][4] + " |"; System.out.println(lineSeparator); System.out.println(row1); System.out.println(lineSeparator); System.out.println(row2); System.out.println(lineSeparator); System.out.println(row3); System.out.println(lineSeparator); System.out.println(row4); System.out.println(lineSeparator); } }

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.