* представляют собой классическую задачу для моделирования эвристических алгоритмов. Обычно задачу решают через количество перемещений и поиск манхеттенского расстояния между каждой * и её позицией в собранной комбинации. Для решения используются алгоритмы наподобие алгоритма A*. Можно показать, что ровно половину из всех возможных 1 307 674 368 000 (=15!) начальных положений * невозможно привести к собранному виду. О чем идет речь?
Игра 15. Неуж-то никогда не играл в неё? Квадрат 4х4, заполнен 15 квадратиками с числами от 1 до 15, одна клетка свободна. Надо расставить эти 15 квадратиков по порядку: 1 ряд:1 2 3 4 2 ряд:5 6 7 8 3 ряд:9 10 11 12 4 ряд:13 14 15 пусто
Добавлено (26.07.2011, 15:34) --------------------------------------------- я как-то сразу на число 15 не обратил внимания и не заметил. Действительно, если запутывать из результата, то головоломку собрать возможно. А если 14 и 15 поменять местами, то нет, то есть 50% вариантов расстановок невозможно решить.
Ну, дк, 15 же это называется. "Пятнашки" - более современное название. Кстати, есть усложненная версия - 12. Прямоугольник 5х3, два квадратика заклеены так, что получается "восьмерка" с одним свободным полем
