Рассмотрим создание программы Обхода доски шахматным конем.
Ход коня можно описать как перепрыгивание через клетку (фигуру)
и движение на 1 клетку в сторону.

Можем написать роцедуру заполняющая массив доступных
клеток на шахматной доске из текущей позиции goriz,vert.

procedure VozmojnieHodi(goriz:integer;vert:integer);
begin
VozmHodiVert[1]:=vert-1; //Записываем возможные ходы

для текущей клетки
VozmHodiGoriz[1]:=goriz-2;

VozmHodiVert[2]:=vert-2; //2
VozmHodiGoriz[2]:=goriz-1;

VozmHodiVert[3]:=vert-2; //3
VozmHodiGoriz[3]:=goriz+1;

VozmHodiVert[4]:=vert-1; //4
VozmHodiGoriz[4]:=goriz+2;

VozmHodiVert[5]:=vert+1; //5
VozmHodiGoriz[5]:=goriz-2;

VozmHodiVert[6]:=vert+2; //6
VozmHodiGoriz[6]:=goriz-1;

VozmHodiVert[7]:=vert+2; //7
VozmHodiGoriz[7]:=goriz+1;

VozmHodiVert[8]:=vert+1; //8
VozmHodiGoriz[8]:=goriz+2;
end;

Также необходимо учитывать размеры доски при переходе на следующую

клетку,т.к. можем
оказаться за пределами доски.
Затем последовательно ходим на доступные клетки,полученные из

VozmojnieHodi,одновременно
проверяем полученные координаты на доступность клетки(координаты

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

сама себя(рекурсия) и при каждом ходе определят доступные клетки

из текущей позиции.При выходе из процедуры пробуем пойти на

следующую доступную клетку на которой еще не были.Таким образом

перебирая последовательно все варианты клеток на доске,мы

приближаемся к решению задачи.Следует учесть что некоторые доски

не имеют решения:
Если произведение сторон доски нечетно и сумма координат

начальной позиции нечетна, то решения не существует также
не существует ни одного обхода при N, M < 3; N = 3, M = 5, 6; N =

M = 4;
имеется как минимум одна клетка, из которой возможен обход доски

при N = 3, M = 4; N = 3, M >= 7; N >= 4, M >= 5.Программу

рекомендую запускать без режима вывода на экран,т.к. затормаживает

обход.
Прогу качаем с
Ход конем
самораспаковывающийся архив.
Удачи.

Это сообщение отредактировал(а) Darksquall - 22.3.2004, 13:45

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

Это сообщение отредактировал(а) Alex101 - 22.3.2004, 16:55

Да в принципе пробовал я на Athlone 2500 доска 8x8 заняла у меня 5 минут.Пока не оптимизировал алгоритм но про Правило Вансдорфа уже почитал.Главное что уже первая версия проги есть.

Цитата(Darksquall @ 22.3.2004, 14:19)

Да в принципе пробовал я на Athlone 2500 доска 8x8 заняла у меня 5 минут.

Что-то долго...
Посмотри, может где можно что ускорить.
При простом бэктрекинге (без стоимостей) она должна минуты три-четыре считать на 386м...

просто там в цикле несколько проверок.Т.к планирую делать не стандартные доски,Например в форме звезды или бублика :-) с четным количеством клеток

Ура заработало быстрее,время отнимала application.processmessages и совместная обработка изображения.Я отделил графику от обработки