Finding the number of permutation inversions

Question

I was looking at this because I'm trying to make a fifteen puzzle solver. I don't really understand what it's talking about. How would I go about checking if a given set of numbers (from 0-15, stored in an array, 0 being the blank) is valid given that "if the permutation symbol of the list is +1 the position is possible". I'm working in javascript, if its relevant.

Answer 1

Consider the following: If you took a solved 15-puzzle, and with a pair of plyers physically removed and swapped and replaced the 14 and 15 blocks, and scrambled it... could you return it to a valid state?

The answer is no. There is an invariant that is preserved by all moves you can do in a 15-puzzle, and the permutation symbol is probably referring to that invariant.

According to http://en.wikipedia.org/wiki/Fifteen_puzzle :

The invariant is the parity of the permutation of all 16 squares (15 pieces plus empty square) plus the parity of the taxicab distance moved by the empty square.

This is an invariant because each move changes both the parity of the permutation and the parity of the taxicab distance. In particular if the empty square is not moved the permutation of the remaining pieces must be even.

To calculate this parity, check out http://en.wikipedia.org/wiki/Parity_of_a_permutation (you could also check out Levi-Civita Symbol, but it's a bit arcane), implement it in python, then calculate the manhattan distance the empty square has moved from its starting position, and take the parity of the sum of both those values.

Something like:

#!/usr/bin/python3

from pprint import pprint

state_starting = list(range(1,16)) + [None]
START = state_starting

def positionIsPossible(state):
    """
        state is a list, the starting position is [1,2,3,...,15,None]
    """
    numInversions = sum(
        state.index(START[j]) > state.index(START[i])
        for i in range(16) for j in range(i)  # each pair (i,j)
    )  #sum([True,True,False])==2

    # Uncomment if you want to see what's going on here:
    #pprint(list(
    #    ((i,j), (START[i],START[j]), state.index(START[j]) > state.index(START[i]))
    #    for i in range(15) for j in range(i)
    #))

    newEmptySquareYPos = state.index(None)//4
    newEmptySquareXPos = state.index(None)%4
    emptySquareMovedDistance = abs(3-newEmptySquareYPos)+abs(3-newEmptySquareXPos)

    parity = (numInversions + emptySquareMovedDistance)%2

    print('number of inversions:', numInversions)
    print('distance empty square moved:', emptySquareMovedDistance)
    print('parity:', parity)

    return parity==0

Here are some examples / test cases:

def swap(state, i, j):
    state = list(state)
    state[i], state[j] = (state[j], state[i])
    return state

def validate(state):
    def formatState(state):
        return '\n'.join('|'+' '.join([str(y if y else '').rjust(2) for y in x])+'|' for x in [state[0:4],state[4:8],state[8:12],state[12:16]])
    print(formatState(state))
    print(state, 'is', 'reachable' if positionIsPossible(state) else 'unreachable')
    print()

# reachable
validate(state_starting)
validate(swap(state_starting, 15,14))
validate(swap(state_starting, 15,11))

# unreachable
validate(swap(state_starting, 14,13))

Results:

| 1  2  3  4|                                                                                                                                                                                                                                                       
| 5  6  7  8|
| 9 10 11 12|
|13 14 15   |
number of inversions: 0
distance empty square moved: 0
parity: 0
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, None] is reachable

| 1  2  3  4|
| 5  6  7  8|
| 9 10 11 12|
|13 14    15|
number of inversions: 1
distance empty square moved: 1
parity: 0
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, None, 15] is reachable

| 1  2  3  4|
| 5  6  7  8|
| 9 10 11   |
|13 14 15 12|
number of inversions: 7
distance empty square moved: 1
parity: 0
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, None, 13, 14, 15, 12] is reachable

| 1  2  3  4|
| 5  6  7  8|
| 9 10 11 12|
|13 15 14   |
number of inversions: 1
distance empty square moved: 0
parity: 1
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, None] is unreachable

If your algorithm doesn't really care about whether the position is possible or not (you're just doing this to say "invalid input! position not possible!" you could ignore this part, run it anyway for a few hundred iterations, and return "impossible!" if unsolved.

Answer 2

Because of the "cycles" required to move pieces on one of these puzzles, piece swaps cannot be made in isolation. Consider the board:

You must swap (11) an (12) to solve it. But how can you? Simply "cycling" (11, 12, 15, -) in either direction will never change the order. Therefore we must involve more pieces, but in doing so, we cannot preserve the order of those other pieces. Anything we try will result in the order of another pair being swapped. For example, we might correct (11) and (12) by involving the (7) and (8), but in doing so, swap the (8) and (-):

Therefore, the number of swaps required to solve the puzzle must be even, or we are left with an "odd man out" as in the board above.

Therefore again, if you detect in your solver a situation in which a single swap will solve the puzzle, you know that this board cannot be solved.