Логические задачи. Самостоятельное решение приносит удовольствие!

Любимую собаку-киборга мегамозга злобные оккупанты посадили в клетчатый лабиринт 6х6 клеток, в левую нижнюю его клетку. В правой верхней клетке находится лестница - выход из лабиринта. Стороны квадрата: северная, восточная, южная и западная – непроходимы, также между некоторыми клетками стоят непроходимые перегородки, однако путь от собаки к выходу существует. Но Мегамозг все это предусмотрел и заранее снабдил собаку бесконечным источником энергии и конечной последовательностью команд, которую она начинает выполнять, попав в лабиринт. Собака понимает команды вида: «север», «юг», «запад», «восток». При выполнении команды она перемещается в соседнюю клетку в соответствующем направлении. Наткнувшись на перегородку, собака останавливается и переходит к выполнению следующей команды.
Как мегамозгу задать такую последовательность команд, выполняя которую, собака гарантировано когда-нибудь наткнется на выход?