Fifteen puzzle (?)

Discuss about this problem

Given n,let P_n be the set of all transpositions of adjacent elements in the n*n square grid plus identity. given n, find a permutation p of {1..n}^2 such that max{i,p not in P_n^i} is as big as possible A087725 0,6,31,80 Maximum number of moves required for the n X n generalization of Sam Loyd's Fifteen Puzzle. A089484 1,2,4,10,24,54,107,212,446,946,1948,3938,7808,15544,30821,... Number of configurations of Sam Loyd's sliding block 15-puzzle that require a minimum of n moves to be reached, starting with the empty square in one of the corners. A090164,A090165 can be done in 2 parts like the pancakes contest First part: submit several hard-to-solve N*N Loyd's puzzles. Second part: solve all submitted puzzles in the miminum number of moves