Идея задачи взята отсюда: http://www.coderussia.ru/treasurehunter.html, 11 задание.
На прямоугольной сетке нарисован лабиринт. Каждая ячейка либо путь, либо стена (перемычек между клетками нет). В одной точке находится ваше существо, в другую нужно прийти (там типа сокровище). Гарантируется, что путь есть.
Доступны следующие методы управления: шаг вперед, шаг назад, поворот направо или налево. Доступны проверки, есть ли впереди, сзади, слева или справа стена или ваши следы (только в соседних ячейках, проверять через 1 или дальше нельзя). Можно ставить цикл, пока не найдено сокровище, цикл, пока не достигнуто условие (см. выше, проверка). Есть условный оператор (в системе он реализован без ветки "иначе"), доступны булевы И и НЕ.
Нет переменных, вообще. Запоминать дерево пройденных путей, учитывать координаты и т.д. не получится.
Можно ли написать алгоритм (пусть долгий, но рабочий), который в любом лабиринте, при любом расположении существа и сокровища (но путь от 1-го ко 2-му есть), выведет существо к сокровищу?
На хабре есть статья по алгоритму прохождения, но там у чувака вроде есть переменные (долго не читал). http://habrahabr.ru/post/198266/
А без переменных (с описанными ограничениями) можно?

(3) гы, по условию задачи переменных для запоминания графа пройденных тобой путей нет
(4) "не вижу проблемы наваять" и "всё, сделал!" - немного разные вещи )))

(5) с опытом, задача решена (более неинтересна) == уже просчитал решение задачи
т.е. не вижу смысла что то доказывать "для славы"

На чем реализован Лабиринт ?

(0) любой случайный алгоритм при неограниченном количестве ходов

(6) я тоже наваял алгоритм (правда сам не понимаю, как он работает), который решает лабиринт, приведенный в примере. но решит ли он любой лабиринт, хорошая математическая задачка.
(7) в первой ссылке есть реализация. если хочется убрать ограничение на количество операторов или задать свой лабиринт, надо на чем-то писать. почему бы не на 1с? ;-)))

(8) генерации случайного числа среди доступных инструментов нет... пичалька )))

(10) подойдет и псевдослучайное

(10) А текущее компьютерное время есть ?
     Если есть то можно сделать и генератор.

(0) "Всегда направо". Увидел следы - меняешь на правило "всегда налево". Вот и весь алгоритм. Можно также начинать с правила "всегда налево".

(11), (12) как же на мисте не любят читать ))). в (0) перечислены все доступные инструменты. псевдослучайных чисел и даже переменных нет!!!

(13) звучит интересно, но не работает. если ты уперся в свои следы, и сзади тебя твои следы - куда тебе идти?

"правила левой руки" по-идее должно хватить

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

(15) Работает. Можешь проверить. Если в лабиринте нет замкнутых циклов, тогда подойдет любое из правил.
Переключение с правила на правило нужно для выхода из замкнутого цикла.

(15) Идти вперед, но по другому правилу.

всем, кстати рекомендую попробовать первую ссылку, приведенную в (0), задача 11. сразу перестаешь думать, что все очень просто.

(17) "вдоль внешней стены" - аргумент, ибо в этом случае просто нет входа :)
а вот "просто одну стенку обходить" - тат да, проблема, но тут должны помочь "следы"

(19), (21) рабочий алгоритм дадите? четкий, читаемый?

(13) кстати, переменной для хранения текущего направления (направо или налево) по условию нет!!! я тоже забыл про это )))

(22) Пока не нашел следы идешь по правилу "левой руки", потом по правилу "правой руки".

(24) Хотя... Тут без рекурсии не обойтись. Рекурсия допустима?

(24) Это же надо запомнить, что следы нашёл. А переменных нет
(25) Нет

(26) Ты - автор?

(0)ОМГ "Кумир" задача для 5 класса.

(27) Воу-воу, палехче. В (0) же ссылка

(25) рекурсии нет. а помогла бы?

(0) приведи полный текст задания сюда.

(26) Есть цикл "пока не нашел следы".

(0)Нельзя написать

(30) Рекурсия помогла бы. Дело в том, что может потребоваться несколько "переключений правила".

(30)Помогла, она дала бы понять когда переключить правило, хотя бы один раз.

+(35)Наверное даже дала бы понять когда переключать правило многократно.

(32) Блоков не хватит на два одинаковых цикла)

По ссылке не заходил, дома посмотрю. Условий не пересекать свои следы и выбирать путь на перекрестках где следов нет не достаточно?

(31) ну если в (0) для тебя неполный текст задания, то открой первую ссылку, задачу 11.
как минимум, написать алгоритм, решающий данный лабиринт.
как максимум, написать алгоритм, решающий произвольный лабиринт. правда (33) говорит, что не получится

(39) к сожалению не очень удобно открывать мультяшную ссылку с явным игровым наполнением

(38) а если вокруг тебя везде твои следы? все, приплыли?
(34) окей, а одна переменная типа "булево" тебя бы спасла? в ней хранить право/лево?
(39) вроде все постарался написать по максимуму формально. какие конкретно уточнения нужны? по ссылке зайди из дома потом, если интересно стало.

Блин зачем такие задачи давать посреди рабочего дня? Все работа пока.

проблема в том, что любой алгоритм перебора должен отмечать "бесперспективные" ветки. И следов тут недостаточно. Ладно перебор. Даже эвристику невозможно реализовать, так как нет переменной для хранения значения эвристики, и нельзя сравнить с прошлым значением.

Задача максимум нереализуема.
Задача минимум реализуема в виде "решил вручную и сделал такой алгоритм, который пойдет этим путем".

если вход и выход расположены на границе лабирина (а не внутри него), то есть правило "левой" руки, то есть всегда нужно сворачивать налево и гарантировано найдешь путь..

ничего запоминать не нужно, только идти все время касаясь левой рукой стены

(41) Да, тут минимум нужно иметь 2 вида следов одинарный и двойной.

Может быть и можно написать, надо хорошо подумать.

пока не этоВыход цикл
попытка
  повернутьНалево()
   Исключение
    попытка
     пройтиПрямо()
    Исключение
     попытка
      повернутьНаправо()
     Исключение
       ПойтиОбратно()
     КонецПопытки
    КонецПопытки
   КонецПопытки
КонецПопытки
КонецЦикла

>(в системе он реализован без ветки "иначе")
Там кстати она есть. Даже есть ИначеЕсли) Надо на шестерёнку нажать.

(47)Это если простой лабиринт.
Уже сто раз поднималось это правило руки, можено же запомнить уже что только для простого лабиринта работает. Если в лабиринте есть лабиринт то надо руку менять.

(42) не одному же мне страдать )))
(44), (47) никто ж этого не гарантирует. а правило левой руки, да, понятно как реализовать.
(45) а поможет? даже если предположить, что будет показывать кратность следа?
(48) ёшкин кот! и точно!

(47) Концов попыток больше чем самих попыток.
Что за функция ПовернутьНаправо()? Как может быть исключение при повороте?
ПройтиПрямо = до упора?

Есть идея, дома проверю, если взлетит напишу.

без кратности следов, памяти и без взгляда через клетку - сильно сомневаюсь в существовании универсального варианта.

(50) Не выбираем пути, по которым ходили 2 раза. На перекрестках выбираем пути где не ходили, если таких нет, то где ходили 1 раз. Как то так вроде.

Идем по правилу "левой(правой) руки" с одним исключением. Если клетка "по правилу" со следами и есть клетка без следов, тогда идем на клетку без следов. Вроде должно работать.

(43) почему? достаточно порядка вариантов, и цикла попробовал - следующий вариант.
из подходящего варианта - возврата не будет

+(56) - единственное ограничение - этот алгоритм найдет только "первый подходящий" вариант

(56) твой вариант предполагает хранение дерева вариантов. с ним понятно, что решается, думаем без него взлетит или нет? ограничение, что переменных нет вообще

(56) Ты не сможешь вернуться по своим следам и начать заново. И ты не сможешь обеспечить неповторяемость ошибочных вариантов.

(57) тебе даже номер текущего варианта негде хранить

(58) В (0)можно управлять пером?

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

(62) Можно указать, что тут ставим след, а тут нет?

(0) Прошел. Остался еще один неиспользованный блок. Имхо, простенько.

(62) Не нужна никакая кратность. Просто идем по правилу "левой руки" и иногда от этого правила отступаем. Будет работать.

(63) в оригинале нет. потом захочется оставлять на клетках номера, так и до хранения в лабиринте дерева путей дойдем )))

(62) При наличии следов со всех сторон, идем по правилу. Отступаем от правила при наличии ячейки без следов.

бредятина какая-то. как без запоминания ходить по лабиринту? так можно просто тупо по одному и тому же пути ходить.

(0) Прошел. Блоков не осталось :/

(68) Так следы ведь есть.

Скриншотик мож вам выложить рабочего алгоритма, или сами попаритесь? :)

Модернизировал немного алгоритм, 3 блока осталось.

(70) а. понял

(70) и чего? как тебе следы в этом месте подскажут, что вон там есть место без следов и тебе нужно туда?

(74) см. (65)

Ну тогда тупо "затоптать" все сетку :) Алгоритм с возвратом. Ходим по стрелке. Если стена, возвращаемся, смотрим след. по час стрелке ячейку. Если вернулись в начало, значит пути нет.

проверил на http://s018.radikal.ru/i500/1206/02/eabf69ffb8d0.gif,  простой, без отдельноСтоящих стенок - работает  ...правда проверка ЕстьСледыВпереди так и не понадобилась, лабиринт наверное сильно простой  :)  
  
Процедура Аглоритм()
    
    Пока ШагВперед Цикл // поиск стены
        ШагНазад;
        ПоворотНалево;
    КонецЦикла;
    ПоворотНаправо; // нашли
    
    Пока Не ЕстьКлад Цикл
        Пока ШагВперед Цикл // движение    
            
            Если НЕ ЕстьСтенаСлева Тогда
                ПоворотНалево;
            КонецЕсли;    
            Пока ЕстьСледыВпереди Цикл
                Если НЕ ЕстьСтенаСправа Тогда
                    ПоворотНаправо;
                КонецЕсли;    
            КонецЦикла;    
            
        КонецЦикла;
        ПоворотНаправо; // уперлись в угол
    КонецЦикла;
    
КонецПроцедуры

(76) Путь есть по условию.

(75) Пример. Сокровище в центре лабиринта, и по кругу от него есть круговой маршрут.

(67) начинаем с 1 в кружочке. ломается вроде?
http://s017.radikal.ru/i426/1512/d2/88352e65dc7c.png

(79) Следы подскажут, когда отступить от правила левой руки.
Можешь проверить. На твоем примере - работает.

(80) Нет. Ты "затопчешь" весь левый нижний квадрат, после чего, благополучно выйдешь из него.

+(82) И это - правильно. Квадрат должен быть "затоптан" весь. Вдруг сокровище где-то там.

(82) как выйдешь? если идешь по правилу правой руки (как у меня), потом оказываешься в центре квадрата, дополнительных приоритетов по следам нет (все затоптано), как идти? поворот направо всегда доступен, так и будешь в 4 ячейках без стенок по кругу ходить?

(81) Ок. Любопытный алгоритм.

кстати, а на точку старта какие ограничения? Если она тоже в центре, то твой первоначальный след может разделить карту на две части, и часть останется неисследованной. Потому что для того, чтобы начать исследовать, нужно будет пересечь цепочку следов, а необходимости в этом алгоритм не увидит.

(85) хотя нет. это возможно, если прямо идти, а не вдоль стены.

(84) У тебя правило не правильное ))). Правильное правило правой руки - держаться за стенку правой рукой. Нет стены - идешь вперед.

(86) Нужно использовать правильное правило. см. (87)

(87) алгоритм правильного правила приведешь? вроде, если стены справа нет, поворачиваешь направо, иначе это не правило правой руки?

(0)
волновой алгоритм не катит ?

http://orionxl.ru/volnovoj-algoritm.html

(89) Нет стен вообще - идешь прямо.
Нет стены справа  - поворачиваешь направо.

(91) хорошо, ты в центре левого нижнего квадрата. стен нет, идешь прямо до стены. дошел, повернул направо? тогда ты идешь уже держась за стену левой рукой. косяк?
(90) все бы хорошо, но переменные хранить негде по условию. так-то алгоритмы есть, ага.

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

Принцип такой - сначала перебираем все возможные лабиринты - их конечное множество. Для каждого возможного лабиринта генерируем алгоритм его полного обхода из любой точки.
Далее соединяем все алгоритмы в один.
Полученный мега-алгоритм гарантированно обойдет случайный лабиринт из случайной точки.

Для лабиринта любого размера есть подозрение, что такого алгоритма не существует

(55) С исключением застрянет в таком закоулке:
http://s1.radikale.ru/uploads/2015/12/14/b9dfbfac6beac9a8e6083daf26c873cd-full.jpg
Старт отмечен точкой, закциклится и не выйдет

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

(94) Я когда решал (0) сделал следующее правило: в случае нет незатоптанных клеток и можно идти назад - идем назад. Вперед нафиг нафиг.

(96) Не поможет, я нарисую лабиринт, где
1)По правилу правой руки он зацикливается
2) По исключению со следами он находит одну дырку, попадает в узкий коридор который приводит его снова в этот лабиринт.
Если у тебя будут всякие "исключения" назад, то этот узкий коридор будет просто длинный и изогнутый так, чтобы обойти все эти "исключения"

(97) Рисуй.

(97) Вот то что решает задачу из (0) на тамошнем тестовом лабиринте. Принцип простейший. Нарисуешь контрпример - молодец.
http://screencast.com/t/qWgLjMgE

сотко!!!
(99) суровый алгоритм, обходит неплохо!
но вроде я контрпример придумал. С - это существо, * - сокровище. номера ходов написаны в лабиринте, пока не начинаем идти по следам. когда идем по следам, номера пишутся внизу, новый = уже написанный. заканчивается тем, что существо идет по правой руке по своим следам обратным ходом и зацикливается. http://s017.radikal.ru/i435/1512/5e/3e32cbc439f5.png

(100) В принципе да. В конце не совсем верно обсчитал вроде, но конец будет бесславным )

то есть похоже, что в данных условиях не получается.
а если чуть-чуть добавить информации, и выдавать кратность следа, то есть можно будет сравнить кратность следа с каждой из сторон. тогда получится?
навскидку, взять алгоритм (99), добавить, что если со всех сторон следы, то идем в сторону следа наименьшей кратности, а если таких не один, то по алгоритму.
пока головы не хватает понять что будет... )))

Поразмыслил тут на досуге. Ограничение на использование переменных можно обойти, можно написать компилятор из программы, где есть переменные, в программу с ограничениями из (0), правда это сильно скажется на длине программы.
Допустим, у нас есть одна переменная К типа word, ее размер от 0 до 65535. Тогда я утверждаю, что программу, использующую эту переменную К, можно скомпилировать в программу, с ограничениями из (0), где длинна строк этой программы возрастет в 65536 раз.

Избавляемся от К примерно следующим образом:
В процессе компиляции я раскопирую программу на 65536 блоков, значение переменной К будет храниться в позиции алгоритма. Каждый блок будет соответствовать конкретному значению переменной К. Какой блок сейчас работает, то значение К и будет эмулированно в этом блоке.
Любое действие над К можно организовать через алгоритмы переходов между блоками. Любое сравнение К с ветвлением можно в каждом блоке заменить на простой переход.

Если переменных несколько, и они используют N бит памяти, то технически их всех можно заменить одной переменной длины 2^N. Тогда программа из (0) при компиляции увеличится в 2^N раз

(103) Легче будет читать brainfuck чем подобный код )