Пятнадцать головоломки свойственна в том , что только половине возможных состояний расположения разрешимы. Если вы перевернете плитки 14 и 15, вы не сможете сдвинуть блоки так, чтобы они перевернулись.
Ваша задача - создать программу, которая принимает список целых чисел в выбранном вами формате (содержащий ровно один экземпляр каждого из чисел от 0 до 15, где 0 - пробел), представляющий состояние расположения плиток в сетка 4x4 и выводит единственное логическое значение, определяющее, разрешима сетка или нет.
Самый короткий код для этого на любом языке выигрывает.
Ответы:
Желе , 9 байт
Монадическая ссылка, принимающая список целых чисел, читаемых в порядке старших строк, чередующихся между левым-правым и правым-левым, который дает,
0
если решаемо, и1
если нет (чтобы инвертировать это, добавьте¬
справа от кода).Попробуйте онлайн! (этот пример - доска, где 12 просто нужно сдвинуть на место)
Как?
Как и в ответе Джона Дворака, мы вычисляем четности и используем змеевидный порядок ввода для упрощения четности на доске проверки, хотя вместо проверки равенства четности мы суммируем счетчик не в порядке с ненулевыми индексами и проверяем, странный:
источник
J, 28 символов
Порядок ввода - основной ряд, строки читаются попеременно слева направо и справа налево по одному пути по всей таблице. Предполагается, что ноль принадлежит верхнему левому углу.
Использование в Windows:
Объяснение:
<nul set /p=
используется для предотвращения перехода на новую строку во вводе, котораяecho
выдает, что".
не нравится. Конечно, Unix поддерживаетecho /n
.v&.".&.stdin''
читает «v под анализом под stdin», что означает «ввод, затем анализирует ввод, затем выполняет v, затем отменяет анализ (= формат), затем отменяет ввод (= вывод)».1!:1]3
на один символ короче, но не имеет определенного обратного.C.!.2
означает «четность перестановок». Он возвращает либо1
(четный паритет), либо_1
(нечетный паритет). Это,_1^inversions
_1^i.&0
означает «-1 к степени индекса 0».C.!.2=_1^i.&0
означает «равенство перестановки равно четности положения дыры?»Это работает для платы 4x4, но если желаемая конечная позиция является главной строкой слева направо, то перестановка для решаемой позиции имеет нечетное число инверсий и, следовательно, нечетную четность. Кроме того, четность меняется на противоположную (для любого входного порядка), когда желаемое положение отверстия перемещается сверху вниз слева направо. В обоих случаях исправление состоит из одного символа: добавьте
-
после,=
чтобы изменить ожидаемый паритет.Доказательство правильности:
После каждого хода ноль обменивает позицию с некоторым числом, переключая четность перестановки. Ноль также чередуется между белыми и черными позициями шахматной доски, обозначенными нечетными и четными позициями во входном порядке. Таким образом, это условие является необходимым. Это также достаточно для счетного аргумента: общеизвестно, что ровно половина позиций разрешима. Это условие отфильтровывает ровно половину возможных позиций.
источник