Question: Write short notes on The 15 puzzle Problem.

Subject: Analysis Of Algorithm

Topic: Backtracking

Difficulty: High

aoa(14) • 4.1k views
modified 21 months ago by gravatar for awari.swati831 awari.swati831250 written 3.3 years ago by gravatar for satishmanje93 satishmanje9320

The 15 puzzle problem is invented by sam loyd in 1878.

  • In this problem there are 15 tiles, which are numbered from 0 – 15.
  • The objective of this problem is to transform the arrangement of tiles from initial arrangement to a goal arrangement.
  • The initial and goal arrangement is shown by following figure.

enter image description here

  • There is always an empty slot in the initial arrangement.
  • The legal moves are the moves in which the tiles adjacent to ES are moved to either left, right, up or down.
  • Each move creates a new arrangement in a tile.
  • These arrangements are called as states of the puzzle.
  • The initial arrangement is called as initial state and goal arrangement is called as goal state.
  • The state space tree for 15 puzzle is very large because there can be 16! Different arrangements.
  • A partial state space tree can be shown in figure.
  • In state space tree, the nodes are numbered as per the level.
  • Each next move is generated based on empty slot positions.
  • Edges are label according to the direction in which the empty space moves.
  • The root node becomes the E – node.
  • The child node 2, 3, 4 and 5 of this E – node get generated.
  • Out of which node 4 becomes an E – node. For this node the live nodes 10, 11, 12 gets generated.
  • Then the node 10 becomes the E – node for which the child nodes 22 and 23 gets generated.
  • Finally we get a goal state at node 23.
  • We can decide which node to become an E – node based on estimation formula.

Estimation formula:

C (x) = f (x) + G (x)

Where, f (x) is length of path from root to node x.

G (x) is number of non-blank tiles which are not in their goal position for node x.

C (x) denotes the lower bound cost of node x.

State Space Tree:

enter image description here

written 3.3 years ago by gravatar for satishmanje93 satishmanje9320
Please log in to add an answer.