Здравствуйте, mbait, Вы писали:

M>А теперь, знатоки, внимание, вопрос: у этой задачи существует детерминированное решение?

У этой задачи существует детерминированное решение даже при отсутствии обратной связи.
Даже если все, что мы можем — это только подавать команды, но никогда не знаем, удалось ли роботу их выполнить.
Мы можем сформировать последовательность команд, которая будет гарантировать обход всех достижимых клеток лабиринта независимо от лабиринта.

Если нам известен размер лабиринта и известно начальное положение робота:
1. Берем множество всех возможных лабиринтов (оно конечно) и нумеруем их.
2. В каждый лабиринт помещаем по роботу. Настраиваем их всех на прием нашего передатчика, чтобы каждая поданная команда выполнялась всеми роботами одновременно.
3. Даем последовательность команд, котрая заставит первого робота обойти свой лабиринт (остальные роботы параллельно выполняют те же команды).
4. Даем последовательность команд, которая заставит второго робота обойти свой лабиринт из точки, в которой он оказался после выполнения пункта 3.
5. Даем последовательность команд, которая заставит третьего робота обойти свой лабиринт из точки, в которой он оказался после выполнения пунктов 3 и 4.
6. Даем последовательность команд, которая заставит четвертого робота обойти свой лабиринт из точки, в которой он оказался после выполнения пунктов 3, 4 и 5.
...
И так, пока не заставим последнего робота обойти последний лабиринт.
Получается, что каждый робот выполнил одну и ту же (очень длинную) последовательность команд, и каждый робот при этом обошел свой лабиринт.
Таким образом, эта очень длинная последовательность команд и есть детерминированное решение, подходящее для любого лабиринта.

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