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

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

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

Для вариантов пятнашек с большим, чем 15, количеством костяшек задача поиска кратчайшего решения является NP-полной

3. РАЗРАБОТКА ПРОЕКТА

Для разработки игры «Пятнашки» применялась среда визуального программирования Delphi 7. Проект программы состоит из двух окон (рисунок 2.1)

Рисунок 2.1 - рабочая зона проекта

Настраиваем форму: размер, цвет:

Сначала на форме располагается компонент TPanel со свойствами BevelInner и BevelOuter, равными bvLowered, для создания эффекта бордюра по краям формы. Затем на полученную панель ставится еще одна панель меньшего размера со свойством BevelOuter равным bvRaised, BevelInner --bvLowered, а цвет Color --clBlack. Эта вторая панель будет фоном для кнопок с цифрами. Затем добавляются кнопки (компоненты TButton или TSpeedButton) с названиями about, game, exit и кнопка начать игру (компонент TSpeedButton). Расположение их показано на рисунке. Теперь надо создать те самые квадратики с цифрами. Эту роль играют компоненты TButton. Расположите их на второй панели именно так, как показано на рисунке, то есть, кнопка с цифрой (Caption) 1 должна иметь имя (Name) Button1, кнопка 2 --Button2 и т.д. Это важно. Объясняю, почему. При добавлении компонента на форму он автоматически заносится в список (массив) компонентов формы и получает индекс начиная с 0. В дальнейшем взаимодействие с кнопками программой будет осуществляться через их индексы. Поэтому если у вас кнопка с именем Button1 будет иметь Caption 2, вам просто будет сложнее работать с ней. Что касается размеров кнопок, то я установил параметры Heigth и Width каждой по 50. Да, еще. Чтобы посмотреть индекс кнопки, размещенной на форме, в ее процедуре-обработчике события (Event), например, OnClick, наберите:

form1.caption:=inttostr((sender as tbutton).componentindex);

Это приведет к тому, что при нажатии на кнопку ее индекс будет выводиться в заголовке формы. Потом эту строчку можете удалить.

Рисунок 2.2 - форма с кнопками.

Теперь, когда интерфейс программы готов, можно перейти непосредственно к программированию. Опишем глобальные переменные модуля. В разделе var (там, где написано Form1: TForm1) напишите:

a:array[1..16]of byte;

i,k,fl,rn,p,m:byte;

x,y,x1,y1,num,pos,lr,td,lr1,td1:integer;

flag:boolean;

(назначение переменных я буду объяснять далее). После этого нужно написать процедуру, генерирующую массив случайных чисел от 1 до 16 так, чтобы они не повторялись. Потом по этому массиву будут расставляться кнопки с числами. Случайные числа будем заносить в массив a. Цифра 16 будет означать пустую область, на которой нет кнопки. Процедура заполнения массива случайными числами выглядит следующим образом:

procedure rndarr;

begin

for k:=1 to 16 do a[k]:=0;

randomize;

i:=1;

repeat

rn:=random(16)+1;

fl:=0;

k:=1;

while (a[k]<>rn) and (k<>17) do inc(k);

if k=17 then begin a[i]:=rn;

Inc(i);

end;

until i=17;

end;

Теперь делаем визуализацию массива. На этом принципе работают многие игры. Например, тот же тетрис: имеется некий двумерный массив (стакан), в котором нули -- пустые позиции, единицы -- квадратики, из которых строятся фигуры тетриса. Далее в массиве эти единицы сдвигаются, и массив выводится на экран с заменой 0 и 1 на графические элементы. Это повторяется несколько раз, что создает эффект падения фигур. В данном случае все должно происходить аналогичным образом: все перемещения производятся в массиве, а в соответствии числам из массива располагаются сами «пятнашки». Для того чтобы это осуществить, нужно написать процедуру, в которой читаются элементы массива, соответствующие индексам компонентов-кнопок с цифрами. Затем происходит обращение к этим кнопкам по их индексу и размещение их соответственно значениям в массиве. То есть, если первым элементом массива является число 15, то первой кнопкой в левом верхнем углу будет кнопка с цифрой 15 и т.д. Вот эта процедура:

procedure drawarr;

begin

p:=0;

for i:=0 to 3 do

for k:=0 to 3 do

begin

p:=p+1;

if a[p]<>16 then

begin

with TButton(form1.components[a[p]+5]) do

begin

left:=k*50+2;

top:=i*50+2;

end;

end;

end;

end;

Так как у меня первая кнопка в массиве компонентов формы имеет индекс 6, то я при обращении к кнопкам прибавляю к значению из массива число 5, чтобы получить их индексы:

Начнем работу с процедурами-обработчиками событий. Первая из них -- обработчик события OnClick кнопки (TSpeedButton) «Начать игру». Дважды щелкните по этой кнопке. При этом откроется редактор кода с таким заголовком процедуры:

procedure TForm1.SpeedButton2Click(Sender: TObject);

begin

rndarr;

drawarr;

form1.speedbutton2.caption:='Начать игру заново';

end;

Таким образом, при нажатии на кнопку «Начать игру» происходит генерация массива случайных чисел процедурой rndarr, затем -- размещение кнопок с цифрами соответственно числам в массиве процедурой drawarr и, наконец, изменение названия кнопки Начать игру на Начать игру заново.

Предпоследний этап. Нужно сделать так, чтобы при нажатии на кнопку с цифрой определялось направление ее движения, т.е. то место, где нет другой кнопки. Для этого клацните дважды, например, по кнопке 15 и в появившейся процедуре-обработчике события OnClick (как и в предыдущий раз) между Begin и End наберите:

if flag then exit; {если flag=true -- выход из процедуры}

pos:=0;m:=0;num:=0;

num:=(sender as tbutton).componentindex-5; {num -- номер нажатой кнопки}

for i:=1 to 16 do if a[i]=num then pos:=i; {определение ее позиции в массиве}

{определение направления движения}

if (pos-1>0)and(pos-1<>4)and(pos-1<>8)and(pos-1<>12)and(a[pos-1]=16)then m:=1;

if (pos+1<17)and(pos+1<>5)and(pos+1<>9)and(pos+1<>13)and(a[pos+1]=16)then m:=2;

if (pos-4>0)and(a[pos-4]=16)then m:=3;

if (pos+4<17)and(a[pos+4]=16)then m:=4;

if m=0 then exit; {если вокруг кнопки пустой позиции нет -- выход}

flag:=true; {установливаем флаг, означающий, что кнопка в движении}

lr1:=(sender as tbutton).left; {сохраняем в lr1 и td1 начальные координаты}

td1:=(sender as tbutton).top;

lr:=0;td:=0;

form1.move(sender); {вызов процедуры перемещения кнопки}

В Object Inspector в разделе Events для остальных кнопок с цифрами напротив события OnClick укажите эту процедуру. Таким образом, она будет выполняться при нажатии любой кнопки с цифрой. В этой процедуре определяется, есть ли рядом с нажатой кнопкой пустая позиция. Если таковая слева, то m:=1, справа --m:=2, сверху --m:=3, снизу --m:=4. Определение «слева или справа» происходит путем вычета или прибавления к позиции нажатой кнопки единицы, определение «сверху или снизу» -- через вычет или прибавление 4. Переменная Flag служит для того чтобы определить, движется ли какая-либо кнопка или нет. Если движется -- процедура не должна выполняться. Процедура перемещения кнопки form1.move описана далее.

Чтобы как-то «оживить» игру, требуется движение. В данном случае -- движение кнопок. Для реализации заметного человеческому глазу и более-менее плавного движения потребуется компонент TTimer. Выберите его из списка компонентов и расположите в любом месте формы. Установите его свойство Interval равным 1. Затем в его единственном событии OnTimer в Object Inspector напишите move и нажмите Enter. На экране появится тело процедуры-обработчика этого события:

procedure TForm1.move(Sender: TObject);

begin

timer1.enabled:=true; {включение таймера}

case m of {исходя из направления движения}

1:dec(lr,5); {уменьшаем на 5 lr}

2:inc(lr,5); {увеличиваем на 5 lr}

3:dec(td,5);

4:inc(td,5);

end;

with TButton(components[num+5])do begin {перемещаем компонент}

left:=lr1+lr;top:=td1+td;end;

if (abs(lr)=50) or (abs(td)=50) then {когда пройдено 50 шагов}

begin

timer1.enabled:=false; {выключаем таймер}

lr:=0;

td:=0;

flag:=false;

case m of {перестановка чисел в массиве}

1:begin a[pos-1]:=a[pos];a[pos]:=16;end;

2:begin a[pos+1]:=a[pos];a[pos]:=16;end;

3:begin a[pos-4]:=a[pos];a[pos]:=16;end;

4:begin a[pos+4]:=a[pos];a[pos]:=16;end;

end;

fl:=0;

for i:=1 to 16 do if a[i]<>i then fl:=1; {определяем, расставлены ли кнопки по порядку от 1 до 15}

if fl=0 then showmessage('Вы выиграли!'); {если кнопки расставлены как надо -- сообщение «Вы выиграли!»}

end;

end;

Основная часть программы уже написана. Осталось внести последние штрихи. Создайте форму AboutBox и в процедуре-обработчике события OnClick кнопки About напишите: AboutBox.Show. Аналогично, для кнопки Exit напишите Close -- для выхода из программы.

Далее компилируем и если правильно сделано, то программа запустится и будет вида:

Рисунок 2.3 - Игра «Пятнашки»

ЗАКЛЮЧЕНИЕ

ГЛОССАРИЙ

№ п/п Понятие Определение

1. Команды - сообщения, с помощью которых реализуется процесс управления ходом диалога

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

3. Объектно-ориентированное программирование - это методика создания программ, в основе которой лежит понятия объектов и классов

4. Ошибка - сообщение о прерывании выполнения программного кода, невозможность обработки входных данных пользователя

5. Проект - совокупность файлов форм, файлов настройки, файлов программного кода, участвующих в разработке программного обеспечения

6. Процедура - подпрограмма, которая необходима для выполнения конкретной задачи или подзадачи

7. Синтаксис - построение программы на языке программирования

8. Тестирование программы - комплекс мероприятий, направленных на выявление ошибок в функционировании программ

9. Форма - окно программы на стадии ее разработки

10. Файл проекта - файл, который создается автоматически, связывая все файлы программы и код инициализации

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

Размещено на Allbest.ru