traintracks

traintracks

Решатель головоломки «Поездные пути», написанный на JavaScript.

Головоломка

В «Saturday Times» (в Великобритании) есть головоломка под названием «Железнодорожные пути».

Это сетка из квадратов 8х8. В каждой строке и столбце есть номер, показывающий, сколько частей находится в этой строке или столбце.

Также имеется маркер A и B в начале и конце трека. Возможно, на сетке уже есть одна или несколько других фигур.

Ваша задача — нарисовать дорожку, используя только прямые или угловые элементы под углом 90 градусов от A до B чтобы правильное количество элементов присутствовало в каждой строке и столбце сетки.

Вот пример головоломки:

Кодирование головоломок

Мы кодируем головоломку следующим образом: <A><B>-<cols>-<rows>-<pieces> .

Загадка выше: 54-14134544-54234341-48EW.53NE

A и B — это числа от 1 до 8, указывающие, как далеко по сетке (слева внизу) находится начало (как далеко вверх) и финиш (как далеко вправо). В этом примере A равно 5 , а B равно 4

cols — это список из 8 чисел от 1 до 8, указывающих ограничение столбца. числа читаются слева направо (вверху головоломки, как показано на рисунке).

rows одинаков для строк, на этот раз сверху вниз, что облегчает понимание настоящей головоломки.

pieces — это список начальных кусков (не считая начала и финиша), разделенных точкой . и являются <rol><col><type> , где тип — это то, как указывает фрагмент. Допустимые типы: NS (вертикальный), EW (горизонтальный), NE L-образный, NW назад-L, SE вверх-L, SW с поворотом на 180 градусов L.

Это гораздо проще напечатать, чем кажется. Но если бы это использовалось на веб-сайте, то более интуитивно понятный пользовательский интерфейс мог бы создать головоломку и сгенерировать кодировку.

Решатель

В любом случае, когда у нас есть кодировка, мы можем вызвать инструмент traintracks :

 $ traintracks 54-14134544-54234341-48EW.53NE
Puzzle: 54-14343245-14134544-48EW.53NE
    1 4 1 3 4 5 4 4            1 4 1 3 4 5 4 4
   ┌─┬─┬─┬─┬─┬─┬─┬─┐          ┌─┬─┬─┬─┬─┬─┬─┬─┐
 8 │ │ │ │━│ │ │ │ │ 5      8 │ │┏│━│━│━│┓│ │ │ 5
   ├─┼─┼─┼─┼─┼─┼─┼─┤          ├─┼─┼─┼─┼─┼─┼─┼─┤
 7 │ │ │ │ │ │ │ │ │ 4      7 │ │┃│ │ │ │┗│━│┓│ 4
   ├─┼─┼─┼─┼─┼─┼─┼─┤          ├─┼─┼─┼─┼─┼─┼─┼─┤
 6 │ │ │ │ │ │ │ │ │ 2      6 │ │┃│ │ │ │ │ │┃│ 2
   ├─┼─┼─┼─┼─┼─┼─┼─┤          ├─┼─┼─┼─┼─┼─┼─┼─┤
 A │━│ │ │ │ │ │ │ │ 3      A │━│┛│ │ │ │ │ │┃│ 3
   ├─┼─┼─┼─┼─┼─┼─┼─┤          ├─┼─┼─┼─┼─┼─┼─┼─┤
 4 │ │ │ │ │ │ │ │ │ 4      4 │ │ │ │ │┏│━│━│┛│ 4
   ├─┼─┼─┼─┼─┼─┼─┼─┤          ├─┼─┼─┼─┼─┼─┼─┼─┤
 3 │ │ │ │ │┗│ │ │ │ 3      3 │ │ │ │ │┗│━│┓│ │ 3
   ├─┼─┼─┼─┼─┼─┼─┼─┤          ├─┼─┼─┼─┼─┼─┼─┼─┤
 2 │ │ │ │ │ │ │ │ │ 4      2 │ │ │ │┏│━│━│┛│ │ 4
   ├─┼─┼─┼─┼─┼─┼─┼─┤          ├─┼─┼─┼─┼─┼─┼─┼─┤
 1 │ │ │ │┃│ │ │ │ │ 1      1 │ │ │ │┃│ │ │ │ │ 1
   └─┴─┴─┴─┴─┴─┴─┴─┘          └─┴─┴─┴─┴─┴─┴─┴─┘
    1 2 3 B 5 6 7 8            1 2 3 B 5 6 7 8
Solved: true - Steps: 323

И вы можете наблюдать за работой алгоритма, добавив --animate . Посмотрите видео об асцинеме:

Мотивация

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

Итак, дорожная карта:

• Создать решатель
• Сделайте это AR
• Выгода ???