Пример за курсова работа Информатика-програмиране

УРАЛСКИ ДЪРЖАВЕН РУДЕНСКИ УНИВЕРСИТЕТ

Кон, обхождащ шахматната дъска

Изпълнено от: Таранова М.В.

Пример за програмата

Този интересен пъзел беше предложен от математика Ойлер. Задачата на пръв поглед е съвсем проста - имате нужда от шахматен рицар на произволен квадрат на шахматната дъска, за да заобиколите всички останали квадрати на дъската, чийто размер също е зададен произволно. В този случай една клетка може да бъде извървена само веднъж.

Конят, както знаете, ходи Г-образно. Тези. два квадрата във всяка посока (нагоре, надолу, надясно, наляво) и един квадрат в перпендикулярна посока. По този начин, с рицар, можете да направите максимум осем различни хода от даден квадрат (или по-малко, ако рицарят е на ръба на дъската).

За да се реши този проблем на компютър, е необходимо да се разработят правила, според които компютърът ще избере ход. По принцип следващият ход може да бъде избран произволно.

Оригинално правило, даващо линеен във времето алгоритъм за преминаване по дъската, е предложено от Warnsdorff през 1983 г. Приложих го в курсовата си работа.

Алгоритъмът е формулиран много просто: следващият рицарски ход трябва да бъде направен на площада, откъдето има най-малък брой възможни ходове. Ако има няколко клетки с еднакъв брой ходове, тогава можете да изберете всеки.

На практика това се прилага, например, както следва. Преди всеки ход на рицаря се изчислява рейтингът на най-близките налични квадрати - квадратите, на които рицарят все още не е бил и към които той може да се движи с едно движение. Рейтингът на дадено поле се определя от броя на най-близките полета, налични от него. Колкото по-нисък е рейтингът, толкова по-добър е той. След това се прави ход на полето с най-нисък рейтинг (на който и да е от тях, ако има няколко от тях) и така нататък, стига да има къде да отидете.

Евристиката винаги работи на дъски от 5x5 до 76x76 квадрата; при големи размери на дъската рицарят може да заседне. Освен това алгоритъмът, базиран на правила, не дава всички възможни решения (т.е. рицарски пътеки): можете да се противопоставите на правилото и пак да получите байпас, отговарящ на условието на проблема.

Има линеен алгоритъм за дъски с всякакъв размер, който разделя дъската на по-малки парчета, но поради изобилието от специални случаи е доста сложен и не толкова интересен като тази елегантна евристика.

Освен това бих искал да поясня как се извършва преместването. Вече казахме, че има осем възможни хода. Всички те са кодирани с числа от 0 до 7. На фиг. са показани всички възможни ходове.

Всеки ход може да бъде представен като движение на даден брой клетки хоризонтално и вертикално. Например, нулево движение съответства на движение на две клетки хоризонтално, а "-1" клетка вертикално (знакът минус посочва посоката на движение).

Попълването на масива за достъпност е малко по-сложно. Всеки от неговите елементи съответства на клетка на дъската, но тук записваме информация за това колко клетки можете да приличате на дадена. Например клетка A1 може да бъде подобна на две клетки (c2 и b3). Преди да започне да решава проблема, този масив има следната форма:

Пример за програмата

Диалог за създаване на шахматна дъска с рицар, на който избираме размера на полето, размера на клетката, позицията на рицаря и други параметри. Можете също да заредите изображения на елементи на дъската от файлове.

Създаден е квадрат 5х5, рицарят е в позиция 2х4. След като полето вече е създадено, можете да стартирате алгоритъма за преминаване по дъската с рицар.

Резултатът от обхождането на алгоритъма се вижда на дъската, цифрите показват реда на рицаря, прекосяващ дъската. Можете да изтриете реда на обхождане и да рестартирате алгоритъма. Можете също така да разхождате кон с помощта на стрелки и мишка.