Назад

Программа игры Пятнашки

 

 

 

 

 

 

 

 

 

 

 

Пятнашки — популярная головоломка, которую придумал в 1878 году Ной Чепмэн. Существует вариант для восьми элементов. Представляет собой набор одинаковых квадратных фишек с числами в квадратной коробке. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов и в три раза больше для набора в 8 элементов, соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке добиться упорядочивания их по номерам, сделав как можно меньше перемещений.
Пятнашки представляют собой классическую задачу для моделирования эвристических алгоритмов. Обычно задачу решают через количество перемещений и поиск манхеттенского расстояния между каждой костяшкой и её позицией в собранной головоломке.
Можно показать, что ровно половину из всех возможных 1307674368000 (=15!) начальных положений пятнашек невозможно привести к собранному виду: пусть квадратик с числом i расположен до (если считать слева направо и сверху вниз) k квадратиков с числами меньшими i. Будем считать ni = k, то есть если после костяшки с i-м числом нет чисел, меньших i, то k = 0. Также введем число e - номер ряда пустой клетки (считая с 1). Если сумма является нечётной, то решения головоломки не существует.
Для вариантов пятнашек с большим, чем 15, количеством костяшек задача поиска кратчайшего решения является NP-полной.
Пошаговый алгоритм программы игры Пятнашки:
1. Создание игрового поля генератором случайных чисел.
2. Прорисовка игрового поля.
3. Ожидание нажатия клавиши игроком. Если нажата:
а) “Esc” – переход к пункту 6;
б) “Лево”, “Право”, “Вверх” или “Вниз”, то переход к соответствующей функции проверки передвижения.
4. Проверка на совпадение комбинации в игровом поле с выигрышными, при несовпадении переход к пункту 3.
5. Функция-поздравление.
6. Выход из игры.
Описание функций программы игры Пятнашки
create_field. Функция заполняет поле игровой матрицы А с помощью генератора случайных чисел. Исключает повторения и, при выпадении числа больше 15, заменяет его на 0 – пустое место в игровой доске.
print_field. Функция прорисовывает игровую доску с костями для передвижения. Построение происходит по нахождению координат числа в игровой матрице А.
siegn_test_up. Функция вызывается при нажатии клавиши “Вверх”. Ищет координаты «пустого места» в игровом поле. Фактически опускает 0 в матрице на одну строку ниже. При упоре в «стенку» игрового поля не производит никаких действий.
siegn_test_dn. Функция вызывается при нажатии клавиши “Вниз”. Ищет координаты «пустого места» в игровом поле. Фактически поднимает 0 в матрице на одну строку выше. При упоре в «стенку» игрового поля не производит никаких действий.
siegn_test_lf. Функция вызывается при нажатии клавиши “Лево”. Ищет координаты «пустого места» в игровом поле. Фактически передвигает 0 в матрице на один столбец вправо. При упоре в «стенку» игрового поля не производит никаких действий.
siegn_test_rt. Функция вызывается при нажатии клавиши “Право”. Ищет координаты «пустого места» в игровом поле. Фактически передвигает 0 в матрице на один столбец влево. При упоре в «стенку» игрового поля не производит никаких действий.
verification. Функция производит сравнение матрицы игрового поляс матрицами победных вариантов.
congratulens. Функция выводит на экран поздравления в случае победы игрока.
Теперь собственно программа игры Пятнашки на языке С