If n pieces of a puzzle all have v possible orientations, then encode the orientation of each of these pieces as a number between 0 and v-1. Then n of such orientation values in an array or[1...n] can be encoded into a number between 0 and v^{n}-1 as follows:

t=0

for i = 1 to n

t = t * v

t = t + or[i]

endfor

return t

for i = 1 to n

t = t * v

t = t + or[i]

endfor

return t

To extract the individual orientations again from t < v^{n}-1, use the following code:

for i = n to 1

or[i] = t mod v

t = t / v

endfor

or[i] = t mod v

t = t / v

endfor

Usually there is the constraint that the total twist is 0 modulo v, in other words the orientation of the last piece is dependent on the other n-1. In this case just do not encode the orientation of the last piece, which gives a number between 0 and v^{n-1}-1:

t=0

for i = 1 to n-1

t = t * v

t = t + or[i]

endfor

return t

for i = 1 to n-1

t = t * v

t = t + or[i]

endfor

return t

To extract the individual orientations again from t < v^{n-1}-1, use the following code:

s=0

for i = n-1 to 1

or[i] = t mod v

s = s - or[i]

if s < 0 then s = s + v

t = t / v

endfor

or[n] = s

for i = n-1 to 1

or[i] = t mod v

s = s - or[i]

if s < 0 then s = s + v

t = t / v

endfor

or[n] = s

If n pieces of a puzzle can be permuted amongst themselves then their permutation can be encoded in a number between 0 and n!-1. Use a fixed numbering for both the pieces and the positions: the n piece positions are numbered from 1 to n, and the pieces are also from 1 to n (usually so that piece 1 belongs at position 1 when solved, piece 2 at position 2 and so on, but this is not strictly necessary). The permutation is stored in an array pm[1...n]. A permutation can now be encoded as a number between 0 and n!-1 as follows:

t = 0;

for i = 1 to n-1

t = t * (n-i+1)

for j = i+1 to n

if pm[i] > pm[j] then t = t + 1

endfor

endfor

return t

for i = 1 to n-1

t = t * (n-i+1)

for j = i+1 to n

if pm[i] > pm[j] then t = t + 1

endfor

endfor

return t

Note that if all pieces are in position then it is encoded as 0. To extract the permutation again from a number t < n! use this:

pm[n]=1

for i = n-1 to 1

pm[i] = 1 + (t mod (n-i+1))

t = t / (n-i+1)

for j = i+1 to n

if pm[j] >= pm[i] then pm[j] = pm[j] + 1

endfor

endfor

for i = n-1 to 1

pm[i] = 1 + (t mod (n-i+1))

t = t / (n-i+1)

for j = i+1 to n

if pm[j] >= pm[i] then pm[j] = pm[j] + 1

endfor

endfor

Often there is the constraint that the permutation must have even parity. This means that the position of the last two pieces is dependent on the other n-2. In this case just do not encode the position of the last two pieces, which gives a number between 0 and n!/2 - 1:

t = 0;

for i = 1 to n-2

t = t * (n-i+1)

for j = i+1 to n

if pm[i] > pm[j] then t = t + 1

endfor

endfor

return t

for i = 1 to n-2

t = t * (n-i+1)

for j = i+1 to n

if pm[i] > pm[j] then t = t + 1

endfor

endfor

return t

To extract the even permutation again from a number t < n!/2 use this:

pm[n] = 2

pm[n-1] = 1

s = 0

for i = n-2 to 1

pm[i] = 1 + (t mod (n-i+1))

s = s + pm[i]-1

t = t / (n-i+1)

for j = i+1 to n

if pm[j] >= pm[i] then pm[j] = pm[j] + 1

endfor

endfor

if s mod 2 = 1 then swap pm[n] , pm[n-1]

pm[n-1] = 1

s = 0

for i = n-2 to 1

pm[i] = 1 + (t mod (n-i+1))

s = s + pm[i]-1

t = t / (n-i+1)

for j = i+1 to n

if pm[j] >= pm[i] then pm[j] = pm[j] + 1

endfor

endfor

if s mod 2 = 1 then swap pm[n] , pm[n-1]

If m pieces identical pieces of a puzzle can be in any of n positions, then there are n!/m!(n-m)! ways to do this. Use a fixed numbering for the positions, from 1 to n. The combination is stored in an array cm[1...n], where an array element is p if one of the pieces is there and some other value otherwise. A combination can now be encoded as a number between 0 and n! / ( m!(n-m)! ) -1 as follows:

t = 0

r = m

for i = n-1 to 0

if cm[i+1] = p then

t = t + comb(i,r)

r = r - 1

endif

next

return t

r = m

for i = n-1 to 0

if cm[i+1] = p then

t = t + comb(i,r)

r = r - 1

endif

next

return t

Here comb(i,r) equals i!/ ( r!*(i-r)! ). For speed, it is best to have a pre-calculated n by n table with the values for the various i and r. To extract the permutation again from a number t < n!/m!(n-m)! use this:

r = m

for i = n-1 to 0

if t >= comb(i,r) then

t = t - comb(i,r)

cm[i+1] = p

r = r - 1

endif

endfor

for i = n-1 to 0

if t >= comb(i,r) then

t = t - comb(i,r)

cm[i+1] = p

r = r - 1

endif

endfor

The pseudo-code below calculates God's algorithm for a puzzle, i.e. a table with the distances from start for all positions. It is assumed that a position can be converted to an index between 1 and N using the function pos2idx, and vice versa using the function idx2pos.

Fill table completely with -1.

table[ pos2idx(startposition) ] = 0

len = 0

loopbegin

c = 0

for p = 1 to N

if table[p] = len then

for each available move m

q = pos2idx( m applied to idx2pos(p) )

if table[q]=-1 then

c=c+1

table[q] = len+1

endif

endfor

endif

endfor

len = len + 1

print c "positions at distance" len

loop while c>0

table[ pos2idx(startposition) ] = 0

len = 0

loopbegin

c = 0

for p = 1 to N

if table[p] = len then

for each available move m

q = pos2idx( m applied to idx2pos(p) )

if table[q]=-1 then

c=c+1

table[q] = len+1

endif

endfor

endif

endfor

len = len + 1

print c "positions at distance" len

loop while c>0

Clearly it is faster if the expression *pos2idx(m applied to idx2pos(p))* is calculated beforehand for all p and m, i.e. if a transition table is used. If a transition table would be too much trouble to implement, or too large and p cannot be split into several indices each with its own small transition table, then it is certainly best to calculate idx2pos(p) outside the innermost *for* loop.

Note that the same method is used for calculating pruning tables. For God's algorithm we have a one on one relation between the positions and the numbers 1 to N, but for pruning tables this is no longer the case. Each number represents many puzzle positions, and pos2idx() converts all these to that number, and idx2pos generates any one of those positions which is used to represent them all. Thus we still have p = pos2idx(idx2pos(p)) for any number 1<=p<=N.