Finding the number of permutations inversions

Question

I watched this one because I'm trying to make fifteen puzzle. I do not quite understand what this is talking about. How could I check if a given set of numbers is really (from 0-15 stored in an array, 0 is empty), given that "if the permutation character in the list is +1, then the position is possible." I work in javascript if necessary.

Answer 1

Consider the following: if you decide to solve the 15 puzzle and, using a pair of physiotherapists, remove and swap and replace the blocks 14and 15, and scramble it ... can you return it to its actual state?

The answer is no. There is an invariant that is preserved by all the moves you can make in the 15 puzzle, and the permutation symbol probably refers to this invariant.

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

An invariant is the parity of the permutation of all 16 squares (15 pieces plus an empty square), as well as the parity of the distance of a taxi moved by an empty square.

, , . , , .

, http://en.wikipedia.org/wiki/Parity_of_a_permutation ( -, ), python, , , .

- :

#!/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 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

/ :

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))

:

| 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

, ( , " !", , "!", .

Answer 2

- "", , . :

(11) (12), . ? "" (11, 12, 15, -) . , . , , . , (11) (12) (7) (8), (8) (-):

, , , , " ", .

, , , , .