ПРАВИТЕЛЬСТВО САНКТ – ПЕТЕРБУРГА КОМИТЕТ ПО ОБРАЗОВАНИЮ
Государственное бюджетное общеобразовательное учреждение гимназия № 000
Невского района Санкт – Петербурга
Адрес: Санкт-Петербург, ул. Новосёлов, д.21
Телефон/, e-mail: *****@***ru
ПРОЕКТНО – ИССЛЕДОВАТЕЛЬСКАЯ ДЕЯТЕЛЬНОСТЬ
ТЕМА ПРОЕКТА
«Игра в 15» или «пятнашки»
Руководитель проекта
,
К. п.н., учитель математики
Работу выполнил
8 «В» класс
г. Санкт – Петербург
2016
Содержание
Содержание 2
Введение 3
Основная часть 5
Глава 1. История головоломки 5
История происхождения головоломки 5
История теорий решения головоломки 9
Глава 2. Практическая работа с головоломкой 13
Проверка алгоритма решения головоломки для поля 4 на 4. 13
Обобщение алгоритма решения головоломки для поля n на n 15
Заключение 20
Список литературы 21
Введение
Предлагаемая вниманию читателя исследовательская работа посвящена популярной головоломке 19 века – «пятнашки» или «игра в 15». В этой работе я расскажу про «игру в 15» и покажу алгоритм для решения этой головоломки. Меня заинтересовала эта игра из – за того, что решив поиграть, я не смогла ее решить и задумалась над тем как это сделать.
Актуальность вопроса. Данная тема выбрана вследствие того, что в настоящее время игра «Пятнашки» встречается часто и при ее решении возникают трудности.
Цель работы: выяснить, что же это «Игра в 15», и показать алгоритм для ее решения.
Для достижения этой цели мы ставим перед собой следующие задачи:
1. Изучить литературу по данной теме.
2. Найти и описать разнообразие видов данной игры.
3. Составить алгоритм для решения головоломки.
4. Проверить на практике эффективность алгоритма для решения.
Гипотеза 1: если при передвижении фишек использовать один и тот же способ, то головоломку можно будет легко решить.
Гипотеза 2: для решения головоломки пятнашки с большим или меньшим количеством фишек можно использовать тот же алгоритмом, что и для решения головоломки с 15 фишками.
Методы исследования:
1. Изучение специальной литературы.
2. Обобщение и систематизация материала по данной теме.
3. Наблюдение и фиксация наблюдений.
Термины, встречающиеся в исследовательской работе
Комнка (конно-железная городская дорога) — вид общественного транспорта, широко применявшегося до перевода железной дороги на паровую, тепловую, электрическую или канатную тягу. Наиболее распространённой областью применения конки был городской транспорт; таким образом, конка была предшественником электрического трамвая.
Почтмемйстер (происходит от нем. Postmeister) — в дореволюционной России и других странах руководитель, начальник почтового учреждения (почтовой конторы).
Рейхстаг — парламент в кайзеровской Германии.
Индуктивное умозаключение - процесс логического вывода на основе перехода от частного положения к общему.
Основная часть
Глава 1. История головоломки
Сайт «Википедия» предлагает следующее определение понятия “игра в 15” — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов (и в три раза больше для набора в 8 элементов), соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке, добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений. [2]
История происхождения головоломки
Изобретателем головоломки был Ной Палмер Чепмэн, почтмейстер из Канастоты , который ещё в 1874 году показывал друзьям головоломку, состоящую из шестнадцати пронумерованных квадратиков, которые надо было сложить в ряды по четыре штуки. [2]
Старые версии головоломки «Пятнашки» часто имели фишку с номером 16, которая могла быть удалена для игры в нормальные «Пятнашки». Она была для того чтобы можно было подумать над решением создания «Магического квадрата». В данном случае «Магический квадрат» должен состоять из чисел от 1 до 16, которые располагаются таким образом, что каждый из четырёх рядов, каждый из четырёх столбцов и обе диагонали имеют сумму равную 34. [3]
Сын Ноя Чепмэна, Фрэнк Чепмэн, привёз доработанные головоломки в Сиракузы (штат Нью-Йорк), а затем в Хартфорд (Коннектикут), где слушатели Американской школы для слабослышащих начали производство головоломки. К 1879 году она уже продавалась не только в Хартфорде, но и в Бостоне. Тогда о «пятнашках» узнал художник по дереву Матиас Райс.
В декабре 1879 года он начал бизнес по производству новой головоломки под названием «Драгоценная головоломка». В начале 1880 года некий Чарльз Певи, дантист из Вустера, привлёк внимание общественности, предложив денежное вознаграждение за решение задачи собирания головоломки, что добавило популярности новой забаве. Весной того же года игра достигла Европы. 21 февраля 1880 года Ной Чепмэн попытался оформить патент на своё изобретение под наименованием «Block Solitaire Puzzle», однако заявка на патент была отклонена, так как мало отличалась от уже оформленного тремя годами ранее патента «Хитрые блоки»,
«Puzzle-Blocks». [2]
Сайт «библиотека по математике» предлагает такую историю головоломки: Общеизвестная коробочка с 15 нумерованными квадратными шашками имеет любопытную историю, о которой мало кто из игроков подозревает. Расскажем о ней словами немецкого исследователя игр, математика В. Аренса.
Около полувека назад - в конце 70-х годов - вынырнула в Соединенных Штатах "игра в 15"; она быстро распространилась и, благодаря несчетному числу игроков, которых она заполонила, превратилась в настоящее общественное бедствие. То же наблюдалось по эту сторону океана, в Европе. Здесь можно было даже в конках видеть в руках пассажиров коробочки с 15 шашками. В конторах и магазинах хозяева приходили в отчаяние от увлечения своих служащих и вынуждены были воспретить им игру в часы занятий и торговли. Содержатели увеселительных заведений ловко использовали эту манию и устраивали большие игорные турниры.
Игра проникла даже в торжественные залы германского рейхстага. "Как сейчас вижу в рейхстаге седовласых людей, сосредоточенно рассматривающих в своих руках квадратную коробочку", - вспоминает известный географ и математик Зигмунд Гюнтер, бывший депутатом в годы игорной эпидемии. В Париже игра эта нашла себе приют под открытым небом, на бульварах, и быстро распространилась из столицы по всей провинции. "Не было такого уединенного сельского домика, где не гнездился бы этот паук, подстерегая жертву, готовую запутаться в его сетях", - писал один французский автор.
В 1880 г. игорная лихорадка достигла, по-видимому, своей высшей точки. Но вскоре после этого тиран был повержен и побежден оружием математики. Математическая теория игры обнаружила, что из многочисленных задач, которые могут быть предложены, разрешима только половина; другая не разрешима никакими ухищрениями. Стало ясно, почему иные задачи не поддавались самым упорным усилиям, и почему устроители турниров отваживались назначать огромные премии за разрешения задач. В этом отношении всех превзошел изобретатель игры, предложивший издателю нью-йоркской газеты для воскресного приложения неразрешимую задачу с премией в 1000 долларов за ее разрешение; так как издатель колебался, то изобретатель выразил полную готовность внести названную сумму из собственного кармана. Имя изобретателя Самуэль (Сэм) Лойд. Он приобрел широкую известность как составитель остроумных задач и множества головоломок. Любопытно, что получить в Америке патент на придуманную игру ему не удалось.
Согласно инструкции, он должен был представить "рабочую модель" для исполнения пробной партии; он предложил чиновнику патентного бюро задачу, и когда последний осведомился, разрешима ли она, изобретатель должен был ответить: "Нет, это математически невозможно". "В таком случае, - последовало возражение, - не может быть и рабочей модели, а без модели нет и патента". Лойд удовлетворился этой резолюцией, - но, вероятно, был бы более настойчив, если бы предвидел неслыханный успех своего изобретения".
Приведем собственный рассказ изобретателя игры о некоторых фактах из ее истории:
Рис. 1. Игра в 15
"Давнишние обитатели царства смекалки, - пишет Лойд, - помнят, как в начале 70-х годов я заставил весь мир ломать голову над коробкой с подвижными шашками, получившей известность под именем "игры в 15" (рис. 10). Пятнадцать шашек были размещены в квадратной коробочке в правильном порядке, и только шашки 14 и 15 были переставлены, как показано на прилагаемой иллюстрации (рис. 11). Задача состояла в том, чтобы, последовательно передвигая шашки, привести их в нормальное положение, причем, однако, порядок шашек 14 и 15 должен быть исправлен.
Рис. 2. 15 шашек были размещены в квадратной коробочке в правильном порядке, и только шашки 14 и 15 были переставлены
Премия в 1000 долларов, предложенная за первое правильное решение этой задачи, никем не была заслужена, хотя все без устали решали эту задачу. Рассказывали забавные истории о торговцах, забывавших из-за этого открывать свои магазины, о почтенных чиновниках, целые ночи напролет простаивавших под уличным фонарем, отыскивая путь к решению. Никто не желал отказаться от поисков решения, так как все чувствовали уверенность в ожидающем их успехе.
Штурманы, говорят, из-за игры сажали на мель свои суда, машинисты проводили поезда мимо станций; фермеры забрасывали свои плуги». [3]
Из всей истории можно сказать, что в 19 веке головоломка набрала большую популярность из – за ее неразрешимости. И все же неужели никто не смог ее решить?
История теорий решения головоломки
Этот же сайт продолжает рассказывать о головоломке «Пятнашки», только теперь про решение головоломки, за которое Ной Палмер Чепмен готов выплатить 1000 долларов.
Изучим теоретические основания этой игры. В полном виде она очень сложна и тесно примыкает к одному из отделов высшей алгебры ("теория определителей"). Мы ограничимся лишь некоторыми соображениями, изложенными В. Аренсом.
Задача игры состоит обыкновенно в том, чтобы посредством последовательных передвижений, допускаемых наличием свободного поля, перевести любое начальное расположение 15 шашек в нормальное, т. е. в такое, при котором шашки идут в порядке своих чисел: в верхнем левом углу 1, направо - 2, затем 3, потом в верхнем правом углу 4; в следующем ряду слева направо: 5, 6, 7, 8 и т. д. Такое нормальное конечное расположение мы даем здесь на рис. 10."Вообразите теперь расположение, при котором 15 шашек размещены в пестром беспорядке. Рядом передвижений всегда можно привести шашку 1 на место, занимаемое ею на рисунке.
Точно так же возможно, не трогая шашки 1, привести шашку 2 на соседнее место вправо. Затем, не трогая шашек 1 и 2, можно поместить шашки 3 и 4 на их нормальные места: если они случайно не находятся в двух последних вертикальных рядах, то легко привести их в эту область и затем рядом передвижений достичь желаемого результата. Теперь верхняя строка 1, 2, 3, 4 приведена в порядок, и при дальнейших манипуляциях с шашками мы трогать этого ряда не будем.
Таким же путем стараемся мы привести в порядок и вторую строку: 5, 6, 7, 8; легко убедиться, что это всегда достижимо. Далее, на пространстве двух последних рядов необходимо привести в нормальное положение шашки 9 и 13; это тоже всегда возможно. Из всех приведенных в порядок шашек 1, 2, 3, 4, 5, 6, 7, 8, 9 и 13 в дальнейшем ни одной не перемещают; остается небольшой участок в шесть полей, в котором одно свободно, а пять остальных заняты шашками 10, 11, 12, 14, 15 в произвольном порядке.
В пределах этого шестиместного участка всегда можно привести на нормальные места шашки 10, 11, 12. Когда это достигнуто, то в последнем ряду шашки 14 и 15 окажутся размещенными либо в нормальном порядке, либо в обратном (рис. 11). Таким путем, который читатели легко могут проверить на деле, мы приходим к следующему результату. Любое начальное положение может быть приведено к расположению либо рис. 1, либо рис. 2.
Если некоторое расположение, которое для краткости обозначим буквою S, может быть преобразовано в положение I, то, очевидно, возможно и обратное - перевести положение I в положение S. Ведь все ходы шашек обратимы: если, например, в схеме I мы можем шашку 12 поместить на свободное поле, то можно ход этот тотчас взять обратно противоположными движениями. Итак, мы имеем две такие серии расположений, что положения одной серии могут быть переведены в нормальное I, а другой серии - в положение II. И наоборот, из нормального расположения можно получить любое положение первой серии, а из расположения II - любое положение второй серии. Наконец, два любых расположения, принадлежащих к одной и той же серии, могут быть переводимы друг в друга. Нельзя ли идти дальше и объединить эти два расположения - I и II? Можно строго доказать (не станем входить в подробности), что положения эти не превращаются одно в другое никаким числом ходов. Поэтому все огромное число размещений шашек распадается на две разобщенные серии:
На те, которые могут быть переведены в нормальное I: это - положения разрешимые, На те, которые могут быть переведены в положение II и, следовательно, ни при каких обстоятельствах не переводятся в нормальное расположение: это - положения, за разрешение которых назначались огромные премии.Как узнать, принадлежит ли заданное расположение к первой или ко второй серии? Пример разъяснит это.
Рассмотрим такое расположение. Первый ряд шашек в порядке, как и второй, за исключением последней шашки (9). Эта шашка занимает место, которое в нормальном расположении принадлежит 8. Шашка 9 стоит, значит, ранее шашки 8: такое упреждение нормального порядка называют "беспорядком". О шашке 9 мы скажем: здесь имеет место 1 беспорядок. Рассматривая дальнейшие шашки, обнаруживаем "упреждение" для шашки 14; она поставлена на три места (шашек 12, 13. 11) ранее своего нормального положения; здесь у нас 3 беспорядка (14 ранее 12; 14 ранее 13; 14 ранее 11). Всего мы насчитали уже 1+3=4 беспорядка.
Далее, шашка 12 помещена ранее шашки 11, и точно так же шашка 13 ранее шашки 11. Это дает еще 2 беспорядка. Итого имеем 6 беспорядков.
Подобным образом для каждого расположения устанавливают общее число беспорядков, освободив предварительно последнее место в правом нижнем углу. Если общее число беспорядков, как в рассмотренном случае, четное, то заданное расположение может быть приведено к нормальному конечному; другими словами, оно принадлежит к разрешимым. Если же число беспорядков нечетное, то расположение принадлежит ко второй серии, т. е. к неразрешимым (нуль беспорядков принимается за четное число их). Благодаря ясности, внесенной в эту игру математикой, прежняя лихорадочная страстность в увлечении сейчас совершенно немыслима. Математика создала исчерпывающую теорию игры, теорию, не оставляющую ни одного сомнительного пункта. Исход игры зависит не от каких-либо случайностей, не от находчивости, как в других играх, а от чисто математических факторов, предопределяющих его с безусловной достоверностью». [3]
Из всего вышесказанного следует, что первые две строчки легко привести к изначальному положению и основные трудности могут случится в третьей и четвертой строчках. Так же можно сразу определить возможность решения головоломки способом подсчетов беспорядков.
Глава 2. Практическая работа с головоломкой
Проверка алгоритма решения головоломки для поля 4 на 4.
Для проверки теорий решения мы взяли самый обычный и распространённый вид головоломки «Пятнашки», состоящий из 15 костяшек. Одно из решений представляет собой повторяющийся алгоритм, про который я подробно расскажу.
На данной картинке представлена сама головоломка уже в собранном виде.
Эта картинка показывает разложенный вид который мы будем привадить к собранному.
Первое что можно всегда передвинуть на свои места это фишки с номерами 1, 2 и 3. Они всегда без труда встают на свои места.
Следующими шагами вступает в действие важная часть алгоритма. Мы передвигаем фишки так чтобы пустой квадратик оказался под фишкой 1 , затем спускаем ее вниз и задвигаем все верхние влево. Затем, не трогая числа 1, 2, 3, передвигаем фишку 4 к 3.
Следом освобождаем верхний правый угол, сдвигаем верхние фишки вправо и ставим единицу на свое место. Первая строчка поставлена.
С второй строчкой все тоже самое. Ставим числа 5, 6 и 7 на свои места, сдвигаем 5, добавляем 8 и второй ряд готов. Следуя из информации данной сайтом «Библиотека по математике» можно точно сказать то разрешима эта головоломка или нет, так как в ней имеются 18 беспорядков то она разрешима.
Дальше будет немного по – сложнее, так как нам сразу нужно буде поставить две фишки. В данном случае это будут 9 и 10, причем первая должна быть под второй.
Остается поставить все в нужном порядке, но и здесь нужно быто внимательнее с четвертым рядом, так как можно подобрать не правильное решение. 11 и 12 сразу ставим после 10(здесь уже применяем алгоритм), при этом сразу нужно смотреть что бы 13 стояла после 9 и тогда, сдвигая ряд, ставим 9 на свое место. Четвертый ряд сразу же оказывается собранным и головоломка решена.
Это был один из вариантов решения, теперь я расскажу, что будет если после постановки 10 и 9 остальные фишки не ставятся на свои места. В это случае меняется решение последних двух строчек.
Вот мы поставили первые два ряда и теперь нужно поставить 13 и 14 в левом нижнем углу, так что бы 13 была над 14. Практически так же как и в первом способе, но после этого все поменяется.
Теперь нужно поставить 15 после 14, а 9 и 10 после 13 так как на картинке. Следующими шагами снова действует алгоритм, сдвигая 4 строчку, передвигаем 13 вниз, а 12 вверх.
Так же бывает так, что ни один из способов не помогает и тогда остается только начать сначала.
Обобщение алгоритма решения головоломки для поля n на n
Теперь зная алгоритм решения головоломки пятнашек с размером поля 4 на 4 фишки рассмотрим вторую гипотезу, в которой говорится о том, что головоломки с большим или меньшим количеством фишек (3 на 3, 5 на 5, 6 на 6 и т. д.) можно решить одним тем же способом. Для начала решим головоломку 3 на 3 фишки в которой 8 чисел.
У нас есть данный порядок размещения чисел на поле:
Как и в алгоритме, для начала простроим первый ряд. Приведем 1 и 3 в левый верхний угол первой строчки. Затем опустим 1 на строчку вниз и перетянем ряд влево.
Найдем и приведем число 3 к числу 2, затем прокрутим ряд по часовой стрелке и получим построенный первый ряд.
Теперь будем собирать второй ряд и третий ряд. Для этого, следуя алгоритму, найдем числа 4 и 5 и поставим их друг за другом с левой стороны, где 4 будет под 5. Затем приведем фишку 6 к числу 5.
И последним действием прокрутим два последних ряда по часовой стрелке и получим решенную головоломку.
Таким образом мы собрали головоломку пятнашки в варианте 3 на 3 используя алгоритм, используемый для решения головоломки 4 на 4. Но из-за меньшего размера, а соответственно и количества чисел в варианте 3 на 3 нам пришлось приводить только 1, 2 к первому ряду, так как в варианте головоломки 4 на 4 нужно привести числа 1, 2, 3.
Теперь решив головоломки 4 на 4 и 3 на 3, можно сказать, что для одного и того же требуется один алгоритм решения. Остается проверить 5 на 5 и, возможно, 6 на 6 и тогда можно будет точно сказать о верности и неверности гипотезы.
Почему же мы не рассматриваем вариант головоломки 2 на 2, скорее всего спросите вы. Вот пример головоломки пятнашки в варианте 2 на 2:
Здесь вариант решения один – просто прокрутить числа против или по часовой стрелке до установления числа 1 на позицию левого верхнего угла и головоломка решена.
Теперь рассмотрим вариант головоломка 5 на 5, где будет 24 числа, которые нам нужно будет поставить по порядку. Они даны нам в данной комбинации:
И теперь приступим к самому решению. Как и всегда для начала нам нужно привести числа первого ряда на свои места. Приводим 1, затем 2, 3 и 4. Используем алгоритм и получаем первый ряд.
Затем таким же способом собираем второй ряд,
третий ряд. Для последних двух мы используем алгоритм передвигая числа 16 и 17 по порядку в левую сторону, ставя 16 под 17 и за ними выстраиваем остальные числа четвертого ряда. Но при этом внимательно смотрим за числами пятого ряда, что бы и там числа стояли по порядку, иначе потом нам придется передвигать полностью последние два ряда.
Теперь нам остается сделать одно действие и тогда мы получим собранную головоломку.
Заключение
На данный момент мы смогли решить головоломки трех видов: 3 на 3, 4 на 4, 5 на 5. На основе полученных результатов можно сделать индуктивное умозаключение о верности гипотезы о том, что для решения головоломки пятнашки с большим или меньшим количеством фишек можно использовать тот же алгоритм, что и для решения головоломки с 15 фишками.
Нам уже точно известно из практики, что алгоритм сам по себе прост и подходит для решения головоломок разных вариантов, с разными количествами фишек в них. Единственное, что менялось – это само число приведений чисел, а также число ходов, требуемых для этих передвижений. На самом деле усложнялась только первая часть, с приведением первых чисел ряда и усложнялась только из-за их большого количества, вторая же часть, с увеличением количества фишек, становилась все проще в решении. Так как на последних двух оставшихся строчках особо ничего не по перемещать и ограниченность пространства в длину и ширину играет здесь главную роль, а с увеличением этих показателей решение не представляет трудности. Таким образом сколько именно фишек будет в головоломке абсолютно не важно, даже если их будет 10.000 или 100.000.000, все зависит от времени решающего и от того знает ли он алгоритм.
В процессе работы над исследованием я приобрела опыт решения головоломок на подобии «игры в 15», а также смогла потренироваться в умении обдумывать различные ситуации и находить способы их решения. Думаю, что полученные мной знания позволят мне избежать ошибок в дальнейшем решении задач, логических игр и помогут мне в жизни.
