I am developing a heuristic solution for the blocks world problem.

I tried using the number of blocks out of place as my $h(n)$. It seems a little ineffective.

Can someone please point out a suitable heuristic for the problem and explain with a few examples how it will work.

Blocks world problem example:

Initial(starting State):
Stack 0: D,B
Stack 1: A,E
Stack 2: C
Stack 3: F

Goal State:
Stack 0: A,B,C,D,E,F

1 Answer 1


You may start assigning penalties for undesirable conditions in a state like:

1) Number of blocks outside stack 0.

Supose you penalize with 10 units each block outside stack 0, then the starting state above adds 40 units to the penalty score

2) Number of blocks in the stack 0 in a position different than in the goal state.

Supose you penalize with 50 units each block in stack 0 in the wrong position of the stack 0, then the starting state adds 50 to the penalty score (block D).

And go on you may add as many penalties as you find helpful for solving the problem.

Then for each step you list all possible block moves, for each one of this moves you calculates the total penalty score that this move produces and choose the one move with the minimal score (if ties choose the first one). You keep repeating above until you reach the final state (penalty 0).


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .