Рівняння на шестикутних плитках

Смішна головоломка складається з набору шестикутних плиток, щільно розташованих разом, причому на кожній плитці зображена цифра, знак рівності =, або арифметична операція: +, -, *, або /. Розглядаються суцільні шляхи, що проходять через кожну плитку рівно один раз, причому кожна наступна плитка є безпосереднім сусідом попередньої. Мета полягає у виборі такого шляху, щоб послідовність символів на плитках утворювала коректне рівняння згідно з обмеженнями, переліченими нижче. На кожному малюнку вище наведено приклад такої послідовності. У малюнку 1 сірий шлях зверху дає послідовність символів "6/3=9-7". Аналогічно, у малюнку 2, починаючи з нижнього лівого 3, отримуємо "3*21+10=73".

Можливих шляхів навіть у невеликому наборі шестикутних плиток — дуже багато. Гравець може засмутитися й захотіти побачити відповідь. Ваше завдання — автоматизувати пошук розв'язку.

Розташування шестикутних плиток і вибір символів у кожній головоломці мають відповідати таким правилам:

1. Гексагональний малюнок містить непарну кількість рядів, більшу за $2$. Усі ряди з непарними номерами містять однакову кількість плиток. Парні ряди мають на одну плитку більше, ніж непарні ряди, і ці довші парні ряди виступають ліворуч і праворуч за межі непарних. 2. У гексагональному малюнку міститься рівно один символ =. 3. У малюнку не більше двох символів *. 4. У малюнку менше $14$ плиток. 5. Припускаючи обмеження на допустимі послідовності символів, описані нижче, кожен гексагональний малюнок має єдиний прийнятний розв'язок.

Для того, щоб послідовність по шляху була прийнятною, вирази по обидві сторони від знака рівності повинні мати припустиму форму й обчислюватися до одного й того самого числового значення. Далі наведено правила припустимої форми та обчислення виразів:

6. Оператори +, -, * і / можна використовувати лише як бінарні; послідовності, в яких + чи - виступають як унарні, не приймаються. Наприклад, "-2*3=-6" та "1=5+-4" не приймаються. 7. Стандартний порядок виконання операцій не використовується. Натомість усі операції виконуються зліва направо, з однаковим пріоритетом. Наприклад, "44-4/2=2+3*4" прийнятне, а "14=2+3*4" — ні. 8. Ділення дозволено лише у випадках, коли результат на кожному етапі — точне ціле число. Наприклад, "10/5=12/6" та "7+3/5=3*4/6" припустимі, але "5/2*4=10" — ні, адже проміжне значення не є цілим. "5/2*4=8" також не припустиме, бо рівність потребує округлення чи відкидання дробової частини. 9. У числі допускається не більше двох послідовних цифр. Наприклад, "123+1=124" — не припустиме. 10. Послідовність, у якій цифра $0$ безпосередньо передує іншій цифрі, не приймається. Наприклад, "3*05=15" — не припустиме.

За цих припущень проміжний чи остаточний арифметичний результат ніколи не перевищує трьох мільйонів за модулем.