пятнашки всегда ли можно собрать
Игра Пятнашки: существование решения
Напомним, что игра представляет собой поле 
на , на котором расположены 
фишек, пронумерованных числами от 
до , а одно поле оставлено пустым. Требуется, передвигая на каждом шаге какую-либо фишку на свободную позицию, прийти в конце концов к следующей позиции:
Игру Пятнашки («15 puzzle») изобрёл в 1880 г. Нойес Чэпман (Noyes Chapman).
Существование решения
Здесь мы рассмотрим такую задачу: по данной позиции на доске сказать, существует ли последовательность ходов, приводящая к решению, или нет.
Пусть дана некоторая позиция на доске:
где один из элементов равен нулю и обозначает пустую клетку 
.
(т.е. перестановка чисел, соответствующая позиции на доске, без нулевого элемента)
Обозначим через 
количество инверсий в этой перестановке (т.е. количество таких элементов 
и 
, что 
, но 
a_j»>).
Далее, пусть 
— номер строки, в которой находится пустой элемент (т.е. в наших обозначениях 
.
Тогда, решение существует тогда и только тогда, когда 
чётно.
Реализация
Проиллюстрируем указанный выше алгоритм с помощью программного кода:
Доказательство
Однако оба эти доказательства были достаточно сложны.
В 1999 г. Арчер (Archer) предложил значительно более простое доказательство (скачать его статью можно здесь).
Решаемые и нерешаемые комбинации
Решаемые и нерешаемые комбинации
Начальную позицию можно разложить многими способами. Всего существует
16!=20 922 789 888 000 начальных позиций.
Это с учетом расположений пустой клетки. Например, вот такая позиция.
15!=1 307 674 368 000 позиций.
Например, вот такое начальное расположение
Здесь рассматривается четко, что пустая клетка всегда находится в правом нижнем углу.
Половина из всех раскладов решается. Другая половина не собирается, так как приходит вот к такому положению:
Как помним, это задача Лойда.
Надеюсь, вы поняли, что 50% раскладов собрать не удастся.
Любую начальную позицию можно проверить на решаемость. Причем не надо пытаться ее собрать и посмотреть на конечное расположение 15 и 14. Для этого достаточно лишь высчитать «Четность расклада», «Параметр беспорядка» (это понятие кто как хочет, так и называет). В реале действительно быстрее просто собрать за полминуты фишки и посмотреть что получилось, нежели считать в уме многоцифар. Но для полноты картины изучим теорию. Определение четности довольно сложное. Давайте посмотрим, что пишет Википедия:
является нечётной, то решения головоломки не существует
Есть еще одно определение, попавшееся на глаза:
головоломка имеет решение, если так называемый параметр беспорядка (число пар чисел, в которых большее число предшествует меньшему с прибавлением номера горизонтального ряда с пустой клеткой), четный
Хоть оно и проще, смысл по-прежнему сложно уловить.
Попытаемся объяснить более простым языком, как подсчитать Четность.
Здесь указаны номера позиций. Соответственно, чем меньше номер, тем более ранняя позиция (надеюсь, этот момент понятен).
Например, возьмем вот такой расклад:
Малость теории: Всего имеется 15 фишек, что образует 105 пар (14+13+12+. +1). На практике сравнить 105 пар не так уж и сложно, только надо их четко подсчитывать. Например, можно поступить так (см. рисунок выше):
Сначала берем первое число (у нас 12). Считаем, сколько чисел меньше находится после него. На примере это одиннадцать чисел (от 1 до 11 – эти числа меньше и расположены позже, то есть после рассматриваемого нами числа 12). Результат записали.
Теперь берем третье число (8) и считаем также количество меньших чисел, стоящих после (их шесть, то есть от 1 до 7 не считая 5, так как пятерка стоит раньше).
Так и продолжаем дальше.
Не забываем в самом конце прибавить ряд с пустой клеткой. У нас на примере это третий ряд.
Мы здесь не будем полностью считать четность, эти вычисления лишь пример как нужно делать. Да и нудно это математикой заниматься в таких объемах.
Всего подсчет займет минут 5-10. Если полученная сумма четная – позиция соберется. Если иначе (нечетная) – то не соберется.
История головоломки «Пятнашки» интересна и противоречива. Наиболее точной является такая история – придумал её Ноель Палмер Чепмэн (Noyes Palmer Chapman), который работал почтмейстером в штате Нью-Йорк в городе Канастота. В 1874 году он показал своим друзьям головоломку, которая состояла из шестнадцати пронумерованных квадратиков. Требовалось сложить эти квадратики в ряды по четыре штуки так, чтобы в каждом ряду сумма чисел составляла 34.
Старинный образец головоломки «Пятнашки», Франция 1880 год
Старые версии головоломки «Пятнашки» часто имели фишку с номером 16, которая могла быть удалена для игры в нормальные «Пятнашки». Она была для того чтобы можно было подумать над решением создания «Магического квадрата». В данном случае «Магический квадрат» должен состоять из чисел от 1 до 16, которые располагаются таким образом, что каждый из четырёх рядов, каждый из четырёх столбцов и обе диагонали имеют сумму равную 34.
«Магический квадрат» числа 34 в головоломке «Пятнашки»
Сын Ноя Чепмэна, Фрэнк несколько доработал идею головоломки и сначала привёз её в Сиракузы, а затем в Хартфорд, где наладил выпуск этой игры слушателями Американской школы для слабослышащих. К 1879 году головоломка «Пятнашки» уже начали продаваться в Хартфорде и в Бостоне.
А после этого началось массовое помешательство на логическую игру «Пятнашки» и её начали выпускать этой разными именами. Некий предприниматель Маттиас Райс в 1879 году начал производство головоломки под названием «Драгоценная головоломка» (Gem Puzzle). А в начале 1880 года стоматолог из Вустера (штат Массачусетс) Чарльз Певи привлёк всеобщее внимание к продаже своего варианта головоломки «Пятнашки» предложив денежное вознаграждение за решение задачи собирания головоломки.
Но всех больше остался в истории Сэм Ллойд – именно он больше всех утверждал, что именно он является изобретателем этой головоломки. И именно он назначил приз в 1000 долларов любому, кто сможет решить задачу по перестановке местами двух частей головоломки – фишек с числами 15 и 14. Так что теперь весьма распространённой ошибкой является то, что именно Сэм Ллойд является изобретателем головоломки «Пятнашки».
Карикатура изображающая Сэма Ллойда и проблему «15-14»
А 21 февраля 1880 года сын изобретателя «Пятнашек» Ной Чепмэн попытался оформить патент на изобретение под названием «Головоломка из бриллиантовых блоков» (Block Solitaire Puzzle), но его заявку отклонили, сославшись на то, что сходная головоломка «Puzzle-Blocks» запатентована Эрнестом У. Кинси. Вот так изобретение одного стало собственностью другого.
Возвращаясь к грандиозной по тем временам призовой сумме в 1000 долларов за перестановку местами фишек с цифрами 14 и 15 добавим, что масса людей бросилась искать решение этой задачи. Конечно же, все они предварительно купили у предприимчивого Сэма Ллойда его продукцию. Началось так называемое «пятнашечное сумасшествие».
Музыкальное произведение на тему «Пятнашечного сумасшествия»
Довольно быстро массовое движение по всеобщей заинтересованности головоломкой «Пятнашки» охватило Америку, Европу, Австралию, Новую Зеландию и даже азиатские страны. Эта ситуация весьма сильно напоминала то, что произошло когда появился кубик Рубика. Разгадка перестановки двух фишек стало почти всеобщим помешательством. Желающие найти решение увлечённо искали способ, забывая про еду, сон, учёбу и работу. Владельцы предприятий запрещали приносить на работу эту адскую игру, так как работники переставали работать. Владельцы бакалейных лавочек забывали открывать двери своих магазинов и принимать посетителей, лоцманы сажали суда на мель, а машинисты поездов проезжали станции увлечённо решая задачу по перестановке фишек. Рассказывали даже об одном известном священнике, который простоял зимнюю ночь под уличным фонарём и всё это время пытался вспомнить как ему удалось переставить местами фишки 15 и 14. Самое удивительное, что никто из тех кто утверждал, что нашёл решение не мог вспомнить и повторить последовательность ходов, которая привела к победе.
…За последние несколько недель вошла в моду новая игрушка-головоломка. и что от Атлантического океана до Тихого все население Соединенных Штатов прекратило работу и занимается только этой игрушкой; что в связи с этим вся деловая жизнь в стране замерла, ибо судьи, адвокаты, взломщики, священники, воры, торговцы, рабочие, убийцы, женщины, дети, грудные младенцы, — словом, все с утра до ночи заняты одним-единственным высокоинтеллектуальным и сложным делом. что веселье и радость покинули народ — на смену им пришли озабоченность, задумчивость, тревога, лица у всех вытянулись, на них появились отчаяние и морщины — следы прожитых лет и пережитых трудностей, а вместе с ними и более печальные признаки, указывающие на умственную неполноценность и начинающееся помешательство; что в восьми городах день и ночь работают фабрики, и все же до сих пор не удалось удовлетворить спрос на головоломку…
Политическая карикатура о поиске кандидата в президенты США
от республиканской партии в 1880 году
Но оказывается, что в задаче, за решение которой Ллойд предложил фантастическую призовую сумму, нет решения. Головоломку не получится собрать, у неё просто нет решения. Эта задача из области так называемых нерешаемых. Головоломка «Пятнашки» имеет решение, если число пар чисел, в которых большее число предшествует меньшему, четное. А так как по заданию надо поменять только одну пару (15 и 14), то так называемый параметр беспорядка делает задачу в таком расположении фишек нерешаемой. Ллойд знал об этом с самого начала, но общественность узнала этот важный момент значительно позже, когда ажиотаж на игру сошёл на нет, а хитрец Сэм Ллойд вошёл в историю и прилично подзаработал.
В процессе поиска решения для задачи по перестановке фишек 14 и 15 были разработаны другие задачи. И сейчас они так же актуальны и непросты как и почти полтора века назад.
Задачи для головоломки «Пятнашки» из буклета Modern Brand Inc
Problem No. 1 A Невозможное В Возможно
Problem No. 2 A Возможно B Невозможное
Problem No. 3 A Возможно B Невозможное
Problem No. 4 A Невозможное В Возможно
Problem No. 5 A Возможно B Невозможное
Problem No. 6 A Возможно B Невозможное
Problem No. 7 A Невозможное В Возможно
Problem No. 8 A Невозможное В Возможно
cartrege
cartregeПросто
ну. вот так просто.
Думаю, все знакомы с этой игрой с детства и каждый, хотя бы раз, да пробовал разместить все цифры в одном порядке.
Задача игры состоит обыкновенно в том, чтобы посредством последовательных передвижений, допускаемых наличием свободного поля, перевести любое начальное положение 15 шашек в нормальное (ну то есть 1 в правом верхнем, за ней справа 2, дальше 3, потом 4, во втором ряду сверху справа 5. ну и тэ дэ).
Ну, ясно, что рядом передвижений шашку 1 всегда можно поставить на место. Точно так же, не трогая шашки 1 можно поставить на место и шашку 2.. далее 3 и 4. В общем, привести верхнюю строку в порядок. Далее, не трогая верхнюю строку точно так же приводим в порядок и вторую (это уже чуть посложнее сделать, но не сильно). Потом, когда останется привести в порядок два ряда, нужно поставить на место шашки 9 и 13. Теперь, из всех приведенных в порядок шашек, дальше ни одной не трогаем. У нас остается участок в 6 полей, на котором нам нужно привести в порядок все остальные шашки. Здесь всегда можно привести в порядок шашки 10, 11 и 12. После того, как это сделано, шашки 14 и 15 могут оказаться в верном порядке (то есть сначала 14, а за ней 15) или в обратном (сначала 15, а потом 14).
А теперь секрет всей игры: если общее число беспорядков четное, то заданное расположение может быть приведено к нормальному конечному (L), другими словами оно принадлежит к разрешимым . Если же число беспорядков нечетное, то расположение принадлежит к неразрешимым (ноль беспорядков принимается за четное число). Вот и все!
Игра в пятнашки
Пятнашки – одна из известнейших миру головоломок. Она представляет набор, в который входит квадратная коробка, сторона которой равна 4 сторонам костяшки, то есть. 4х4. Внутри этой коробки 15 квадратных костяшек. В коробке остается 1 свободное место под одну костяшку. Цель игры – упорядочивание костяшек по порядку. Концом игры считается, когда все костяшки от 1 до 15 стоят друг за другом.
Игра поможет вам развить память и логическое мышление. У вас будет развиваться возможность просчитывать ходы вперед без ошибок. Сыграем?
Играть в пятнашки онлайн
Номерки уже разбросаны в случайном порядке. Нажатием на костяшку, Вы сможете ее передвигать в направлении свободной клетки. Постарайтесь распределить их по порядку, используя наименьшее количество ходов.
Эту игру можно купить практически в любом магазине детских или настольных игрушек. Материал, из которого сделаны пятнашки, может быть различный, как дерево, так и металл или пластик.
Правила игры
Если Вы играете в первый раз, то, наверное, задаетесь вопросом «как собрать пятнашки» или «как играть в пятнашки»? Это головоломка не из простых, и Вам потребуется логика и терпение для их собирания. В среднем людям приходится тратить 200-300 ходов на решение задачи. Попробуйте и Вы! После небольшой тренировки у вас получится куда быстрее, не сомневайтесь!
Алгоритм «Как собрать пятнашки»?
Как-то раз, собирая пятнашки, заметил, что чем меньше поле ячеек в игре пятнашки, тем проще их собрать. Получается, что проще всего собрать пятнашки размером 3х3 ячейки, чем например, пятнашки размером 4х4.
Пятнашки размером 3х3 элемента собираются очень легко, особенно если отсортировать все костяшки по порядку вокруг поля:
Для этого нужно перемещать самую первую костяшку по кругу против часовой стрелки, и при первой же возможности поставить следом за первой костяшкой, вторую, потом третью, собрав, таким образом, паровозик из костяшек от первой до последней.
Главное, чтобы последние две костяшки, в данном случае 7 и 8 стояли наоборот, то есть. паровозик из цифр должен выглядеть так: 1 2 3 4 5 6 8 7. Если мы поделим этот паровозик на строки, то как раз и получим собранные пятнашки.
Посмотрите еще раз на картинку выше, там костяшки 1 2 3 уже стоят на своем месте, осталось всего-то переместить костяшки 4 5 6 на второй ряд. В результате этого переноса костяшки 7 и 8 уже будут стоять в третьем ряду в нужном порядке.
Разделяй и властвуй
Это очень простой способ сбора пятнашек, однако, собрать таким способом пятнашки размером 4х4 ячейки уже намного сложнее, не говоря уже о пятнашках бОльшего размера.Если приосмотреться к этой игре внимательно, то можно увидеть, что ничего сложного нет, если разделить поле 4х4 ячейки на 3 части и собрать эти 3 части по отдельности.
Часть первая, костяшки 1 2 3 4
В первую очередь лучше собрать костяшки 1 2 3 4 и расположить их на своем месте, после чего просто “забыть” про них, будто их нет:
После того как мы про них “забыли”, дальше остается собрать пятнашки с размером поля уже 4х3, вместо 4х4.
Часть вторая, костяшки 5 9 13
Теперь нам нужно собрать костяшки 5 9 13 в паровозик и поставить их сбоку слева.
Часть третья, оставшиеся костяшки
Теперь, когда мы уже поставили костяшки 1 2 3 4 и 5 9 13 на свои места, рабочее поле уменьшилось до размеров 3х3, и осталось только собрать пятнашки размером 3х3:
Единственное отличие заключается только в номерах костяшек, которые нужно отсортировать так же по возрастанию, поменяв последние две костяшки наоборот, чтобы получился паровозик: 6 7 8 10 11 12 15 14, который так же разделится на 3 ряда:
Проблема может быть только в том, что костяшки могут встать не по порядку. Вместо паровозика из цифр 6 7 8 10 11 12 15 14 может получиться последовательность 6 7 8 10 11 12 14 15. В таком случае нужно будет постараться поменять эти костяшки местами. Зачастую для этого приходится ломать уже построенные костяшки 5 9 13 или 1 2 3 4, но зато они потом так же быстро выстраиваются снова.
Скачать
Скачать игру пятнашки на свой компьютер Вы сможете по ссылке, расположенной ниже. Скачав игру, Вы сможете решать головоломку без интернета, нежели Вы будете решать ее на сайте.
Системные требования: Windows XP, Vista, 7, 8, 8.1, 10.
Видео
Здесь Вы можете увидеть видео-пример по прохождению игры Пятнашки.
Подвижная игра пятнашки
Количество участников может быть различным (оптимальное 4-12). Отметим границу для игры в пятнашки, к примеру 7 метров в длину и ширину.
Выбирают водящего человека, который как в салках бегает за другими ребятами. Остальные же игроки располагаются по периметру квадрата. Выход за пределы запрещен. Цель водящего – догнать других игроков и «запятнать» их. Запятнанные игроки немедленно покидают поле. Игра продолжается пока не будут запятнаны все игроки.После конца кона можно начать еще раз, выбрав другого водящего.
История появления игры
Авторство игры принадлежит Ною Палмеру Чепмэну. Еще в далеком 1874 году Ной показывал свою игру знакомым, которая включала в себя квадратную коробку, сторона которой равна 4 сторонам костяшки, в свою очередь костяшек 15 одинаковых квадратных штук. В коробке остается 1 свободное место под одну костяшку. Однако, целью игры было перемещение костей так, чтобы в каждом ряду была сумма 34.
Особое внимание было к игру с 1880. Именно в этом году некто Чарльз Певи, установил денежное вознаграждение за решение данной задачи. Популярность игры мгновенно выросла. С тех пор правила поменялись и теперь они такие, как описаны выше.Существуют различные варианты игры c разными размерами:
Пятнашки 3х3
Пятнашки 4х4
Пятнашки 5х5
Похожие игры
Существуют похожие игры, в которые вы сможете играть онлайн. Игры взяты с сайта нашего партнера BrainApps, на котором вы сможете найти и множество других интересных и увлекательных игр. Например:
Игра «Анаграммы»
Анаграммы помогут развить такие качества как: внимание, концентрация, скорость мысли, скорочтение. В этой игре Вам предстоит выбрать 1 вариант из 4, в которым перемешаны только те буквы, которые входят в состав данного слова. В каждом раунде дается новое слово. Помните, что время ограничено! Чем быстрее вы будете искать ответ – тем больше очков получите в конце игры.
А если вы хотите играть с сохранением статистики результатов, то предлагаем игру от нашего партнера BrainApps, нужно только зарегистрироваться и около 30 бесплатных развивающих игр Ваши:
