Еврістичне створення головоломки

Еврістичне створення головоломки

32

КУРСОВА РОБОТА

на тему: «Еврістичне створення головоломки»

• Вступ
• Темою курсового проекту є «Еврістичне створення головоломки».
• Евристика (грец. heurisko - знаходжу, відшукую, відкриваю) - наука, яка вивчає творчу діяльність, методи, які використовуються у відкритті нового і в навчанні. Евристичні методи (друга назва Евристики) дозволяють пришвидшити процес вирішення задачі. Значний інтерес до їх дослідження виник у звязку з можливістю вирішення ряду задач (розпізнавання обєктів, доведення теорем і т.д.), в яких людина не може дати точний алгоритм вирішення, з допомогою технічних засобів. Метою Евристики є побудова моделей процесу вирішення якої-небудь нової задачі.
• Існують наступні типи моделей:
• 1. модель сліпого пошуку, яка спирається на так званий метод проб і помилок;
• 2. лабіринтна модель, в якій вирішувана розглядається як лабіринт, а процес пошуку рішення - як прохід по лабіринту;
• 3. структурно-семантична модель, яка рахується на даний час найбільш повною і яка відображає семантичні відношення між обєктами, які складають область задачі.
• Евристика повязана з психологією, фізіологією вищої нервової діяльностю, кібернетикою і т.д.
• Найпершою задачею еврістичного пошуку була головоломка, яка передбачала пересування гральних фішок по горизонталі або вертикалі на порожню ділянку до тих пір, доки отримана конфігурація не буде відповідати цільовій конфігурації.
• Програма, виконана у курсовій роботі, є комп'ютерною версією відомої «П'ятнашки». Це логічно нескладна і достатньо проста у керуванні і використанні програма.
• Актуальність теми полягає у тому, що на сьогоднішній день комп'ютер став досить важливою частиною життя суспільства, а комп'ютерні ігри набувають більшого поширення.
• Метою курсової роботи є поглиблення знань і розширення навиків по розробці алгоритмів та їх реалізації на персональному комп'ютері. Вона виконана в середовищі Турбо Паскаль з використанням графічних можливостей мови у роботі із масивами і графікою.

Пятнашки - популярна головоломка, що являє собою набір однакових квадратних кісточок з нанесеними числами, ув'язнених у квадратну коробку.

Суть самої гри полягає в наступному:

Гравець на екрані бачить табло, яке розбито на 16 кліток. У п'ятнадцяти з них розташовані неповторювані цифри, у випадковому порядку від 1 до 15 і одна порожня.

У загальному виді дане табло можна представити у вигляді таблиці 1:

Таблиця 1. Зразок табло

Гравець повинен переміщати по одній клітинці із цифрою на порожнє місце.

Так відбувається доти, доки користувач не вибудує послідовну комбінацію цифр (Таблиця 2), і лише після цього гравець уважається переможцем.

Таблиця 2. Правильне заповнення табло

Для розробки програми потрібно врахувати необхідність створення ігрового табло в графічному вигляді, розподілу його на необхідну кількість осередків, заповнення табло випадковими числами, розробку способу управління.

2. Проектування

2.1 Розробка функціональної схеми

Незважаючи на простоту даної програми, написання алгоритму виявилося досить не простим завданням. У зв'язку із цим довелося розділити його, з метою його читаності й доступності.

Основний алгоритм програми розбитий на два розділи;

1. Керування;

2. Гра;

Рис. 2.1.1. Функціональна схема

1. Ініціалізація графічного режиму;

2. Заповнення в пам'яті комп'ютера табло випадковими цифрами;

3. Вивід табло на екран;

4. Уведення напрямку переходу;

5. Пошук порожнього елемента;

6. Переміщення елементів табло;

7. Вихід з режиму гри:

У програмі використовуються наступні вхідні дані (див. табл. 2.1.1.).

Таблиця 2.1.1. Імена та типи даних

Алгоритм даної гри (Рис. 2.2.1. Алгоритм гри.) реалізований за допомогою процедури Game15 і полягає в наступному:

Ініціалізація графічного режиму;

Заповнення в пам'яті комп'ютера табло випадковими цифрами;

Виведення табло на екран;

Введення напряму переходу;

Пошук порожнього елементу;

Переміщення елементів табло;

Вихід з режиму гри;

Схематично, даний алгоритм виглядає наступним чином:

Рис. 2.2.1. Алгоритм гри

1) Ініціалізація графічного режиму

Ініціалізація графічного режиму здійснюється в процедурі Game15. Перехід до графічного режиму здійснюється, за допомогою процедури Initgraph (grdriver, grmode, grpath), де grdriver - це використовувані програмою драйвер відеоадаптера (VGA), grmode - режим роботи відеосистеми (Vgahi), grpath - це місце знаходження файлу EGAVGA.BGI на диску (як і у випадку з файлами, пишемо тільки ім'я й розширення файлу, а не повний шлях, для того щоб у майбутньому можна було переміщати файли програми).

2) Заповнення табло випадковими числами

У пам'яті комп'ютера створюється табло, в якому, надалі проводитимуться перестановки. Табло складається з 16 (4 рядки і 4 три стовпці), яке заповнюється п'ятнадцятьма, цифрами, що не повторюються, від 1 до 15 і однією порожньою кліткою.

Даний розділ реалізований за допомогою процедури Tablo. Фактично табло, яке описується раніше це двовимірний масив з цифрами від 1 до 15 і порожня клітинка.

Наступному моментом реалізації даної процедури, є заповнення табло випадковими цифрами. Для заповнення табло випадковими цифрами використовується функція random, яка є генератором випадкових цифр, але працює відповідно тільки з цифрами, а у нас рядковий двовимірний масив.

Проаналізувавши вище сказане, приходимо до того, що необхідно створити два масиви. Один одномірний із шістнадцяти елементів типу integer, другий двовимірний, чотири на чотири, типу string. Спочатку одномірний масив, у випадковому порядку, заповнюється цілими неповторюваними цифрами від 1 до 16, а потім залежно від розташування цифр, заповнюється двовимірний строковий масив. ПРИМІРОМ, якщо перший елемент одномірного масиву дорівнює цифрі 11 тоді першому елементу двовимірного масиву буде привласнено рядок «11».

Загальний алгоритм (Рис. 2.2.2. Алгоритм заповнення табло випадковими числами.) полягає в наступному:

Вибір випадкового числа;

Перевірка на наявність збігів в масиві;

Заповнення двовимірного масиву;

Рис. 2.2.2. Алгоритм заповнення табло випадковими числами

Вибір випадкового числа;

Деякій змінній b привласнюється випадкове число, за допомогою функції random. При чому функція random обмежена інтервалом від 1 до 16.

Перевірка, чи є співпадання;

Змінна b порівнюється з кожним елементом масиву bs[і], за допомогою інструкцій For і if. Якщо такий елемент уже присутній в одномірному масиві, тоді змінної b, знову привласнюється випадкове число. Так відбувається доти, поки змінної b не буде привласнена цифра, якої ще немає в масиві.

- Занесення інформації в масив.

Значення змінної b, яке було знайдено раніше, вноситься в масив bs[і], за останнім елементом внесений у масив

- Перевірка чи заповнений масив.

Програма перевіряє чи заповнений масив повністю, якщо ні, те алгоритм повертається.

У підсумку ми маємо одномірний масив заповнений, у випадковому порядку неповторюваному цифрами від 1 до 16.

- Заповнення двовимірного масиву.

Заповнення двовимірного масиву, за допомогою інструкції For і змінних і й j, які позначають стовпець і рядок.

Алгоритм заповнення двовимірного масиву полягає в наступному:

- Спочатку змінної z привласнюється одиниця. Дана змінна нам необхідна як лічильник.

- Кожному елементу j рядка й і стовпця привласнюється строковий елемент, залежно від цифри вартої під номером z в одномірному масиві, якщо поточної елемент одномірного масиву містить цифру 8, те поточному елементу двовимірного масиву привласнюється строковий елемент «8». Виключенням становить цифра 16. У цьому випадку у двовимірний масив уводиться пробіл. Вибір строкового елемента здійснюється за допомогою інструкції case.

- Так відбувається доти, поки двовимірний масив не буде повністю заповнений.

3) Виведення табло.

У даному розділі на екрані з'являється табло з поточною комбінацією цифр. Спочатку, табло заповнюється випадковим чином, а надалі на екрані буде відображено поточне перебування цифр на табло, залежно від зроблених користувачем ходів.

Даний розділ реалізований в процедурі Vivod.

Загальний алгоритм (Рис. 2.2.3. Алгоритм виведення табло.) даного розділу полягає в наступному:

- Промальовування клітинок;

- Промальовування рамки;

- Виведення елементів масиву зверху клітинок табло;

Рис. 2.2.3. Алгоритм виведення табло

Промальовування клітинок;

Малювання кліток здійснюється в наступному порядку:

2) Визначення розміру майбутніх кліток, за допомогою двох змінні (h1, w1, координати верхньої лівої й правої нижньої крапок);

3) За допомогою процедури Setfillstyle, задаємо потрібний колір і стиль заповнення. Колір виберемо синій, а стиль заповнення поберемо Solidfill - суцільне заливання поточному кольором, тобто синім.

4) За допомогою процедури Bar вичерчуємо на екрані квадрат.

5) Щоб дані дії не повторювати 16 раз, використовуємо інструкцію For.

Промальовування рамки;

Для того, щоб табло мало закінчений вигляд, помістимо раніше створені клітинки в рамку, за допомогою процедури Line.

Виведення елементів масиву на клітинках табло;

У підсумку на екрані з'являється табло із шістнадцятьома клітками, залишається лише в центр цих кліток помістити цифри із двовимірного масиву.

Тому що ми перебуваємо в графічному режимі, то для висновку елементів двовимірного масиву використовуємо процедуру Outtextxy.

У підсумку на екрані з'явиться досить акуратне й не погано оформлене табло із клітками, у центрі кожної з яких, перебуває цифра.

У майбутньому, коли користувач буде переміщати клітки, він фактично буде робити операції з масивом і на екран буде виводитися інформація з масиву, у якім здійснена перестановка, а клітки залишаться незмінними.

4) Пошук порожнього елементу.

У даному розділі здійснюється пошук порожнього елементу, щоб надалі відносно його можна було б здійснювати пересування

Даний розділ реалізований в процедурі Poisk. Програма за допомогою інструкції For і змінних i і j порівнює кожен елемент двовимірного масиву AS, з порожнім елементом, за допомогою інструкції IF і коли знаходить, привласнює значення змінних i і j змінним strok і stolb. Таким чином, змінні strok і stolb як би є координатами порожнього елементу.

Загальний алгоритм (Рис. 2.2.4. Алгоритм пошуку порожнього елементу.) даного розділу полягає в наступному:

- Вибір елементу масиву;

- Перевірка, чи є даний елемент пропуском;

Привласнення координат рядка і стовпця змінним;

Рис. 2.2.4. Алгоритм пошуку порожнього елементу

Вибір елементу масиву;

За допомогою інструкції For по черзі вибиратимемо кожен елемент масиву.

Перевірка, чи є елемент порожньою коміркою;

За допомогою інструкції If, порівнюємо кожен елемент масиву з пропуском.

Запам'ятовування координат порожньої комірки;

Змінним strok і Stolb привласнюємо координати порожнього елементу.

5) Введення напряму переходу.

У даному розділі користувачеві пропонується вибрати напрям переходу кліток з цифрами, щодо порожньої клітки. Вибір здійснюється за допомогою курсору, на клавіатурі.

Даний розділ алгоритму реалізований в процедурі Napravlenie.

Фактично деякою змінною ch (типу char) привласнюється код натиснутої клавіші.

Алгоритм процедури полягає в наступному:

- Користувачеві пропонується, за допомогою курсору, ввести напрями переходу.

- Після того, як користувач, натиснув кнопку на клавіатурі, код клавіші привласнюється змінною ch, за допомогою функції readkey [3];

Наприклад, якщо користувач ввів напрям курсору вгору, це означає, що користувач натиснув службову клавішу під кодом 72.

6) Переміщення елементів табло

У даному розділі, залежно від напряму переходу, вибраного раніше за допомогою курсору, і розташування порожньої клітинки, відбувається переміщення:

Стрілка вліво - переміщає вліво цифру, що стоїть праворуч від порожньої клітинки;

Стрілка управо - переміщає управо цифру що стоїть зліва від порожньої клітинки;

Стрілка вниз - переміщає вниз цифру що стоїть зверху від порожньої клітинки;

Стрілка вгору - переміщає вгору цифру що стоїть знизу від порожньої клітинки.

Загальний алгоритм (Рис. 2.2.5. Алгоритм переміщення елементів табло.) реалізований в процедурі Zamena і полягає в наступному:

Вибір напряму перестановки;

Переміщення клітинок;

Рис. 2.2.5. Алгоритм переміщення елементів табло

Вибір напряму перестановки;

Коли користувач робить хід, він натискає службову клавішу, що кодується під певним номером. За допомогою інструкції IF і функції ord, вибирається напрями перестановки елементів.

Переміщення клітинок;

Залежно від значень змінних Strok, Stolb, яким було привласнено координати порожнього елементу в масиві і вибраного напряму, здійснюється переміщення.

Наприклад, користувач ввів напрям курсору вгору, це означає, що користувач натиснув службову клавішу під кодом 72, тоді, за допомогою інструкції if і функції ord (if ord(ch)=72 then), здійснюється переміщення.

Переміщення здійснюється за наступним принципом: порожньої клітинки, а саме елементу масиву з координатами as [strok, stolb], привласнюється вміст елементу що стоїть під порожньою клітинкою (as [strok, stolb]:= as [strok+1, stolb];), а відповідно елементу, що стоїть під порожньою клітинкою привласнюється пропуск (as [strok+1, stolb]:=' ';).

3. Програмування

Для написання програми знадобилося використання декількох програм і функцій стандартних модулів (див. Табл. 3.1.). Також для зручності текст програми був розбитий на декілька окремих дій, оформлених у вигляді процедур (див. табл. 3.2.)

Таблиця 3.1. Використані стандартні процедури та функції

32

Таблиця 3.2. Підпрограми користувача

Додаток А

Інструкція користувача

Дана програма-головоломка призначена для розвитку логічного мислення користувача, а також для використання у якості розважальної гри.

Для запуску гри досить будь-якого комп'ютера, на якім установлена хоч яка-небудь операційна система, сімейство Windows.

Управління у програмі відбувається за допомогою клавіш курсору, а також клавіш END та ESC.

Після того, як гру розпочато, користувачеві пропонується гральне поле (Рис. А.1. Гральне поле), що складається з авторських даних, деяких вказівок щодо керування і грального поля

Рис. А.1. Гральне поле

Користувачеві необхідно за допомогою курсору переміщати клітки табло, до тих пір, поки на екрані не відобразиться, послідовна комбінація цифр. (Рис. А.2 Гральне поле)

Рис. А.2 Гральне поле

Протягом усієї гри, користувач у будь-який момент може покинути гру, для цього досить натиснути клавішу ESC і гра завершує свою роботу.

Додаток Б

Текст програми

15.pas

{*************************************************************}

{*kyrsova robota na temu 'Evristuchne stvorennja golovolomku»*}

{*Vukonav stydent grypu KSM-09-2 *}

{* Levenec* Artem *}

{*************************************************************}

program Game;

uses crt, Graph;

var

as:array [1.. 4,1..4] of string; {Двухмерный массив, содержит элементы табло}

bs:array [1..16] of integer;

hod:integer;

i, j:integer; {Переменные для работы с массивами}

strok, stolb:integer; {Координаты пустого элемента}

ch:char; {Переменная, которой присваивается код нажатой клавиши на клавиатуре}

procedure Vivod;

{Процедура вывода на экран табло с цифрами сформированное на момент отображения}

var lx, ly:integer; {Координаты вывода двухмерного массива}

x, y:integer; {Координаты клеток}

j1, i1:integer; {Переменные счетчики, для рисование клеток}

w1, h1:integer; {Ширина и высота клеток}

begin

OutTextXY (70,10,'*************************************************************');

OutTextXY (70,20,'*Kyrsova robota na temy, Evristuchne stvotennja golovolomku,*');

OutTextXY (70,30,'* Vukonav stydent grypu KSM-09-2 *');

OutTextXY (70,40,'* Levenec* Artem *'); OutTextXY (70,50,'*************************************************************');

OutTextXY (210,90,'For leaving press ESC');

OutTextXY (180,100,'Dlja zavershennya natusnit END');

w1:=30;

h1:=30; {Клетка размером 30 на 30}

for i1:=0 to 3 do {Цикл, прорисовки клеток}

for j1:=0 to 3 do

begin

x:=235+j1*35; {Сдвиг клеток по х}

y:=150+i1*35; {Сдвиг клеток по у}

setFillStyle (1,1); {Цвет и стиль клеток, цвет синий, стиль заполнение текущем цветом}

Bar (x, y, x+w1, y+h1); {Рисование клетки}

end;

lx:=245;

ly:=162;

for i:=1 to 4 do {Цикл вывода двухмерного массива по вверх клеток}

begin

for j:=1 to 4 do

begin

OutTextXY (lx, ly, as [i, j]); {Вывод текста на экран}

lx:=lx+35;

end;

lx:=245;

ly:=ly+35;

end;

line (220,135,220,300); {Рисование рамки}

line (385,135,385,300);

line (220,135,385,135);

line (220,300,385,300);

end;

procedure Tablo;

{Формирование табло при первом запуске заполненное случайными и неповторяющимися цифрами}

var b:integer; {Переменная, которой присваивается случайное число}

k, z:integer; {Счетчики для операций с массивами}

begin

randomize;

For z:=1 to 16 do

begin

b:=random(15); {Выбор случайного числа}

k:=1;

while k<>17 do {Цикл пока не будет заполнен массив с целыми цифрами}

begin

if bs[k]=b then

begin

b:=random(17);

k:=1;

end

else k:=k+1;

end;

bs[z]:=b; {Присвоение очередного неповторяющегося элемента массива}

end;

z:=1;

for i:=1 to 4 do {Заполнение двухмерного массива, вместо цифр из одномерного, присваиваются строковые элементы}

begin

for j:=1 to 4 do

begin

case bs[z] of

1: as [i, j]:='1 ';

2: as [i, j]:='2 ';

3: as [i, j]:='3 ';

4: as [i, j]:='4 ';

5: as [i, j]:='5 ';

6: as [i, j]:='6 ';

7: as [i, j]:='7 ';

8: as [i, j]:='8 ';

9: as [i, j]:='9 ';

10: as [i, j]:='10';

11: as [i, j]:='11';

12: as [i, j]:='12';

13: as [i, j]:='13';

14: as [i, j]:='14';

15: as [i, j]:='15';

16: as [i, j]:=' ';

end;

z:=z+1;

end;

end;

vivod; {Вывод табло на экран}

end;

Procedure Poisk;

{Поиск пустого элемента в табло}

begin

for i:=1 to 4 do

begin

for j:=1 to 4 do

begin

if as [i, j] = ' ' Then {Поиск, равен ли текущий элемент пробелу}

begin

Strok:=i; {Если равен, то присваиваются координаты пустого элемента}

Stolb:=J

end;

end;

end;

end;

procedure bonus;

{Бонус, для проверки. При нажатии клавиши END на клавиатуре расклад собирается}

begin

as [1,1]:='1 '; as [1,2]:='2 '; as [1,3]:='3 '; as [1,4]:='4 ';

as [2,1]:='5 '; as [2,2]:='6 '; as [2,3]:='7 '; as [2,4]:='8 ';

as [3,1]:='9 '; as [3,2]:='10'; as [3,3]:='11'; as [3,4]:='12';

as [4,1]:='13'; as [4,2]:='14'; as [4,4]:='15'; as [4,3]:=' ';

Strok:=4; Stolb:=3;

end;

procedure napravlenie;

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

begin

ch:=readkey; {Переменной присваивается код нажатой пользователем клавиши на клавиатуре}

end;

procedure Zamena;

{Передвижение клеток с цифрами в зависимости от выбора пользователя}

begin

napravlenie; {Процедура, ввод направления перехода}

if ord (ch)=79 then bonus; {Если нажата клавиша END на клавиатуре то расклад сам собирается}

if ord(ch)=75 then {Если нажата клавиша влево}

begin

if stolb<>4 then {Если это не последний элемент, стоящий у границы табло}

begin

as [strok, stolb]:=as [strok, stolb+1]; {На место пустого элемента присваивается элемент стоящий справа от пустого}

as [strok, stolb+1]:=' '; {Элементу стоящему справа от пустого присваивается пустой элемент}

stolb:=stolb+1; {Новая координата пустого элемента}

hod:=hod+1; {Очередной сделанный ход}

end;

end;

if ord(ch)=72 then {Если нажата клавиша вверх}

begin

if strok<>4 then {Если это не последний элемент, стоящий у границы табло}

begin

as [strok, stolb]:=as [strok+1, stolb]; {На место пустого элемента присваевается элемент стоящий снизу от пустого}

as [strok+1, stolb]:=' '; {Элементу стоящему снизу от пустого присваевается пустой элемент}

strok:=strok+1; {Новая координата пустого элемента}

hod:=hod+1; {Очередной сделанный ход}

end;

end;

if ord(ch)=77 then {Если нажата клавиша вправо}

begin

if stolb<>1 then {Если это не последний элемент, стоящий у границы табло}

begin

as [strok, stolb]:=as [strok, stolb-1]; {На место пустого элемента присваивается элемент стоящий слева от пустого}

as [strok, stolb-1]:=' '; {Элементу стоящему слева от пустого присваивается пустой элемент}

stolb:=stolb-1; {Новая координата пустого элемента}

hod:=hod+1; {Очередной сделанный ход}

end;

end;

if ord(ch)= 80 then {Если нажата клавиша вниз}

begin

if strok<>1 then {Если это не последний элемент, стоящий у границы табло}

begin

as [strok, stolb]:=as [strok-1, stolb]; {На место пустого элемента присваивается элемент стоящий сверху от пустого}

as [strok-1, stolb]:=' '; {Элементу стоящему сверху от пустого присваивается пустой элемент}

strok:=strok-1; {Новая координата пустого элемента}

hod:=hod+1; {Очередной сделанный ход}

end;

end;

Vivod;

end;

procedure Game15;

{Подключение графики и переход в режим ИГРЫ}

var grMode:integer; {Режим работы видеосистемы}

grPath:string; {Путь к файлу}

grDriver:integer; {Используемый программой драйвер видеоадаптера}

begin

hod:=0;

grDriver:=VGA;

grmode:=VGAHi;

grPath:='EGAVGA.BGI';

initGraph (grDriver, grMode, grPath); {Инициализация графического режима}

Tablo; {Формирование табло}

Poisk; {Поиск пустого элемента}

repeat {Цикл, пока не нажата клавиша ESC или пока игрок не победил играть}

Zamena; {Передвижение в массиве}

until (ord (ch)=27);

closeGraph; {Закрытие графического режима}

end;

begin

repeat {Цикл, доки не натиснута клавіша ESC}

Game15; {Виклик процедури переходу у режим гри}

until ord(ch)=27

end.

Висновок