--- предыстория ---

Всем (ну почти всем) известен факт что в игре "пятнашки" есть два вида размещения чисел на игровом поле (ну если числа размещать рандомно в клетках, а не мешать из исходного состояния как кубик-рубика). В первом случае при решении пятнашек получаем "правильную" раскладку:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 Х

Во втором случае в результате "решения" получаем "неправильную" раскладку, когда числа 14 и 15 поменяны местами:

1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 Х

перейти из правильной раскладки в неправильную и наоборот нельзя никакими перестановками.

--- Задача ---
Собственно задача в том, чтобы имея массив 4x4 чисел от 0 до 15 (где 0 это пусто) определить к какому он раскладу относится "правильному" или "неправильному".

ПыСы: Решения пока не искал, наткнулся на историю про игру 15, вот и придумал.

пофиг уже было?

решение элементарно - просто считаем четность перестановки.

(2) +100500

а вот тоже самое, но для 3*3 или 5*5?

А варианты не описанные в известных книжках есть?

(4) ничего не меняется. Четность при каждом движении остается той-же.  Независимо от размера доски.

(6) мне кажется для нечетных четность меняется или меня глючит?

(7) глючит.

(2) блин, ты реально умный!
а что такое "четность перестановки".?

а доказательство?

вот тут наверно
http://habrahabr.ru/company/taucraft/blog/146508/

(9) Четность количества инверсий естественно.

(8) да, четность транспозиций инвариантно

(12) вот сейчас ты в моих глазах еще умней стал! - я чувствую как растет пропасть между тобой и обычными людьми! ;-)