Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm trying to calculate the distance-table (#of states as a function of the distance) of the 15-puzzle (has been done before in 2005 on a supercomputer by Korf et al.). There are $16!$ different states, or nodes, in the tree that needs to be searched. In order to prevent the searcher from reaching the same state twice, a checklist must be kept where each state is checked as soon as it has been visited. I should be able to use just 1 bit per state, which would amount to $\frac{16!}{8\text{bits}} = 2.4\text{TB}$ of data. I don't think I need to add that this is huge...

Luckily, a parity argument can be used to see that only half of the states can actually be reached using legal moves. This is all very nice, and would reduce the required size to $1.2\text{TB}$, but only if I am able to map the states onto $[0,\frac{16!}{2}-1]$, in order to address the correct bit to manipulate.

Each state can be written down as a permutation $\vec{p}$, and therefore mapped to $[0, N!-1]$ using the following mapping: $$ X(\vec{p}) = \sum_{i=1}^{N-1}L_i(\vec{p})(N-i)!$$ where $$ L_i(\vec{p}) = \sum_{j=i+1}^Nl_{ij}, \qquad l_{ij} = \left\{\begin{matrix}0,\quad p_i\ge p_j \\ 1,\quad p_i < p_j\end{matrix}\right.$$ simply counts the number of elements beyond $p_i$ that are less than $p_i$. One can convince himself that $X \in [0, N!-1]$ using the two limit-cases for $\vec{p}$: $$ \vec{p}_\text{min} = \{0, 1, 2, ..., N-1\} \rightarrow X(\vec{p}_\text{min})=0$$ $$ \vec{p}_\text{max} = \{N-1, N-2, ..., 0\} \rightarrow X(\vec{p}_\text{max})=N!-1$$

However, only half the memory will actually be used when this mapping is used, because of a parity constraint. Therefore I'd like to be able to use this constraint to reduce the mapping to the interval $[0, \frac{N!}{2}-1]$. The thing is, I have no clue how...

Puzzles often have a parity-property such that the final two elements of a permutation are determined by the other $N-2$. This is not the case however in the 15-puzzle. The following constraint is true for every permutation of the 15-puzzle: $$P(\vec{p}) + (i_\text{void} + j_\text{void}) = 0 \mod{2}$$ where $P(\vec{p})$ denotes the parity of the permutation, and $i_\text{void}$ and $j_\text{void}$ denote the row- and column-index of the void (which is the 0-entry in $\vec{p}$).

I know this is a longshot, but how can I use this property to cleverly map each state onto a unique index in the appropriate range? I even have a follow-up question in case anyone can help me with this one...

share|improve this question

1 Answer 1

If you are actually storing the distance, won't you need more than just one bit per state? Also, the parity can be expressed so that it is only affeected by the last two items: The void position has $16$ possibilities and then the order of the numbered pieces is one of $15!$ permutations, with the order of the last two pieces determined by parity.

share|improve this answer
    
You're right, I haven't been clear enough. I want the number of states as a function of distance. I'll edit it out in a minute. Also, the order of the last two pieces is determined by the parity as stated in the question, not the mere permutation parity. If this was the case, the index would be trivial (iterate until $N-2$ instead of $N-1$ in the definition of $X$). –  JorenHeit Feb 3 at 13:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.