Доброго времени суток, завсегдатаи форума "Программирование"!
Еще не надоело отвечать на вопросы о том, какой ЯП лучше? Если надоело, то вот вам настоящая задачка.
Дана стандартная шахматная доска 8*8 клеток. В клетке А-1 стоит конь. Конь двигается по правилам игры, т.е. буквой “Г”. Известно, что конь может обойти всю доску, побывав в каждой клетке доски только один раз.
Задание:
Написать программу, которая выдаст количество различных обходов конем доски. Самые умные могут посчитать в уме!

Ну насчёт программы - это по моему слишком.
А на бумаге я пробовал частенько (лекции коротал в институте).
Короче, то что может - это факт. И по моему только одним путём.

Добавлено спустя 1 минуту, 35 секунд:
если, конечно, не считать поворот доски на 90 град. за другой путь

Добавлено спустя 2 минуты, 24 секунды:
Ой, вспомнил....
Я же смотрел на доске 10х10 не в ту степь...

zalom

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

Ну я для этой доски, думаю, решений на несколько десятков ПОРЯДКОВ больше!

Ну зачем же так самокритично? Добрее надо быть к себе.
Признайся честно, "похождения коня" - это тема твоего курсовика? И ты хочешь нахаляву получить здесь готовую программулину. Иначе, почему бы тебе не подискутировать с zalom

Представь на секунду, что, кроме тебя, никому это не интересно.

K'ross

Да, тут ты прав, не хватает у меня мозгов ее решить.

Нет, всего лишь одно из заданий по криптографии.

Сильно сомневаюсь в возможности такого исхода.

Так там не о чем дисскутировать.

Вопрос: если тебе ЭТО неинтересно, зачем ты сюда зашел?

Hamoff

С тем же успехом, иожно было сказать "гы-гы" и поставить смайлик. Если знаешь как она решается, почему бы не рассказать почтенной публике.

Hil

См. выше.

А ход своих рассуждений помнишь?

В связи с новыми данными, получеными из переписки с vor'ом, сообщаю: программу я буду писать сам, т.е. правила раздела "Программирование" нарушать не собирался. Очень прошу вернуть ветку в раздел "Программирование".

В таком случае, удаляю большую часть постов.

При первой попытке задуматься возникают мысли, что 1) здесь проходит тупой рекурсивный перебор и сильно оптимизировать его не удастся 2) для доски 8x8 он не годится, поскольку объем вычислений на десятки порядков превосходит суммарную мощность всех компьютеров Земли вместе взятых.

Поиск подтвердил мои догадки:
http://users.kpi.kharkov.ua/sg_chess/me ... cles/1.htm
К сожалению, дата на статье не указана.

vor

Собсна, аналогичная мысль пришла мне в голову. Программу написал, запустил, и лег спать... Через восемь часов оказалось, что она нашла всего 400.000 вариантов. Так что...

Сейчас пытаюсь реализовать след. мысль:
1. Делаем обычный рекурсивный обход конем доски, но с таким условием, что конь ходит случайным образом (из 7 вариантов)
2. Каждый раз, как заходим в тупик - прибавляем счетчик B.
3. Если доходим до 64-ой клетки - прибавляем счетчик G.
4. Таким макаром гоняем программу несколько часов.
5. Считаем общее кол-во возможных заполнений доски. Обозначим O. (?)
6. Нужное нам число получаем из соотношения O*(G/B).
Осталось лишь решить как посчитать пункт №5. У кого-нибудь есть идеи?

P.S.

Гм... Интересно... За ссылку спасибо. Но ведь не может препод задавать в качестве задания нерешенную проблемму?.. Или может? А как тогда понять то, что у Hil'а была такая-же задача?

Mozg[1024]
Если речь о точном числе вариантов, то без полного перебора не обойтись. Возможны раличные способы отбрасывания тупиковых веток, но они потребуют дополнительных расчетов для каждой позиции. Наскоро сляпал программу (TP 7.1) - для 5x5 считает (в дереве - порядка 2 млн узлов), для 6x6 уже задумывается надолго.


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


Можно в ЛС спросить, действительно ли точно такая же. Потому что распространенная задача - найти один путь. Или найти путь с заданными начальной и конечной клетками.

vor

Ну это понятно. А что ты думаешь по поводу


Интересно... А с кем имею честь общаться?

А какие заполнения доски имеются в виду и почему это должно быть связано с числом обходов?


Да так... задачи для городской составляю, детей к олимпиадам готовлю. Но у нас уровень невысокий.