SLIDER PUZZLE

Search Algorithms

In this assignment you will implement algorithm for solving the slider puzzle that has tiles marked 1 to 20 placed in random order on a sliding board. The tiles can be moved around the circular track but cannot be removed from the track. There is a knob attached to the track that when used can reverse the order four of the consecutive numbers being rotated using the knob. The objective of the puzzle to rotate the knob the numbers come in ascending order. The challenge is to solve the puzzle with least number of rotations. Rotation of knob takes one unit of time and sliding the tiles to the desired position before rotation takes no time You can slide the tiles to the left or right any number of spaces at no cost. We will display the board from the position of the knob. Every rotation will be shown as a rotation from position 1.

For example the track in the picture above has

17 18 19 15 16 20 1 2 3 5 7 10 11 8 9 6 4 12 13 14

then rotating the knob at 1st position would result in

15 19 18 17 16 20 1 2 3 5 7 10 11 8 9 6 4 12 13 14

Now sliding the tiles four positions to the right results in

4 12 13 14 15 19 18 17 16 20 1 2 3 5 7 10 11 8 9 6

then rotating the knob at 1st position would result in

14 13 12 4 15 19 18 17 16 20 1 2 3 5 7 10 11 8 9 6

You will write three algorithms

1. Uniform cost search (heuristic =0) (this gives the optimal path to the goal, even though time and space are very high) With this algorithm get the same results for NUM_EXPANDED, FRINGE_MAX and PATH_COST

2. A* algorithm with the given heuristic, namely, number of tiles out of order. With this heuristic everyone must get the same results for NUM_EXPANDED, FRINGE_MAX and PATH_COST. If this heuristic is admissible you will find optimal path will less number of nodes expanded and less number in maximum length of fringe.

3. A* algorithm with your own heuristic to solve the problem above. The performance of this heuristic is entirely up to the heuristic. . If this heuristic is admissible you will find optimal path will lesser number of nodes expanded and lesser number in maximum length of fringe than the two previous algorithms.

IS 20 17 IS 20 17