задача: обход конем шахматной доски

WarWarRus

Где можно посмотреть, есть ли решение и сколько их для произвольных N и M (N*M - размер доски). Или может кто-нибудь знает универсальное правило?

mtk79

про квадратные:
ну 3*3 принципиально не проходится,
с 4 до 12 лично проходил, далее , если научиться для небольших и подумать...
Кстати, для простых N гораздо легче проходится

Xephon

С возвратом в начало или не обязательно?

WarWarRus

не обязательно с возвратом.. а насчет 4*4. Точно проходится? а то у меня получается что нет

WarWarRus

можно пример последовательности действий для случая 4*4?

mtk79

Да, я вспомнил: чистая 4*4 не проходится (точнее не вспомнил, а проверил) - но для прохождения 8*8 (наиболее сложный случай) как раз потребуется умение 4*4 (и, как раз, ее принципиальная непроходимость)

Zoltan

для 8*8
 
В 1823 году Варнсдорф в брошюре “Простейшее и наиболее общее решение задачи о ходе коня” предложил следующее правило обхода доски размером 8*8:
На каждом ходу ставь коня на такое поле, из которого можно совершить наименьшее число ходов на еще не пройденные поля. Если таких полей несколько, разрешается выбирать любое из них.
  

правда, оно иногда не работает

WarWarRus

спасибо, огромное. у меня просто прога тут насчитала, что 4*4 непроходима, вот я и испугалась. круто! значит не все потеряно

mtk79

Позволю себе сделать "спортпрогноз": "стерический фактор будет" действовать только для случаев 3*n и 4*n , причем: 3*n - непроходим кроме "случайного" 3*4, а 4*n - проходим кроме "случайного" 4*4. Для больших n все проходимо

oofc

Помнится, я по такому правилу на Прологе программу составлял. Так оно за 1.5 секунды рассчитывало обход по доске 72x72(комп был терминальный сервер 2xPIII и там сидела куча программистов, всё время что-то компилирующих).

amanahov

да, довольно быстро тогда считалось
была, кстати, не куча, а человек 6

seregaohota

Не существует гамильтоновых путей на досках
1xN при N>1
2xN
3x3, 3x5, 3x6
4x4
для остальных NxM обход ходом коня существует

Xephon

Автор написал выше, что путь не обязательно гамильтонов.

zuzaka

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

WarWarRus

спасибо, все работает. только вот 6*6 со вчерашнего вечера считает, пока только два пути нашел

seregaohota

На бейсике что ли?
На доске 6*6 насчитал вроде 6 с половиной миллионов решений.
to alessio: Имхо гамильтонов путь и обсуждается. Гамильтонов путь - каждая вершина графа посещается в точности один раз. Ты может с гамильтоновым циклом перепутал, в котором требуется возврат в конце в исходную вершину.
Оставить комментарий
Имя или ник:
Комментарий: