Кто может сделать быстрее задачу о "Путешествии Коня"?

bishop вообще-то слон
вот набросал, можно посмотреть

 

Stiver, доказательство в студию

 

Arhara

Общий случай описан здесь: A.Conrad "Solution of the Knight's Hamiltonian Path Problem on Chessboards." Discrete Applied Mathematics, Vl. 50,P. 125-134 В сети этой работы я не нашел, но если нужно, могу зайти как-нибудь в университетскую библиотеку и отсканировать.
Для специальных случаев, к которым относится и 8, есть значительно более простые алгоритмы, см. например здесь: http://www.borderschess.org/G-KTclosed.htm К сожалению на немецком, но смысл, думаю, будет понятен по картинкам.

В принципе ничего удивительного, одна расстановка ферзей находится ведь тоже за линейное время. На правах рекламы: пользуйтесь Google'ом

 

Я чуточку переделал и похоже слишком наворотил программу, но решает на произвольной доске и может записывать результаты в файл (запаситесь мегабайтами! ), а также можно выбирать с какого положения начать. Алгоритм "дубинный" - перебор подходящих ходов вокруг текущего положения коня по часовой стрелке. Спасибо всем за замечание по поводу Bishop'a .
Пробуйте, ругайте, советуйте!
Я ещё хотел спросить подойдёт ли эта программа как дипломная работа в колледже(техникуме)?

 

hxxp://algolist.manual.ru/maths/combinat/knight.php

5-10 минут программирования уже дипломная работа? зависит от преподователя наверное, у него лучше и консультироваться.

 

Arhara

Подобное семейство путей может быть построено для любой заполняемой в принципе доски (т. е. для любой большей 4 на 4). В школе я исследовал (вручную) доски до кiльканадцять на кiльканадцять включительно.

 

Выложил сюда: http://slil.ru/23052820

 

Как и обещал - задачка на ассемблере. Хотелось бы оптимизировать программу ещё, но не знаю как это сделать с моим П3. В общем попробуйте сделать прогу быстрее.

 

ты решаешь эту задачу с какой - то целью или это просто хобби?

 

Хобби. Просто хотелось посмотреть на что способен П3 как камень

 

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

 

Идея хорошая, но агоритм не очень понятен - распиши поподробнее. Будет время - сделаю.

 

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

 

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

 

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

 

UbIvItS
А ты свою идею не пробовал для начала на игроках проверить? Как оно в реале будет выглядеть (на худой конец самому попробовать поиграть). Можно на шахматные сайты кинуть идею, как они к ней отнесутся.
Только при расстановке должно быть одно ограничение - соперники не видят самого процесса расстановки.
ЗЫ
Токмо кажется мне, что классическая расстановка наилучшая в игровом плане.

 

почему это видить не должны(????) - в классике ж мы видим, а играть не пробовал - руки не дотягивались. насчёт того, что интересней: кому как --------> здесь спорить бесполезно

 

UbIvItS

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

 

а как дело обстоит с ходами при такой схеме?

 

UbIvItS
Ну, значит, как обычно. Расставили в темную, открылись и играют. Ты должен на такие вопросы отвечать, если идею выдвинул.