# Heuristics for an Artificial Intelligence problem

Problem : Given a (one dimensional) row containing $2N$ tiles arranged in $2N + 1$ spaces. There are $N$ black tiles (B), $N$ white tiles (W), and a single empty space. The tiles are initially in an arbitrary ordering. Our goal is to arrange the tiles such that all white tiles are positioned to the left of the black ones, and one black tile is in the rightmost position. The goal position of the empty space is not specified.
Tiles can be moved to the empty space when the empty space is at most $N$ cells away. Hence there are at most $2N$ legal moves from each state. The cost of each move is the distance between the tile and the empty space to which it moves ($1$ to $N$).

So I am doing this problem with A* search algorithm with different heuristics(ofcourse admissible).So can anybody suggest me some heuristics.
Thanks

• I am afraid that the sum of the terms of the arithmetic progression from $0$ to $(N-1)$ equals $\frac{N(N-1)}{2}$ instead of $\frac{N(N+1)}{2}-1$ – Carlos Linares López Aug 21 '12 at 0:05