Что это за игра
Пятнашки — головоломка из пятнадцати фишек в коробке на шестнадцать мест. Одна клетка пустая, и фишки можно только сдвигать в неё.
Цель — расставить фишки по порядку от 1 до 15. Против человека здесь играет машина особого рода: она не соревнуется в скорости рук, а за долю секунды находит самое короткое решение из возможных. Вы получаете то же поле и должны уложиться в предел — кратчайшее решение, умноженное на запас вашего уровня.
На простом уровне запас двукратный, и победить реально. На эксперте — всего четверть сверху, а позиция почти случайная: это уже соревнование с перебором, который видит десятки ходов вперёд.
Правила
- Щёлкните по фишке рядом с пустой клеткой — она сдвинется туда. Фишка дальше в той же строке или столбце сдвигает весь ряд; каждая сдвинутая фишка — один ход.
- Можно играть стрелками на клавиатуре: стрелка двигает фишку, стоящую с этой стороны от пустой клетки.
- Фишка, уже стоящая на своём месте, подсвечивается зелёным.
- Собрали поле не длиннее предела — победа за вами; длиннее — за компьютером. Предел виден над доской, как только компьютер закончил поиск.
- После партии меню «Игра → Решение компьютера» проигрывает кратчайшее решение с исходной позиции.
Как собирать
- Классический способ — по рядам: сначала верхняя строка 1–2–3–4, потом вторая, а последние две строки собираются вместе, столбец за столбцом.
- Труднее всего поставить последнюю фишку ряда: сначала поставьте её под нужным местом, а предпоследнюю — рядом, и заведите обе одним «поворотом».
- Не разрушайте собранное. Если приходится сдвинуть поставленную фишку, верните её как можно скорее.
- Способ по рядам надёжен, но длинен. Чтобы уложиться в предел на сложных уровнях, смотрите на несколько фишек сразу и ведите их к своим местам параллельно, а не по одной.
Немного истории
Головоломку придумал Ной Чепмен, почтмейстер из городка Канастота в штате Нью-Йорк, в 1870-х годах. В 1880 году она стала настоящим поветрием: в пятнашки играли в конторах, на улицах и на заседаниях. Знаменитый составитель головоломок Сэм Лойд позже приписывал изобретение себе и рассказывал о награде в тысячу долларов тому, кто поменяет местами фишки 14 и 15, — но такая позиция нерешаема.
Это доказали ещё в 1879 году Уильям Джонсон и Уильям Стори: ровно половина расстановок фишек недостижима, и всё решает чётность перестановки. Достижимых позиций — 16!/2, около 10,5 триллиона. Поэтому здесь поле всегда перемешивается случайными ходами из собранного состояния: так оно гарантированно решаемо.
Для машины пятнашки стали классической задачей поиска. В 1985 году Ричард Корф предложил алгоритм IDA* и впервые нашёл оптимальные решения для случайных позиций. В 1999 году доказали, что любую позицию можно собрать не более чем за 80 ходов, — это «число Бога» для пятнашек.
Об уровнях
Простой: поле перемешано 24 случайными ходами, предел — вдвое длиннее кратчайшего решения. Аккуратная сборка по рядам обычно укладывается.
Сложный: 50 случайных ходов, предел в полтора раза длиннее кратчайшего. Здесь уже нужно думать на несколько фишек вперёд.
Эксперт: 150 случайных ходов — позиция почти случайная, кратчайшее решение обычно около 45–50 ходов, а предел всего на четверть длиннее. Компьютеру это стоит меньше секунды перебора; человеку — очень хорошей игры.