Slide15

Бесплатно · работает в браузере

Решатель пятнашек

Введите плитки с вашей головоломки. Решатель скажет, собирается ли она вообще, найдёт оптимальное решение и проиграет его на поле.

Поле

Введите числа так, как они стоят на вашей головоломке: слева направо, сверху вниз. Пустую клетку оставьте пустой или поставьте 0.

Нажмите на клетку, чтобы изменить её.

Эта позиция решаема.

Инверсий 39 + строка пустой клетки снизу 4 = 43. На поле с чётной стороной сумма должна быть нечётной.

Как работает решатель

Сначала проверка чётности. Половину всех расстановок нельзя собрать сдвигами, и проверка выясняет это за доли миллисекунды без перебора. Если ваша головоломка её не проходит, никакие ходы не помогут: две плитки придётся физически поменять местами.

Затем запускается IDA* - поиск с итеративным углублением, направляемый манхэттенским расстоянием с поправкой на линейные конфликты. Поиск точный: возвращаемое решение - самое короткое из существующих, а не просто хорошее. На поле 3×3 это миллисекунды. На 4×4 обычная перемешанная позиция решается меньше чем за секунду, сложные - за несколько секунд; самые тяжёлые позиции 4×4 на 70-80 ходов могут не уложиться в лимит времени браузера.

Поиск идёт в фоновом потоке, поэтому страница не зависает, и ничего не отправляется на сервер. Ваша позиция не покидает браузер.

Вопросы о решателе

Почему решатель говорит, что позиция нерешаема?

Потому что сдвигами достижима только половина всех расстановок. Если физическую головоломку разбирали и собирали заново или выковыряли и поменяли две плитки, она попадает в недостижимую половину. Проверка: посчитайте инверсии в порядке чтения; на 4×4 прибавьте номер строки пустой клетки снизу, начиная с 1, и сумма должна быть нечётной; на 3×3 само число инверсий должно быть чётным. Классический нерешаемый пример - собранное поле с переставленными 14 и 15.

Решение действительно кратчайшее?

Да. IDA* с допустимой эвристикой гарантированно возвращает оптимальное решение, если завершается. Показанное число ходов - минимальное количество сдвигов для этой позиции. Самые сложные позиции 3×3 требуют 31 ход, 4×4 - 80.

Можно ли решить 5×5 или больше?

Оптимально в браузере - нет. У поля 5×5 около 7,8 × 10²⁴ решаемых позиций и оптимальные решения по 100-200 ходов; точный поиск для него - научная задача, а не веб-страница. Для 5×5 и больше используйте метод «ряд за рядом» из инструкции: соберите верхний ряд и левый столбец вручную, а остаток - это поле 4×4, которое решатель уже возьмёт.

Как ввести свою позицию?

Читайте поле слева направо, сверху вниз, и вводите каждое число в соответствующую клетку. Пустую клетку оставьте пустой. Вердикт обновляется по мере ввода, а кнопка «Решить» разблокируется, когда каждое число от 1 до 15 (или от 1 до 8) встретится ровно один раз.