Математические методы сборки пятнашек

ScRolL

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

seregaohota

Нет, хочет разгадать оригинальную задачу изобретателя Сэмюэля Лойда где 14 и 15 местами переставлены и заработать миллион - его так за 100 лет никому и не выплатили.
Читай Кострикин. Введение в алгебру.

SonnyFly

 Доказано, что существуют неприводимые начальные расположения.

seregaohota

Ровно половина. Как перестановки. Всё упирается в чётность и нечётность перестановки. Задача, за которую Лойд обещал заплатить $$, вызвала полное сумасшествие, и все бросились её разгадывать. Изобретатель очевидно знал, что не решается. Наварился на продаже головоломок хорошо.

toxin

Есть простые алгоритмы складывания головоломки, когда это возможно. Грубо говоря, нужно в начале поставить на свое место единицу, затем двойку и.т.д. (есть определенные сложности с последним квадратом в ряду и с последними двумя рядами разумеется) Полиномиальных алгоритмов, которые находят минимальное решение на сколько мне известно нет. В прочем, эвристические алгоритмы с этой задачей не плохо справляются.

kravecnata

Ian Parberry, A al-Time Algorithm for the (n²-1)-Puzzle, Inf. Process. Lett., 1995, 56(1):23-28, and references there.
Оставить комментарий
Имя или ник:
Комментарий: