Write short notes on The 15 puzzle Problem.
15 puzzle problem • 7.3k  views

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

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more