поиск пути для кубика, в матрице nxn Опции

[Тёмный Эльф]

Привет! Подскажите пожалуйста с алгоритмом.
Есть матрица n на n. Имеется трехмерный кубик, который в начале пути находится в ячейке A[1,1], а в конце пути должен попасть в ячейку A[1,n]. При этом он должен пройти все ячейки матрицы, да еще плюс к этому не должен вставать на новую позицию своей запрещенной стороной (проще говоря, перваливаясь с одной своей стороны на другую, он не должен прикасаться к полу запрещенной стороной).
В самом начале пути эта запрещенная сторона находится сверху.

Для матриц 2x2 и 3x3 этот путь легко найти. В первом случае кубик проходит путь 1342 (если элементы матрицы пронумерованы по порядку), а во втором 125478963. Но как быть с матрицами 4x4 и большего размера я уже не знаю!

Может, существует общий алгоритм нахождения этого пути?

[xds]

Решение "в лоб" - катать по всякому кубик рекурсивной процедурой, исключая поворот на запрещенную сторону, попутно считая количество посещенных клеток (для определения в клетке (1, n) найдено решение или нет).

[Тёмный Эльф]

Решение "в лоб" - катать по всякому кубик рекурсивной процедурой

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

Сообщение отредактировано: Тёмный Эльф - 24.11.2007 22:55

[Lapp]

Да, я думала над этим. Но, по-моему, это будет выполняться долго.

А что означает "долго" в этом контексте?.. Минуты, часы, дни, годы?..

Возможно как-нибудь обойтись, например, без рекурсии и сделать алгоритм более оптимальным?

Это можно почти всегда в простых случаях. Но почему ты отказываешься от рекурсии, даже не попробовав? Рекурсия обычно реализуется на порядок проще - так может, начать все же с нее?.. Если уж говорить об оптимальности, то не следует ли оптимизировать ВСЕ, в том числе и затраты собственного времени? И вообще, об оптимизации можно говорить только тогда, когда уже что-то есть.

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

Никакому, надо исследовать оба. В этом и есть смысл полного перебора (в виде рекурсии или нет).

Тёмный Эльф, один вопрос мне неясен: можно ли наступать на уже пройденные клетки? Если можно, то способ отутюжить весь квадрать легко придумать и без всякого программирования. А если нельзя, то, думается мне, что задача при n>3 не имеет решения..

[Lapp]

Только сейчас обратил внимание, что тема абсолютно не на месте..

Привет! Подскажите пожалуйста с алгоритмом.

Почему она оказалась в теории Паскаля? Здесь обсуждаются вопросы, касающиеся теории реализации программ на Паскале и специфики выполнения паскалевсикх программ!

М

Переношу в Алгоритмы. И подозреваю, что скоро придется перенести в Задачи..

[hardcase]

Решение "в лоб" - катать по всякому кубик рекурсивной процедурой

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

[xds]

Для n > 9 уже довольно долго.

Добавлено через 17 мин.
Кроме того, на время выполнения влияет порядок перебора - оно меньше, если в первую очередь делается попытка хода с поворотом плоскости "запрещенной" грани.

[hardcase]

Написал программу. Правда, на С# (паскаля нету на машине, но код неотличим от C-шного). Для размера поля 3х3 решение существует, для 6х6, для 7х7. Для размеров выше - не знаю.

З.Ы. багу исправлял =)) - вот и правил мессагу.

З.З.Ы. в аттаче пример обхода квадрата 6х6, который предложила программа - это известный фрактал, (не помню как называется) сразу наталкивает на мысли о множестве матриц, для которых существует решение.


Сообщение отредактировано: hardcase - 25.11.2007 21:42

[xds]

Для 8x8 и 9x9 тоже. 10x10 лень дожидаться

[Тёмный Эльф]

Тёмный Эльф, один вопрос мне неясен: можно ли наступать на уже пройденные клетки? Если можно, то способ отутюжить весь квадрать легко придумать и без всякого программирования. А если нельзя, то, думается мне, что задача при n>3 не имеет решения..

Не-е на клетку можно ступать только один раз. Ну а время в секундах измеряется.
С реализацией "в лоб" разобралась (спасибо xds)

10x10 лень дожидаться

дольше чем полчаса.. (здесь то и встает вопрос, возможно ли оптимизировать на уровне алгоритма)

Почему она оказалась в теории Паскаля? Здесь обсуждаются вопросы, касающиеся теории реализации программ на Паскале и специфики выполнения паскалевсикх программ!

промахнулась малость

И подозреваю, что скоро придется перенести в Задачи..

Да не, не придется: меня интересует алгоритм.

[Lapp]

думается мне, что задача при n>3 не имеет решения..

Да, поспешил я с выводами.. Вчера сделал прогу (в три ночи), запустил для эн равных 4 и 5, увидел, что решения нет - да и обобщил недолго думая.. )))

Для 8x8 и 9x9 тоже. 10x10 лень дожидаться

Да, n=9 считалось на моем ноуте (AMD Turion 64 X2 @1.8 GHz) полминуты.. 10х10 пока все считается, уже 30 мин. Да, вопрос оптимизации встает, что называется, в полный рост . Я предлагаю всем, кому интересно, сделать следующее.
1. Опубликовать здесь время работы своей программы без оптимизации (с указанием процессора).
2. Включиться в соревнование по оптимизации .

[xds]

AMD Duron @ 800 MHz:
n = 8 - 1,43 с;
n = 9 - 18,84 с;
n = 10 - ? (точно больше 50 минут )

В первую очередь интересно, для каких ещё n нет решения

[hardcase]

Ставлю свою софтину (C# .NET 2.0, без распараллеливания) на задачу с n=10 процессор Pentium D 925 (3GHz). Надеюсь, к вечеру закончит.

Сообщение отредактировано: hardcase - 26.11.2007 17:25

[Lapp]

После чистки очевидных несуразностей на компе Athlon 64 X2, 2GHz для случая n=9 имею следующее:

Solution 1,  Time: 0h 0m 12s (1200 ms)
┌─┐┌┐┌──┐
│┌┘│││┌┐│
│└─┘└┘│└┘
│┌───┐└─┐
│└┐┌┐│┌─┘
│*││└┘└─┐
└┘││┌──┐│
┌┐││└┐┌┘│
*└┘└─┘└─┘

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

hardcase прав, очень похоже на фрактал. Но только я бы не стал искать сходства с каким-то конкретным фракталом. Если подумать, то так и должно быть (круто ляпнул, типа вумный.. ) - структура больших петель повторяет структуру малых. Вообще, забавно, что в таких простых условиях получается такой интересный результат..

2 xds: думаю, решения при n<>2,3 есть всегда. Я сейчас вывожу все решения, и их число растет с ростом n. Четверке и пятерке просто не повезло..

Сейчас тоже запущу свою прогу на n=10 и пойду спать

[Rian]

А можно исходники посмотреть. Уж больно интересно-мудрёная задачка.
Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать.

[xds]

После чистки очевидных несуразностей на компе Athlon 64 X2, 2GHz для случая n=9 имею следующее:

Solution 1,  Time: 0h 0m 12s (1200 ms)
┌─┐┌┐┌──┐
│┌┘│││┌┐│
│└─┘└┘│└┘
│┌───┐└─┐
│└┐┌┐│┌─┘
│*││└┘└─┐
└┘││┌──┐│
┌┐││└┐┌┘│
*└┘└─┘└─┘

1. По условию конец пути фиксирован - противоположная сторона первой строки (столбца).
2. И шо ж вы все транспонируете

[hardcase]

А можно исходники посмотреть. Уж больно интересно-мудрёная задачка.
Если есть, то на делфи, а нет, то в чём будет другие языки тоже нужно изучать.

Для того, кто знает С, перевести будет не проблема. Единственный момент, у меня катается кубик с запрещенной гранью, остальные грани не нумерованы, результат она выдает в виде команд кубику (распечатываются они в обратном порядке при выходе из рекурсии).

З.Ы. Комп до сих пор считает - вот уже на протяжении 5 ч 30 м.

Сообщение отредактировано: hardcase - 26.11.2007 23:10

[hardcase]

Как то даже незаметно закончился расчет "в лоб" для решения задачи с n=10. Времени ушло 7ч 25м.
Вот результирующий файл. Еще раз замечу, что читать решение нужно задом-наперед (т.е. снизу - вверх).

[Тёмный Эльф]

Времени ушло 7ч 25м.

Вот это да-а-а
З.Ы Напишу средние значения для n=8 и n=9 (измеряла по 10 раз, потом считала среднее значение)
n=8 : 0.9 сек
n=9 : 8,2 сек
(Процессор Intel Pentium 4 CPU 2.80GHz)

Сообщение отредактировано: Тёмный Эльф - 27.11.2007 2:45

[hardcase]

Судя по ответам xds'а, его программа справится с задачей часа за 3.