Solution to my BP 59: the left boxes represent 15 puzzle states that can be solved. The configurations in the boxes on the right can't be solved.
The 15 puzzle moves invariant:
"The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner. This is an invariant because each move changes both the parity of the permutation and the parity of the taxicab distance."
I've found the parity with a little Python function:
def permutation_parity(perm):
n = len(perm)
#assert sorted(perm) == list(range(1, n + 1))
n_inversions = 0
for i in range(n):
for j in range(i + 1, n):
if perm[i] > perm[j]:
n_inversions += 1
return 'even' if n_inversions % 2 == 0 else 'odd'
Detailed box contents:
State of Box 2:
(3, 11, 1, 15)
(7, 6, 4, 9)
(8, 12, 0, 2)
(13, 14, 10, 5)
permutation = odd
taxicab_distance = 1 + 1 = 2 = even
odd + even = odd
State of Box 8:
(5, 12, 11, 15)
(13, 4, 7, 1)
(2, 0, 14, 6)
(3, 9, 10, 8)
permutation = odd
taxicab_distance = 2 + 1 = 3
odd + odd = even
See also:
https://en.wikipedia.org/wiki/15_puzzle
https://en.wikipedia.org/wiki/Parity_of_a_permutation
#bongardproblem #mathpuzzle #puzzle #visualmath