PKU 2046 Gap

This is a question from Japan Regional Contest 2003

Given 4x8 grid map, which is filled with 28 distinct numbers on the right 4x7 grids, ranging from 11-17, 21-27, 31-37 and 41-47. The left 4x1 grids are left as spaces. Then swap the spaces with 11, 21, 31 and 41 such that the left 4x1 grids are from top 11, 21, 31 and to bottom 41, respectively. The game then starts. Each time the spaces can swap with the next numbers from its left, e.g. 47 can be swapped with a space whose left grid contains 46. Note that under this rule, any space cannot perform swapping if its left is either 17, 27, 37 and 47. The game ends when the map is as follow:

The question asks the minimum step to achieve the goal, given the initial state.

Clearly, the sample input gives the worst case of 60 steps, so you can think that the possible and reachable states should be much less than . Applying BFS should be plausible. Since the state representation in integer is difficult, one may choose the hash the state with slight conflict. Then store the state using hash table. Under sufficiently good hashing function and small hash size, the program can pass the time limit. Note that, since the steps and grid map stores small integer, using short when declaring the structure is always preferred.

The hash function I choose is

Hash table size is 66271