Бесконечный кот

[Equinoxe]

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

(Оффтоп)

Наличие решения не гарантируется :) Но есть несколько неплохих гипотез, изложенных в т. ч. на соседнем форуме, если что, могу их выложить
А вообще, если вдруг задача распространенная, то дайте ссылочки :)
И да, если формулировка не очень, речь идёт о критерии существования гамильтонова цикла в графе из «грязных кафелинок»

[Morkonwen]

Вы уже в курсе, конечно, но необходимо чтобы не было петель. Только одна - сам путь

Кроме того не всегда можно определить ошибался ли кот. Например обычный путь 1-2-3-4-5 он мог один раз пройти как 1-2-5 а следов не останется! Либо я не понимаю вашего условия. Вы не могли бы более абстрактно сформулировать=)? Например пройдены гарантированно все кафелинки со стрелками?

[Equinoxe]

Morkonwen, условие можно переформулировать так: существует ли хоть одно расположение стрелок, при котором кот не ошибся?

-- Сб июл 02, 2011 15:17:16 --

А, и да, в условии сказано, что кот должен вернуться на начальную и пройти все клетки со стрелками. Т.е. обойти по циклу их всех

[Morkonwen]

Equinoxe в сообщении #464296 писал(а):

А, и да, в условии сказано, что кот должен вернуться на начальную и пройти все клетки со стрелками. Т.е. обойти по циклу их всех

Один единственный раз? у вас в условии он аж утомился - столько раз обошел)

[Jony]

(Оффтоп)

по условию заключаем, что Equinoxe зовут Аня, и она любит котов

[Equinoxe]

Jony,

(Оффтоп)

А ещё и то, что у Ани есть кот по имени Наркот :)