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

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.

• 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:

0