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

Question

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

Answer 1

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.

Answer 2

There are 16! = 2.09*10^13 possible states which needs about 44.25 bits to be encoded.

So if you want to encode the state in bytes, you need at least 6 bytes to do it.

Why not encode it this way:
Let us name the values a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p

The value can be

b`:= b - (b>a)?1:0;
c`:= c - (c>a)?1:0 - (c>b)?1:0
d`:= d - (d>a)?1:0 - (d>b)?1:0 - (d>c)?1:0
....

hashNumber= a+b*15+c*15*14+d`*15*14*15+....

This will give you a bijective mapping of each possible sate to a number fitting in 6 bytes.

Also converting the number back to its referring state is quite easy, if you need to do it.

---

Not optimal but fast is:
Use 4 bits for each number (leave out the last one because it can be computed from the previous 15 numbers) that needs 15*4 bits = 60 bits. can be stored in 7.5 bytes or if you are ok to waste more, simply use 8 bytes.