Математики, ваша помощь нужна. «Пятнашки»

Так вам не математики нужны, а следователи. Насколько ваша балалайка соответствует стандартам детским играм онлайн? Поди денег желаете скосить с наших малышей? В глаза мне, в глаза!!!

зависит конечно - в 3х3 как раз не хватает одного "лишнего" поля/линии чтобы можно было поменять местами фишки.

malls, без паники.

Фишек восемь.

cyber_Krosh добавил 20.10.2011 в 00:37

Тоже без паники.

Я у гугла в доле, не трогаю я малышацкие копилки...

Да и сюда засуну, то, что искал несколько лет:

я потому добавил про "линию" - ибо был почти уверен что не поймут! :)

понятно что их 8 - но эти нельзя локально менять - только по сути по кругу гонять.

не очень уверен в точности математики (точнее просто тупой пример привожу) - но кругов таких (вариантов перемещения) в поле 3х3 - кажись 8 штук

Итого 8 вариантов перемещения на 8 фишек - 64 (на самом деле их там число как то увязанное с 3^3 - т.е. 27 и т.п.)

8 фишек на 9 клеток - 72 варианта размещения - вот и трудности.

в поле 15 фишек на 16 клеток - вариантов размещения 240, а вариантов перемещения - гораздо больше (лень считать) больше 250 точно. (4^4 уже 256 дает плюс коэффициенты какие то)

короче не математика конечно - но примерное представление думаю понятно.

можно от обратного пойти - поле 2х2 и 3 фишки дают возможность собрать только в 2 случаях (изначально правильных) из 3х4 = 12 вариантов размещения.

проблема в том, что при _любом_ количестве полей, насколько я понял, в 50% случаев правильная последовательность не сложится в последних двух цифрах.

Этот тезис нужно подтвердить или опровергнуть.

тынц

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

Простой пример Кубик Рубика - "раскрутите" его как угодно - и он всегда соберется. Стоит вытряхнуть из него квадратики и хаотично собрать их - вероятность собрать кубик после этого довольно низка.

давай урл с нескладывающимся раскладом, разберемся =)

см. комбинаторика -> перестановки. Как-то в универе считали сходится ли перестановка или нет.

А вообще, не нужны тебе такие пятнашки.

Пятнашки представляют собой классическую задачу для моделирования эвристических алгоритмов. Обычно задачу решают через количество перемещений и поиск манхеттенского расстояния между каждой костяшкой и её позицией в собранной головоломке. Для решения используются алгоритмы наподобие алгоритма A*.

Нерешаемая комбинация, предложенная Ноем Чепменом

Можно показать, что ровно половину из всех возможных 1 307 674 368 000 (=15!) начальных положений пятнашек невозможно привести к собранному виду: пусть квадратик с числом i расположен до (если считать слева направо и сверху вниз) k квадратиков с числами меньшими i. Будем считать ni = k, то есть если после костяшки с i-м числом нет чисел, меньших i, то k = 0. Также введем число e — номер ряда пустой клетки (считая с 1). Если сумма

является нечётной, то решения головоломки не существует[2].

Для обобщённых пятнашек (с бо́льшим, чем 15, количеством костяшек) задача поиска кратчайшего решения является NP-полной.

Если допустить поворот коробки на 90 градусов, при котором изображения цифр окажутся лежащими на боку, то можно перевести неразрешимые комбинации в разрешимые (и наоборот). Таким образом, если вместо цифр на костяшки нанести точки и не фиксировать положение коробки, то неразрешимых комбинаций вообще не окажется.

Вики