На просторах интернета с 2004 года существует игра "Жук".

Цель игры — построить такой лабиринт, в котором жук найдет выход за наибольшее количество шагов. Жук всегда находит выход, то есть, его алгоритм поиска выхода корректен, но не оптимален. Запирать жука нельзя, в конкурсе участвуют только лабиринты, из которых есть выход.

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

Жук всегда начинает свое движение с левого верхнего угла, а выход всегда находится в правом нижнем. Жук движется не оптимально, а следующим образом: он идет туда, где еще не был, либо был там реже. Т.е. проходя каждую клетку лабиринта, жук запоминает: сколько раз он был в этой клетке и при обдумывании направления своего движения в какой то конкретный момент он смотрит: сколько раз он был в клетке снизу, сколько справа, сколько слева и сколько сверху и движется туда, где он был меньше раз. Если таких направлений несколько и одно из них совпадает с текущим направлением движения, то он не меняет направления, иначе он движется согласно следующим приоритетам: вниз, направо, вверх, налево. Т.е. если минимальное число посещений сразу справа и слева (а двигался он при этом вверх или вниз), то жук идет направо, т.к. у "направо" приоритет выше.

На сайте есть таблица рекордов по всем лабиринтам, в которой указан пользователь и результат прохождения жуком его самого сложного лабиринта. Я там есть, 5-е место с 10 млн ходов. Кстати, 250 млн ходов у победителя было получено совсем недавно, еще в мае его не было.

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

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

UPD: для ускорения прогонки жука на ваших лабиринтах онлайн жмите F12 (консоль разработчика) и пропишите speed = 1/512. Для регистрации рекорда не нужно ждать, просто жмите сохранить и результат будет отправлен на сервер. Там он будет проверен и таблица будет обновлена.