1     2    3

H (n)

A small example:

5

4      8

8 puzzle game

Current state

7      6    5

H function:

the numbers of

the misplaced tiles

1     2

1     2     3

6

includes blank).

4     8    3

4     8     5

We choose the state

7     6

7     6    5

with smallest H value

as the next state

Choose as next state