Як довести, що обходу вже немає

Питання, яке ставлять тільки програвши

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

Відповідь має бути точною — не «десь тут», а номер ходу, після якого обхід став неможливим. Знаходиться він двійковим пошуком по вже зробленому шляху: «чи можливий обхід звідси» лише один раз змінюється з «так» на «ні», тож достатньо кількох кроків. Але кожен крок — це окремий пошук, і половина з них питає про програну позицію.

Знайти легко, довести — ні

Обхід шукається перебором з поверненнями, у якому ходи впорядковані за правилом Варнсдорфа: першим пробується поле, з якого далі лишається найменше варіантів. Звучить як забобон, а працює — на звичайній дошці повний обхід знаходиться за кілька сотень вузлів, майже без повернень.

Так воно поводиться, поки обхід є. Коли його немає, спотикатись нема об що: щоб мати право сказати «немає», перебір мусить обійти все дерево. Стеля стояла на двох мільйонах вузлів — секунда-три на ноутбуці й помітно більше на телефоні, і так по кілька разів на одну відповідь.

Три речі, які видно на обличчі позиції

Програна позиція майже завжди має ознаку, помітну без перебору. Гра перевіряє три, і робить це на кожному вузлі.

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

Друга — забагато вимушених кінців. Клітинка з рівно одним незвіданим сусідом заходиться через нього і не залишається: вона або кінець маршруту, або те, куди кінь іде просто зараз. Кінець в обході один, і «просто зараз» теж один. Дві такі клітинки поза досяжністю — на одну більше, ніж обхід може витримати.

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

Чому відповіді лишились ті самі

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

Це не означає, що гра стала розумнішою. Вона стала менш упертою: раніше вона доводила безнадійність, перебравши все, тепер більшість безнадійних позицій видають себе першою ж перевіркою.

Скільки це коштувало

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

Стеля для відповіді на «де я помилився» тепер п’ятнадцять тисяч вузлів замість двох мільйонів. Двійковий пошук питає її пів десятка разів, тож уся відповідь укладається в десяту частку секунди на ноутбуці.

Чесна ціна цього: зрідка обхід, захований надто глибоко, не знаходиться в межах стелі, і гра назве позицію програною на кілька ходів раніше, ніж вона справді програна. Це та сама помилка, що жила й при двох мільйонах, просто настає раніше. У інший бік — назвати програну позицію живою — гра помилитись не може: «жива» кажеться лише тоді, коли обхід справді знайдено.