Ideas for an efficient way of hashing a 15-puzzle state

I am implementing a 15-puzzle solver by Ant Colony Optimization, and I am thinking a way of efficiently hashing each state into a number, so I waste the least amount of bytes.

A state is represented by a list of 16 numbers, from 0 to 15 (0 is the hole).

Like:

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]

So I want to create an unique number to identify that state. I could convert all the digits to a base 16 number, but I don't think that's very efficient Any ideas?.

Thanks

Solution

Your state is isomorphic to the permutations of 16 elements. A 45 bit number is enough to enumerate those (log2 16!), but we might as well round up to 64 bit if it's beneficial. The problem reduces to finding an efficient conversion from the state to its position in the enumeration of states.

Knowing that each number in 0..16 occurs only once, we could create 16 variables of log2 16 = 4 bits each, where the i^th variable denotes which position the number i occurs. This has quite a bit of redundancy: It takes log2(16) * 16 bits, but that's exactly 64 bit. It can be implemented pretty efficiently (untested pseudocode):

state2number(state):
  idx = 0
  for i in [0;16):
    val = state[i]
    idx |= i << (val * 4)
  return idx

I don't know if this is what you meant by "convert all the digits to a base 16 number". It is insanely efficient, when unrolled and otherwise micro-optimized it's only a few dozen cycles. It takes two bytes more than necessary, but 64 bit is still pretty space efficient and directly using it as index into some array isn't feasible for 64 nor for 45 bit.