Правило правої руки в лабіринті, коли воно працює і як генерують лабіринти

26 вересня 2026 р. · 6 хв читання · Команда Тямки

Чому правило правої руки гарантовано виводить із одних лабіринтів і водить по колу в інших, як програми будують лабіринти і чому одні здаються важчими за інші.

Правило правої руки знають майже всі. Покладіть руку на стіну і йдіть, не відриваючи її, і рано чи пізно вийдете. Це правда, але не для кожного лабіринту, і навіть там, де правило працює, воно не найшвидше. Гарантія залежить від того, як лабіринт побудовано. Приклади з гри лабіринт онлайн на цьому сайті, де кожен лабіринт генерується в мить, коли ви натискаєте «Почати».

Як працює правило правої руки

Ідете вздовж правої стіни і на кожній розвилці повертаєте праворуч, якщо можна. Якщо праворуч стіна — прямо. Якщо й прямо стіна — ліворуч. У глухому куті розвертаєтеся і йдете назад, рука так само на стіні. Ліва рука працює так само, головне — не міняти бік посередині шляху.

Правило обходить стіну, як обходять берег острова. Якщо всі стіни лабіринту зʼєднані між собою або із зовнішньою межею, то стіна одна, довга і звивиста, і, тримаючись її, ви обійдете весь лабіринт і десь по дорозі знайдете вихід. У статті Вікіпедії про розвʼязування лабіринтів такий лабіринт називають однозвʼязним, і саме для нього правило гарантоване.

Коли правило не спрацює

Правило може зламатися, коли в лабіринті є петлі, тобто до якогось місця можна дійти двома різними шляхами. Тоді частина стін утворює окремий острів, не повʼязаний з рештою. Якщо ви почали біля такого острова або вихід стоїть посередині, оточений петлями, рука на стіні може водити вас по колу нескінченно.

Для таких випадків є інші способи.

• Алгоритм Пледжа, названий на честь Джона Пледжа з Ексетера. Він для випадку, коли вихід на зовнішньому краї. Ви тримаєтеся обраного напрямку, рахуєте всі повороти і відходите від стіни, лише коли їхня сума знову нуль. Це не дає застрягнути навколо острова.
• Метод Тремо, за іменем Шарля Пʼєра Тремо. Працює в будь-якому лабіринті з чіткими проходами, але вимагає позначок на підлозі, щоб знати, де ви вже проходили і скільки разів.

Як генерують лабіринти

Щоб зрозуміти, чому в одних лабіринтах правило гарантоване, варто подивитися, як їх будують програми. Беруть прямокутник клітинок, у якому всі стіни на місці, і прибирають стіни між сусідніми клітинками, поки до кожної клітинки не можна буде дійти.

Якщо не прибирати жодної зайвої стіни, яка утворила б петлю, виходить ідеальний лабіринт. Між будь-якими двома клітинками рівно один шлях. Математики назвуть це кістяковим деревом сітки, де клітинки — це вершини, а проходи — ребра, і в сітці з n клітинок рівно n − 1 прохід. Петель немає, отже, всі стіни зʼєднані, і правило правої руки в такому лабіринті обходить кожну клітинку, перш ніж повернутися на старт. Саме воно не зупиниться, але повз вихід пройде неодмінно, навіть якщо вихід посередині. На такому самому дереві збудовані головоломки з трубами, тільки з плиток, які потім повертають навмання.

Алгоритми різняться тим, яке саме дерево вони вибирають, і від цього залежить, який вигляд має лабіринт.

• Пошук у глибину (його ще називають рекурсивним поверненням). Ідете з клітинки до випадкового невідвіданого сусіда, пробиваючи стіну, а коли сусідів не лишилося, повертаєтеся своїм слідом до першого місця, звідки ще можна йти. Виходять довгі звивисті коридори і мало розвилок.
• Алгоритм Прима. Лабіринт росте з однієї клітинки, щоразу додається випадкова клітинка з межі вже прорубаного. Виходить густий кущ, багато розвилок і багато коротких глухих кутів завглибшки в одну-дві клітинки.
• Алгоритм Крускала. Стіни беруть у випадковому порядку і прибирають, якщо клітинки за ними ще не зʼєднані. Вікіпедія зауважує, що він дає досить рівномірні візерунки, які порівняно легко розвʼязувати.
• Алгоритми Вільсона і Олдоса–Бродера. Вони теж будують ідеальний лабіринт, але для них кожен можливий ідеальний лабіринт рівноймовірний. Вільсон робить це випадковими блуканнями зі стиранням петель. Решта алгоритмів тяжіє до певного вигляду лабіринту, і саме тому вони зручні для ігор.

Алгоритм зростального дерева, регулятор між Примом і пошуком у глибину

2011 року програміст Джеміс Бак описав у своєму блозі алгоритм growing tree, алгоритм зростального дерева. Є список активних клітинок. На кожному кроці береться клітинка зі списку, від неї пробивається прохід до невідвіданого сусіда, і сусід теж додається до списку. Клітинка, в якої невідвіданих сусідів не лишилося, зі списку випадає.

Усе залежить від того, яку клітинку брати. За словами Бака, якщо завжди брати найновішу, виходить пошук у глибину, а якщо завжди випадкову, виходить Прим. Змішавши, наприклад половину разів найновішу, а половину випадкову, отримуєте щось посередині.

Наш «Лабіринт» використовує саме цей регулятор. На рівнях з 1-го по 8-й найновішу клітинку беруть у чверті випадків, тож лабіринти ближчі до Прима, з безліччю коротких глухих кутів. З 9-го рівня частка найновішої росте і на 15-му сягає трьох чвертей, гілки стають довгими. Далі не йдемо навмисно. Чистий пошук у глибину дає так мало розвилок, що лабіринт перетворюється на прогулянку.

Чому в нашій грі правило правої руки не допоможе

Усі лабіринти в грі ідеальні, отже, правило правої руки гарантовано вивело б до кільця. Але воно заходить у кожну бічну гілку на своєму боці і вертається назад. А в «Лабіринті» крок у будь-яку бічну гілку коштує одне з трьох життів, і ви лишаєтеся на місці. У дереві кожна бічна гілка зрештою закінчується глухим кутом. І так на кожній глухій гілці на вашому боці до кільця, а три такі гілки закінчують рівень.

Гра задумана навпаки. Увесь лабіринт видно одразу після «Почати», стіни нічого не коштують, крок назад по шляху теж безкоштовний. Треба знайти маршрут очима і лише потім іти.

Як знайти шлях, коли видно весь лабіринт

• Засипайте глухі кути. Шукайте клітинки з трьома стінами, крім крапки і кільця. Кожна з них — глухий кут, і коридор до неї теж, аж до найближчої розвилки. Подумки зафарбуйте їх, і гілки скорочуватимуться, поки не лишиться сам маршрут. У Вікіпедії цей спосіб так і називається, заповнення глухих кутів, і він ніколи не відрізає старт від фінішу.
• Ведіть маршрут з обох кінців. Простежте шлях від крапки, а потім від кільця назад до крапки. Гілка, яка здається вдалою з одного боку, з іншого буває явно хибною.
• Оцінюйте розвилки заздалегідь. Де коридор розходиться, простежте кожну гілку очима, доки вона не скінчиться або не вийде на маршрут. На ранніх рівнях, ближчих до Прима, гілки здебільшого короткі.
• Ідіть відрізками. Коли коридор зрозумілий, пройдіть його одним рухом. Клавішу зі стрілкою можна утримувати, а стіни зупинять вас без жодних втрат.

Чому одні лабіринти важчі за інші

Розмір очевидний. «Лабіринт» росте від 5 × 5 на першому рівні до 14 × 14 на пʼятнадцятому. Довшає і маршрут. У всіх лабіринтів рівня маршрут однакової довжини, від 8 кроків на 1-му рівні до 44 на 15-му, тож кожна спроба рівня має ту саму кількість кроків з балами і той самий максимум.

Будова лабіринту важить не менше. У густих лабіринтах багато виборів, але кожен хибний короткий і його легко відкинути. У лабіринтах з довгими коридорами виборів менше, зате гілка може тягнутися через півполя, перш ніж виявиться глухою, і простежити її треба до кінця. Тому на пізніх рівнях регулятор зсувається до пошуку в глибину, а не лише росте сітка.

Є ще годинник. Ліміту часу немає, але лабіринт прихований до «Почати», тож час на обдумування теж враховується. Кожен новий крок до кільця дає 10 балів і бонус за швидкість, який тане, поки ви стоїте. Крок за 24 мілісекунди після попереднього дає повний бонус, прохід очевидним коридором по 8 клітинок за секунду зберігає більшу частину, а пауза в пів секунди лишає тільки базові бали. Пауза на розвилці коштує трохи балів на одному кроці. Хибний поворот коштує життя.

Що далі

Спробуйте «Лабіринт» і подивіться, як змінюються пізні рівні. Інші логічні ігри теж мають свої статті, швидкий рахунок без калькулятора для «Більшої суми» і як розвʼязувати головоломку із сумами. Усі ігри на сторінці усі ігри.