Кратчайший путь передвижения короля по шахматному полю

Введение

Условие решаемой задачи дословно по заданию звучит следующим образом: «найти кратчайший путь передвижения короля по заданному клеточному полю, соединяющих два заданных поля доски»

Целью представленной работы является разработка приложения “Поиск кратчайшего пути”, которое создает шахматную доску, находит кратчайший путь передвижения короля и отображает его.

Перед началом вычисления пользователь должен указывать в программе следующую информацию:

- размерность поля

- установить слона на начальную позицию и указать конечную (при помощи мыши)

После этого программа должна показать кратчайший путь (пути) движения короля, выделяя его другим цветом.

Неформальная постановка задачи

Задачу ставит заказчик, а принимает разработчик. Между разработчиком и заказчиком должен состояться диалог, цель которого выяснить, одинаково ли они понимают задачу. Диалог может длиться день, месяц… В моей ситуации требуется написать программу, чтобы она могла найти кратчайший путь передвижения короля по заданному клеточному полю, соединяющих два заданных поля доски. Причём начальная и целевая клетки указываются при помощи мыши в запущенной программе.

Формальная постановка задачи

Разработка или поиск алгоритма решения задачи

Проект программы:

Задаём размер поля n.

Проверим, чтобы король и его местоположение должны находиться на полях одного цвета.

Образуем матрицу для расчёта пути размерности n+1.

С помощью полученной матрицы во избежание выхода за шахматное поле заполним окаймляющие элементы значениями false.

Выберем все возможные клетки, когда король из начального местоположения и точки назначения, используя ранее полученную матрицу.

Спецификация функций программы

В появившемся при вызове программы окне вводим размерность поля.

а) если мы вводим размерность поля меньше или больше указанного диапазона, то выводится сообщение

В главном окне отмечаем расположение короля и цели. Отметив на поле короля, мы делаем проверку, чтобы пользователь не мог отметить клетку-цель на поле, не совпадающее цвету, поля короля, а также на поле где расположен сам король.

Тем самым указываются все случаи, которые могут возникнуть при решении задачи на компьютере. Каждый такой случай оформляется как некоторая функция (в смысли достижения цели)