| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Ход конем |
| Автор: Darksquall 22.3.2004, 13:39 |
| Рассмотрим создание программы Обхода доски шахматным конем. Ход коня можно описать как перепрыгивание через клетку (фигуру) и движение на 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.Программу рекомендую запускать без режима вывода на экран,т.к. затормаживает обход. Прогу качаем с http://www.darklibr.narod.ru самораспаковывающийся архив. Удачи. |
| Автор: Alex101 22.3.2004, 16:46 |
| Для полной оптимизации надо заводить стоимости хода. Чем больше ходов возможо из клетки, тем выше ее стоимость. Программа (при очередном ходе) должна сначала пытаться пойти в клетку, стоимость которой минимальна. |
| Автор: Darksquall 22.3.2004, 17:19 |
| Да в принципе пробовал я на Athlone 2500 доска 8x8 заняла у меня 5 минут.Пока не оптимизировал алгоритм но про Правило Вансдорфа уже почитал.Главное что уже первая версия проги есть. |
| Автор: Alex101 22.3.2004, 18:58 | ||
Что-то долго... Посмотри, может где можно что ускорить. При простом бэктрекинге (без стоимостей) она должна минуты три-четыре считать на 386м... |
| Автор: Darksquall 23.3.2004, 10:03 |
| просто там в цикле несколько проверок.Т.к планирую делать не стандартные доски,Например в форме звезды или бублика :-) с четным количеством клеток |
| Автор: Darksquall 1.4.2004, 15:45 |
| Ура заработало быстрее,время отнимала application.processmessages и совместная обработка изображения.Я отделил графику от обработки |