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 vn-1 as follows:
To extract the individual orientations again from t < vn-1, use the following code:
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 vn-1-1:
To extract the individual orientations again from t < vn-1-1, use the following code:
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:
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:
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:
To extract the even permutation again from a number t < n!/2 use this:
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:
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:
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.
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.