Конь проходит все клетки поля всего один раз / гифки :: шахматы

+0,0

В школе так развлекались... на тетрадном листе надо было покрыть все клетки...

zzzak

04.10.2012, 11:27

+1,0

писать цифры... что бы не сбиться =)

04.10.2012, 19:16

+0,2

04.10.2012, 11:34

+1,4

04.10.2012, 19:33

+0,8

В программировании это легко решается рекурсией.

04.10.2012, 11:51

-2,2

вообще то это комбинаторная задача по матрице, а реализуешь ты её с рекурсией или без, полным перебором или адаптивным - это как тебе легче (но я не думаю что напишешь алгоритм меньше чем за 2 недели в лучшем случае)

04.10.2012, 12:23

-1,2

Ты намного ошибся, 2-е недели это слишком много для этой задачи, учитывая, что уже я уже реализовывал этот алгоритм в универе

04.10.2012, 12:28

-0,2

отлично, код в студию!
P.S. Время работы программы так же учитывается в эти 2 недели, даже если сама программа написана за 1 день.

04.10.2012, 13:01

-1,0

Ты перечитай, что ты написал: "но я не думаю что !_напишешь_ !алгоритм меньше чем за 2 недели в лучшем случае".
Не надо придумывать ad-hoc условия, про время выполнения не было ни слова. А я в свою очередь не говорил, что собираюсь писать - жалко времени, да и незачем. Всё уже украдено до нас и в интернетах много по этой теме есть. Так что выдыхай.

04.10.2012, 13:12

-0,6

ну не любой же код считать качественным алгоритмом. Полный перебор 64^63 можно написать за час, а искать оптимальный вариант он будет х.з. скоко (если с середине не вылетит из-за ошибки работы с памятью)

04.10.2012, 13:32

-1,3

Согласен. Качество надо если есть материальный или академический интерес. Так как нет сейчас ни того, ни другого, то заниматься этой задачей смысла 0.

04.10.2012, 13:39

-0,3

какой 64^63? если просто считать что конь имеет макс 8 (от 2 до 8) возможных вариантов на ход и надо сделать 63 хода то это 8^63. но с каждым ходом вычеркиваются клетки и кол-во вариантов чем дальше, тем сильнее уменьшается.

ygyman

04.10.2012, 14:55

+0,1

Обычный эвристический алгоритм, никакой рекурсии и NP-сложности. Сверься с моим комментарием ниже (http://joyreactor.cc/post/465349#comment1048081).
И я написал его за 2 часа на с++, плюс, потом дописал lookahead-логику.

04.10.2012, 13:17

-0,1

согласен. А lookahead зачем? Сущестуют тупиковые "ветки" ?

04.10.2012, 13:27

-0,6

Да существуют, этож эвристика. Но на практике он там не очень то и нужен.

04.10.2012, 13:40

-0,3

Тоже писал такую штуку в прошлом году, тоже на с++, правда другим методом. Написал за вечер. Хз каким наркоманом надо быть чтобы 2 недели мучать такой алгоритм.
п.с. только поле было произвольного рамера

Barbod

04.10.2012, 13:57

-0,6

Мне одному кажется что в итоге получается нечто, похожее на свастику?..

DrPlankton

04.10.2012, 12:04

-1,8

Да, одному.

koshernii-svin

04.10.2012, 12:20

+0,2

Нет.

Zmey!

04.10.2012, 12:34

-1,0

а чё пост не про сиськи разве, про фашистов чёле, какая безобразия!

МаРсОхОд Потемки

05.10.2012, 07:00

0,0

похуй да с на какой клетке он стоит? здесь он не на своем месте

чупа чупс

04.10.2012, 12:09

-0,2

Братюня - порадовал. Люблю шахматы.

EN0Tik

04.10.2012, 12:10

-0,6

ну тут вариантов помоему несколько и да в далеком детстве так развлекались ставя по клеткам 1..2..3...4 чтоб по ходам ориентироваться помоему сотня итог был

totopo

04.10.2012, 12:12

-0,7

о_О клеток, то всего 64

04.10.2012, 12:26

-0,5

это здесь 64 клетки. но это не единственный квадрат или прямоугольник

totopo

04.10.2012, 14:57

0,0

чем больше площадь, тем выше сложность

04.10.2012, 15:00

0,0

04.10.2012, 12:16

-0,4

Лет 9 назад на компе у друга играл в какую то игру (там по замку лазиешь), вот там задание было точно такое же. Поломал голову, в итоге дня через 3 нашёл комбинацию.

DeRR1L

04.10.2012, 12:31

-0,8

Лежит на википедии уже несколько лет.
И не надо тут " я ничитаю вики, читаю только риактар!1"

DeFFenDeR

04.10.2012, 12:31

-0,6

Конь проходит все клетки поля всего один раз
И чё? Почему это смешно или забавно?
От этого становится хорошее настроение?

Veronika2001

04.10.2012, 12:32

-3,4

у меня, да.

angry_cat

04.10.2012, 12:42

0,0

для тп это не интересно

Fitc

04.10.2012, 16:14

+0,0

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

Veronika2001

04.10.2012, 16:22

-0,5

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

Fitc

04.10.2012, 17:14

-0,1

ПРСТ ЗБС, только теперь не актуально=(

Bronepsix

04.10.2012, 12:34

-0,6

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

INVID

04.10.2012, 12:38

-1,1

я башенкой так же могу

ProtoS

04.10.2012, 12:38

-0,3

игра такая была на компе, заебался но прошел)

Лангольер

04.10.2012, 12:42

-0,6

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

04.10.2012, 12:43

+1,8

Я писал в универе чуть более сложный вариант, если на определенном шаге есть несколько клеток с наименьшим коэффициентом, он просматривал на n шагов вперед.

04.10.2012, 12:45

-0,3

Толково, если есть возможность распараллелить вычисления.

stjoker

04.10.2012, 13:19

-0,6

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

04.10.2012, 13:32

-0,5

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

ygyman

04.10.2012, 15:20

0,0

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

04.10.2012, 15:30