Шахматы и лошади...

Вот у меня есть задачка, которая мучает мя долго и нудно. Значит так. Представте себе шахматную доску. В любой ее клетке стоит конь, знаете такой, буквой "Г" ходит?
Задача: пройти все клетки, этим самым Г без попадания на одну клетку дважды. Если кто знает КАК это сделать, особенно на VB or Pascal or C++ or Assembler -                H-E-E-E-LP!!!

по моему, задача решается оплным перебором +метод отсечения чего-то (ветвей и границ что-ли)

проще всего реализовать рекурсией.
то есть пишешь функцию, которая получает координаты клетки, в которой стоит конь. пытается его двинуть каждым и з возможных способов, так чтобыне выйти за пределы сетки и не попасть в уже обойденные клетки (надо хранить массив, в котором помнить, в каких клетках были)
на каждый удачный способ движения вызывает себя для этой клетки
если двигаться некуда, то если вся доска не обойдена, отмечаем текущую клетку как не обойденную и возвращаемся (на предыдущй уровень рекурсии)
если ходить некуда и вся доска обойденна, то кричим УРА и выходим. (надо выйти только из всех вызовов рекурсивных функций. то есть надо написать нашу функцию так, что при вызове ее из себя если она возвращает например 3, то немедленнно выходить,не пробуя другие варианты ходов.

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

ЗЫ можно по ходу вызовов заносить коориднаты очередной клетки в некий глобальный массив, чтобы когда выйдем, был путь обхода. а если функция дя очередной клетки возвращается, никуда не походив, то вытираем из массива текущую клетку (саму последнюю).
ЗЗЫ немножко путанно, но надеюсь поймешь:)
ЗЗЗЫ сам реализуешь?

Сообщение отредактировано: Demo_S - 16.06.02, 21:19

Уважаемый DEMO_S!!! Большое спасибо за Ваше участие в решении моей проблемы. Вы меня прям несказанно просветили. Но боюсь не смогу сам реализовать Вашу идею. Не могли бы помочь конкретным примером? enstain@yandex.ru с удовольствием примет Ваш вариант решения.

Цитата Enstain, 17.06.02, 00:54:56

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

типа сарказм:)))
ладно, завтра жди... экзамены...\%)

Задача решается никак не методом перебора. Любой код коня делается следующим образом:
1. Выбираем варианты куда коняка может пойти
2. Находим среди этих вариантов тот, из которого у коняки меньше всего вариантов дальнейшего хода.
3. Идем на найденную в 2. клетку. Если таких клеток несколько - выбираем любую.
Вот и все  ;D ;D ;D

Сообщение отредактировано: GrAnd - 17.06.02, 03:59

Завтра выложу решение на С и Паскале

Кстати данная задачка уже решалась и даже в этом разделе
http://pascal.sources.ru/cgi-bin/forum/YaB...;num=1017416513

Цитата

Задача решается никак не методом перебора

ну-да, расскажи:))
не спорю, его можно оптимизировать, но он был и останется перебором:)))
потому как, ты можешь зайтив тупик и все...

хотя судя по твоему алгоритму, это больше похоже на прикол:))

ксати, ты ссылка, что ты тдал - то что надо:))
я теперь не буду напрягаться, писать:) только вот там для надежности нужно все же вызывать данную процедурку для каждой клетки, если интересует возможность обхода в принципе, тк  не факт, что из клетки 1:1 можно построить  такой обход:)

На самом деле это действительный гарантированный алгоритм обхода. Алгоритм довольно известный и немного староват. Что же касается окончательного результата, то существует бесконечное количество досок размером (mxn), для которых это невозможно. Простейший пример доска 3х3. Для большей освещенности предлагаю почитать книги Гардера и Лойда

хм, я вот тут подумал, действительно, если существует обход, то пофиг, с ккой клетки начинать, так что проверки дял всех клетокне требуется (хотя если сделать, все равно медленнее не будет:) )
но вот остальное, вес равно перебор:)
про книги: в инете есть? дай ссылку:))

По поводу инета не знаю, но они выпускались издетельством "Диалог-Наука". А  так поищи по поисковикам. Книги шикарные - целая куча головоломок, задач, игр и их решений. ;D ;D ;D

Цитата GrAnd, 17.06.02, 07:59:28

Задача решается никак не методом перебора. Любой код коня делается следующим образом:
1. Выбираем варианты куда коняка может пойти
2. Находим среди этих вариантов тот, из которого у коняки меньше всего вариантов дальнейшего хода.
3. Идем на найденную в 2. клетку. Если таких клеток несколько - выбираем любую.
Вот и все  ;D ;D ;D

Я вот придумал немного другой алгоритм. Давным давно Даже программер на Прологе пивом прставлялся ;D ;D ;D после того, как я его на Пасквиле уделал. Хотя, сознаюсь, приведенный ниже алгоритм хорошо себя "чувствует", когда приходится "работать" на более-менее равносторонних матрицах Например, квадратную матрицу 20х20 с угла данный алгоритм заполняет на 400 шагов и без возвратов! На других, типа 10х10 есть немного возвроатов. Короче критикуйте

Программу написал на Virtual Pascal'е, но можно компильнуть и на BP, правда не помню есть ли там однострочные комментарии, ну или на Ц "перевести". Кстати интересно будет узнать как уважаемый All уловит суть алгоритма по этой проге Може еще и сравните с Вашими

<br>Program CrazyHorse;<br><br>////////////////////////////////////////////////<br>// Copyleft (L) 2002 by O.Melnikov            //<br>// ------------------------------------------ //<br>// (aka JoeUser on http://pascal.sources.ru/) //<br>////////////////////////////////////////////////<br><br>Uses<br>  Crt, VpUtils;<br><br>Type<br>  DotArray  = array[0..1] of Char;<br>  Point     = record X,Y: Integer end;<br><br>Const<br>  M = 20;<br>  N = 20;<br>  B : DotArray = ('.','*');<br>  F : Boolean = False;<br>  V : array[1..8,1..2] of Integer = ((1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2));<br>  T : Integer = M*N;<br>  Z : Integer = SizeOf(Point);<br>  C : Integer = 0;<br>  X : Integer = 0;<br><br>Var<br>  I,J   : Integer;<br>  Gc,Gx : Integer;<br>  Md,Nd : Integer;<br>  P : array[1..M,1..N] of Byte;<br>  W : Point;<br><br>Procedure Paint(I,J,K: Integer);<br>begin<br> // рисование шага<br> GotoXY(J,I);<br> Write(B[K]);<br>end;<br><br>Function Step(I,J: Integer): Boolean;<br> var<br>   S     : array[1..8] of Point;<br>   R     : array[1..8] of Point;<br>   A,B   : Integer;<br>   L     : Integer;<br>   K     : Integer;<br>begin<br>  //Delay(200);<br><br>  // начальная прорисовка и инициализация шага<br>  Inc(X);<br>  Inc(C);<br>  Result:=False;<br>  P[I,J]:=1;<br>  Paint(I,J,P[I,J]);<br><br>  // строим вектор возможных перемещений<br>  for A:=1 to 8 do with S[A] do begin X:=J+V[A][1]; Y:=I+V[A][2] end;<br><br>  // "оцениваем позицию" и выбираем текущую "тактику"<br>  if (I  < Md) and (J  < Nd) then K:=7 else<br>  if (I  < Md) and (J >= Nd) then K:=1 else<br>  if (I >= Md) and (J >= Nd) then K:=3 else K:=5;<br><br>  //строим вектор перебора в зависимости от выбранной тактики<br>  L:=0;<br>  for A:=1 to 8 do with S[K] do begin<br>    // проверяем возможность хода (пpеделы "доски") и незанятость "клетки"<br>    if (X>0) and (Y>0) and (X<=N) and (Y<=M) and (P[Y,X]=0) then begin<br>      Inc(L);<br>      Move(S[K],R[L],Z)<br>    end;<br>    Inc(K);<br>    if (K > 8) then K:=1;<br>  end;<br><br>  if (L>0) then begin<br>    // итого нашли L возможных прыжков, соpтиpуем их их на дальность от центpа<br>    // это так попытка дооптимизировать - но получается, увы еще хуже<br>    // однако на одном из полей позволила сэкономить около 60\%  возвратов<br>    // Короче,здесь можно еще чего-то попробовать сделать<br>    {<br>    for A:=1 to L do for B:=A+1 to L do if Max(Abs(R[A].X-Md),Abs(R[A].Y-Nd)) > Max(Abs(R[B].X-Md),Abs(R[B].Y-Nd)) then begin<br>      Move(R[A],W,Z);<br>      Move(R[B],R[A],Z);<br>      Move(W,R[B],Z);<br>    end;<br>    }<br>    // итого нашли L возможных прыжков, пробуем их<br>    for A:=1 to L do if Step(R[A].Y,R[A].X) then begin<br>      Result:=True;<br>      Break;<br>    end;<br>  end else Result:=(C=T);<br><br>  // если эта ветка разбора неудачная - "убираем" ход из этой клетки<br>  if (not Result) then begin<br>     P[I,J]:=0;<br>     Dec(C);<br>     Paint(I,J,P[I,J]);<br>  end<br>end;<br><br>Begin<br> // Инициализация пустой доски................................................<br> FillChar(P,SizeOf(P),0);<br> Md := M shr 1;<br> Nd := N shr 1;<br> // Рисование поля............................................................<br> for I:=1 to M do for J:=1 to N do Paint(I,J,0);<br> // Заполнение................................................................<br> F:=Step(1,1);<br> // Отчет о работе............................................................<br> GotoXY(1,M+2);<br> if (F) then begin<br>   WriteLn('Доска заполнена');<br>   WriteLn('==================================================================');<br>   Writeln(' * клеток    : ',T);<br>   WriteLn(' * пpыжков   : ',X);<br>   Writeln(' * возвpатов : ',X-T);<br> end else WriteLn('Доску заполнить не получается');<br> // End of story..............................................................<br> ReadKey; while (KeyPressed) do ReadKey;<br>End.<br>

Так это все по поводу один раз обойти все клетки и остановиться неизвестно в какой. А если надо вернуться в исходную клетку?
еще один вопрос по этой теме.
PS: для доски 3 на 3 никакой алгоритм не обойдет все поле...

правильно. они начинаются с 5х5. а если ты хочешь прийти в определённую клетку, тебе надо вопервых не ходить в неё раньше времени, а вовторых когда ты обойдёшь поле, надо ещё проверить, вернулся ли ты туда, куда надо.

зы. ща попробую скомпилить ето дело тмт паскалём

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

http://enzyme.nm.ru/files/horse.rar

те ехешники, которые выдают runtime error 200, надо перекомпилировать борландом, а ещё лучше тмтом.

horse5.exe ищет все возможные пути и записывает их в файл result.txt с феноменальной скоростью (для 7х7 на атлоне 900 - около 200 000 решений в минуту). чтобы засрать любой имеющийся в розничной продаже винчестер, уйдёт не больше одного рабочего дня.
horse6 - то же, но не сохраняет решения на диске, а просто выводит их колво на екран.
horse3.exe показывает первое из решений на екран, ещё в несколько раз быстрее.
horse4.exe - то же, но можно задавать неквадратные поля.
остальные ехешники так или иначе неоптимальны.

в следующей серии ждите объяснение принципов работы етого дела, если я их вспомню.

итак. ето дело, конечно же, основано на поиске в глубину. но при полном переборе всех вариантов не удаётся за разумное время получить даже одно решение квадрата 9х9. но мы можем заметить, что:

1. если при ходе образуются клетки, из которых нельзя походить, и мы ещё не дошли до предпоследней клетки, то такой ход бесперспективен, ибо мы никогда не попадём в такую клетку, или напротив, сходим в неё и застрянем. ежели мы дошли до предпоследней клетки, то, понятное дело, такая клетка непременно образуется, и она будет последней. можно расширить сей критерий и сказать, что мы не будем рассматривать те ходы, при которых невозможно обойти конём все свободные клетки. такой критерий используется в horse7.exe, и, как показывает практика, не приносит особых дивидендов, к тому же считается медленно.

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

понятно, что конь сходит в клетку, которая под ним, и обойдёт все четыре оставшихся клетки. а сейчас

конь остановится на распутье, и куда бы он ни пошёл, ему не суждено обойти все клетки.

понятное дело, она не ищет на каждом ходе все варианты путей из каждой клетки. существует специальный массив zakr[0..32, 0..32], в котором записывается число клеток, в которые конь не может походить из данной клетки (хотя было бы логичнее записывать число клеток, в которые он может походить). стало быть, на каждом шаге сей параметр изменяется только у восьми соседних с конём клеток, и на вышеописанные критерии надо проверять только их.

бедный wormball

я написал не в ту тему, повторюсь:

для 9х9 решения нет.

ето если с приходом в ту же точку, а так есь:

можешь проверить на досуге

что "_так_есь_" я знаю

ето если с приходом в ту же точку, а так есь:

можешь проверить на досуге

Так последовательность ходов вроде получается циклической?
Тогда переносим клетку с 1 в любую другую и последовательность снова останется циклической.
Т.е. я хочу сказать, что если для начальной клетки (1, 1) удалось найти цикл по всем клеткам, то и для любой клетки (x, y) таковая тоже есть.
PS: масло маслянное...

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

Я имел в виду классический случай 8 на 8.
Да, вот еще возник вопросик: а сколько всего способов обхода для поля NxN? Может, получиться найти математическую формулу, или тут тоько полный перебор?