Опис алгоритму методу

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

Алгоритм програми

Зчитати розмірність дошки з клавіатури.
Виконати пункт 3 для верхньої лівої клітинки дошки для першого кроку.
Перейти в дану позицію та знайти клітинки в які можна перейти:
1. Якщо ще не знайдено розв’язок:
  1. Записати в дану позицію номер кроку коня
  2. Якщо всі клітинки пройдені, то розв’язок знайдений.
  3. Інакше, якщо ще не всі клітинки пройдені:
    1. Сформувати масив можливих переходів з даної позиції, для восьми варіантів:
      1. Якщо можна перейти на наступну клітинку -тим способом, то:
        
        Продивитися можливі переходи з наступної клітинки
        
        У разі можливого переходу, запам’ятати кількість цих переходів для цього варіанту.
    2. Спробувати виконати перехід для восьми варіантів ходу
      1. Для всіх варіантів переходу:
        
        Якщо з даної -того варіанту переходу можна зробити менше запам’ятованої кількості переходів то:
        
        Запам’ятати номер варіанту
        
        Запам’ятати кількість переходів для цього варіанту.
      2. Якщо в даному -му варіанті переходу можливо зробити більше переходів та даний варіант ще не відвіданий на цьому кроці, то:
        
        Виконати пункт 3 для позиції, в яку ми переходимо в даному -му варіанті для наступного кроку.
Якщо знайдений розв’язок вивести його на екран, інакше вивести повідомлення про відсутність розв’язку.

Відеокопії екрана

Аналіз достовірності результатів

З відео копій екрану за номерами кроків на клітинках шахової дошки видно, що програма знаходить правильний спосіб обходу шахової дошки, пройшовшись по кожній клітинці лише один раз.

Задача про лабіринт

Умова задачі [2]

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

Вхідні та вихідні тести

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