Цель игры — перемещая костяшки по коробке, добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений. Мы же будем добиваться наименьшего времени.
Как такового способа нет, но мы рассмотрим алгоритм для новичков, который позволит собирать за 20 секунд.
Первое, что нам необходимо сделать, это поставить 1 и 2 на своё место. Я думаю это у вас не составит труда.
Далее идёт пара 3 и 4. Здесь уже могут появиться трудности, например если вы поставили 1,2 и 3, то как же поставить 4? Всё очень просто! Мы ставим 3 на место 4 (или 4 на место 3) и ставим 4 под 3 (3 под 4), освобождаем место рядом и сдвигаем 3 и 4 в одну линию. Подробнее на картинках ->
У нас собран один ряд! Далее собираем ряд слева. Ставим 5 на своё место, а с 9 и 13 производим действия аналогичные тем, которые использовали с 3 и 4.
Как вы видите, теперь мы превратили 15-Puzzle в 8-Puzzle.
Их мы будем собирать аналогично. Посмотрите и сравните
Ставим 6 на своё место, 8 на место 7, 7 под 8, освобождаем место справа. Получаем линию.
Как Собрать Пятнашки | Самый Простой Способ
Далее ставим 14 на место 10, а 10 справа от 14.
Двигаем 14 вниз, и ставим 10 на своё место. И что же мы видим? Осталось только 3 числа, которые уже не составит труда передвинуть.
А теперь давайте попробуем на скорость.
Как вы видите — 16 секунд, как я и обещал! Если у вас не так, то просто потренируйтесь и у вас обязательно получится!
Что же делать, когда стабильно менее 20 секунд?
Профессионалы советуют применять в сборках «Фринж».
Фринж — это вариант последовательности сборки, который считается наиболее оптимальным и быстрым.
1. Собираются 1 2 3 4 или 1 5 9 13
2. Собирается 1 5 9 13 или 1 2 3 4
3. Собираются 6 7 8, или 6 10 14
4. Собираются последние 3 элемента
Надеюсь вы поняли, что пятнашки не только детская игра, но и отличный вариант для развития мышления.
Если вам интересна данная тема, то проявите активность и я сделаю ещё статью.
Источник: dzen.ru
А* для нахождения решения «пятнашек»
2012-09-29 в 22:38, admin , рубрики: java, Алгоритмы, пятнашки, метки: пятнашки
Задача
Наша задача на сегодня состоит в нахождении решения игры «пятнашки». И не любое, а за наименьшее количество ходов. Надо же удивить ребенка тем, что вы умеете ее собирать за 10 ходов!
Пятна́шки — популярная головоломка, придуманная в 1878 году Ноем Чепмэном. Представляет собой набор одинаковых квадратных костяшек с нанесёнными числами, заключённых в квадратную коробку. Длина стороны коробки в четыре раза больше длины стороны костяшек для набора из 15 элементов (и в три раза больше для набора в 8 элементов), соответственно в коробке остаётся незаполненным одно квадратное поле. Цель игры — перемещая костяшки по коробке добиться упорядочивания их по номерам, желательно сделав как можно меньше перемещений.
Описанное здесь решение этой задачи — это реализация одного из Programming Assignments из курса по алгоритмам на coursera.org. Этот курс закончился неделю назад, так что думаю что решение можно публиковать.
Как собрать Пятнашки? Скоростная сборка 15-Puzzle!
Схема решения
Задача годится для учебника по А*. Про сам алгоритм писать не буду, все уже описано в википедии и даже с примерами кода.
В нашем частном случае алгоритм выглядит так:
1. Кладем в очередь с приоритетом первоначальную позицию.
2. Извлекаем из очереди позицию с наименьшим приоритетом.
3. Кладем в очередь все соседние позиции.
4. Повторяем пункты 2-4 пока в пункте 2 не вытащим конечную позицию.
Важно отметить, что в пункте 3 мы кладем не просто позиции сами по себе, а пути, которые привели к данной позиции. То есть наша очередь всегда содержит пути.
Все просто. Правда, для полной ясности надо прояснить, как мы будем определять наименьший приоритет (то есть надо определить нашу эвристическуя функцию). Обратимся опять к википедии:
Порядок обхода вершин определяется эвристической функцией «расстояние + стоимость» (обычно обозначаемой как f(x)). Эта функция — сумма двух других: функции стоимости достижения рассматриваемой вершины (x) из начальной (обычно обозначается как g(x) и может быть как эвристической, так и нет) и эвристической оценкой расстояния от рассматриваемой вершины к конечной (обозначается как h(x)).
В нашем случае возьмем g(x) равной количеству ходов, которые привели к текушей позиции x.
А h(x) возьмем равной количеству клеток, стоящих не на своем месте.
Например, для позиции
1 2 3
4 5 6
7 8
h(x) = 0, а для
1 2 3 4 5 6 7 8
h(x) = 1, так как 8 не на своем месте.
Почему опредляем так? Трудно сказать. Да и не надо — на то f(x) и эвристическая.
Но нам было важно оценить расстояние до цели (при этом мы можем его недооценить, но не наоборот). Наш способ вполне подходит, ходов в любом случае будет не меньше чем h(x).
Напомню, что А* находит кратчайший путь за полиномиальное время, но потребление памяти растет экспоненциально.
Реализация
Реализация — на джаве.
Для начала создадим класс, который является «доской». Экземпляр такого класса будет хранить одно состояние доски, то есть одну позицию:
Дальше, без лишних слов перейдем к реализации А*:
Solver
Тут еще можно сказать несколько слов о методе isSolvable(). В википедии и даже на хабре описана формула, по которой можно легко посчитать — существует решение или нет.
Заключение
Взяв два вышеописанных класса, вы легко сможете находить решение «пятняшек» за минимальное количество ходов. Для этого необходимо создать изначальную позицию и создать Solver:
int[][] blocks = new int[][], , >; Board initial = new Board(blocks); Solver solver = new Solver(initial);
после чего, можно просто выводить решение:
System.out.println(«Minimum number of moves = » + solver.moves()); for (Board board : solver.solution()) System.out.println(board);
В данном случае получится так:
Minimum number of moves = 2 1 2 3 4 0 5 7 8 6 1 2 3 4 5 0 7 8 6 1 2 3 4 5 6 7 8 0
Или можно чуть иначе:
int[][] blocks = new int[][], , , >; Board initial = new Board(blocks); Solver solver = new Solver(initial);
Тогда решение будет выглядеть подлиннее…
Minimum number of moves = 19
1 2 3 0
5 6 7 8
9 10 11 12
13 14 15 4
1 2 0 3
5 6 7 8
9 10 11 12
13 14 15 4
1 2 7 3
5 6 0 8
9 10 11 12
13 14 15 4
1 2 7 3
5 6 8 0
9 10 11 12
13 14 15 4
1 2 7 3
5 6 8 12
9 10 11 0
13 14 15 4
1 2 7 3
5 6 8 12
9 10 11 4
13 14 15 0
1 2 7 3
5 6 8 12
9 10 11 4
13 14 0 15
1 2 7 3
5 6 8 12
9 10 0 4
13 14 11 15
1 2 7 3
5 6 0 12
9 10 8 4
13 14 11 15
1 2 7 3
5 6 12 0
9 10 8 4
13 14 11 15
1 2 7 3
5 6 12 4
9 10 8 0
13 14 11 15
1 2 7 3
5 6 12 4
9 10 0 8
13 14 11 15
1 2 7 3
5 6 0 4
9 10 12 8
13 14 11 15
1 2 0 3
5 6 7 4
9 10 12 8
13 14 11 15
1 2 3 0
5 6 7 4
9 10 12 8
13 14 11 15
1 2 3 4
5 6 7 0
9 10 12 8
13 14 11 15
1 2 3 4
5 6 7 8
9 10 12 0
13 14 11 15
1 2 3 4
5 6 7 8
9 10 0 12
13 14 11 15
1 2 3 4
5 6 7 8
9 10 11 12
13 14 0 15
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
Источник: www.pvsm.ru
Saved searches
Use saved searches to filter your results more quickly
Cancel Create saved search
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window.
Reload to refresh your session.
Универсальный решатель пятнашек
License
pomponchik/n_puzzle
This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
Switch branches/tags
Branches Tags
Could not load branches
Nothing to show
Could not load tags
Nothing to show
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Cancel Create
- Local
- Codespaces
HTTPS GitHub CLI
Use Git or checkout with SVN using the web URL.
Work fast with our official CLI. Learn more about the CLI.
Sign In Required
Please sign in to use Codespaces.
Launching GitHub Desktop
If nothing happens, download GitHub Desktop and try again.
Launching GitHub Desktop
If nothing happens, download GitHub Desktop and try again.
Launching Xcode
If nothing happens, download Xcode and try again.
Launching Visual Studio Code
Your codespace will open once ready.
There was a problem preparing your codespace, please try again.
Latest commit
03add52 Sep 8, 2022
Git stats
Files
Failed to load latest commit information.
Latest commit message
Commit time
September 8, 2022 21:24
February 9, 2022 22:19
September 5, 2022 01:12
February 9, 2022 22:19
February 7, 2022 23:58
September 8, 2022 21:29
February 9, 2022 22:19
September 8, 2022 21:24
README.md
NPuzzle — решатель пятнашек
Есть такая игра из жанра комбинаторных — пятнашки. В ней игроку дается поле 4 на 4, на котором расположены 15 квадратиков с числами от 1 до 15 и еще один пустой слот. Задача игрока — сдвигать квадратики с числами на этот пустой слот до тех пор, пока числа не окажутся выстроенными в нужном порядке.
У данной игры есть вариации, чаще всего связанные с размером поля (бывает не только 4 на 4, но и, к примеру, 5 на 5, или 3 на 3) или с порядком чисел, к которому по итогу нужно придти.
Алгоритмическое решение здесь сложно тем, что каждое действие игрока изменяет игровое поле. Поэтому обычно задачу решают с помощью алгоритмов поиска пути (чаще всего это вариации вокруг A*), где программа «путешествует» по веткам изменений состояния поля. При этом на каждом шаге из нескольких вариантов мы выбираем тот, в котором наша оценка «ошибки» минимальна. Ошибка вычисляется при помощи эвристик, из которых самая популярная — манхэттенское расстояние.
В данной реализации используется алгоритм A*, а эвристик на выбор предлагается 4 штуки. Итоговый порядок расстановки чисел не обычный линейный, а спиральный.
Программа запускается и выводит результаты своей работы через консоль. Для запуска необходимо подать ей на вход путь к файлу, в котором описано стартовое состояние игрового поля, например вот так:
python3 npuzzle.py examples/5.txt
Но я советую вместо стандартного интерпретатора использовать pypy, обычно это ускоряет решение примерно в 100 раз.
Содержимое файла должно выглядеть примерно так:
# This puzzle is solvable 4 14 7 15 2 5 8 10 1 12 4 3 11 0 13 6 9
На первой строчке здесь указан размер игрового поля (то есть у поля размером 5 на 5 там будет 5), а последующие просто описывают расположение чисел на поле. Пустая клеточка здесь обозначается нулем.
Результат выводится в виде последовательности состояний поля, примерно вот так (здесь приведен только конец вывода для приведенного выше поля, поскольку иначе это заняло бы очень много места):
. 1 2 3 4 12 13 14 5 10 11 15 6 9 0 8 7 | V 1 2 3 4 12 13 14 5 10 11 15 6 0 9 8 7 | V 1 2 3 4 12 13 14 5 0 11 15 6 10 9 8 7 | V 1 2 3 4 12 13 14 5 11 0 15 6 10 9 8 7 Complexity in time: 13035 Complexity in size: 6699 Number of moves: 500
Текст, который выводится в конце, позволяет оценить масштаб вычислений, которые пришлось проделать программе, чтобы придти к решению. «Complexity in time» — это общее число комбинаций полей, которое было просмотрено. «Complexity in size» — это максимальное число полей, которые одновременно лежали в очереди с приоритетом (чтобы узнать, зачем нужна эта очередь — читайте, как устроен алгоритм A*). «Number of moves» — итоговое число перестановок на поле, которое нужно, чтобы привести его в желаемое состояние.
По умолчанию для оценки поля программа использует эвристику «base». Она просто подсчитывает, сколько чисел в данный момент находятся не на своих местах (так называемое «расстояние Хэмминга»). Но поддерживаются еще 3 эвристики: «manhattan», «manhattan+» и «all». Указать эвристику можно передачей ее названия в качестве еще одного аргумента при запуске программы:
python3 npuzzle.py examples/5.txt manhattan
Эвристика «manhattan» подсчитывает классическое манхэттенское расстояние для каждого числа между его «идеальным» положением на поле (то есть таким, которого мы хотим добиться) и положением в данный момент. Сумма таких расстояний представляет собой оценку текущего отклонения поля от идеального состояния. Чем оно больше — тем хуже, а в идеале оно должно быть равно нулю.
Эвристика «manhattan+» еще прибавляет к оценке текущего состояния поля количество шагов, которые пришлось сделать, чтобы к нему придти. Если A* c обычным «manhattan» — это так называемый жадный алгоритм, то с данной его вариацией — уже нет.
Различные эвристики могут давать разные результаты и требовать разного объема вычислений. К примеру, для приведенного выше поля эвристика «manhattan» выдает:
Complexity in time: 1943 Complexity in size: 1124 Number of moves: 172
Как видим, количество шагов сократилось примерно в 3 раза, также сильно упало число просмотренных вариантов. И сравним это с «manhattan+»:
Complexity in time: 984296 Complexity in size: 509626 Number of moves: 84
Бросается в глаза, что, хоть мы и сократили количество шагов более чем в 2 раза, для этого пришлось проделать драматически больше работы — примерно в 500 раз. К слову, если на предыдущих эвристиках на моем компьютере (MacBook Air на m1) все считалось практически мгновенно, то тут ему пришлось заметно попотеть, на вычисления ушли примерно 1 час и 10 минут (на pypy — 1 минута и 20 секунд).
Последняя из эвристик — «all». Она является просто суммой всех прочих эвристик, но вес «manhattan» в ней удвоен — как выяснилось опытным путем, это резко повышает ее эффективность. Попробуем:
Complexity in time: 766392 Complexity in size: 393465 Number of moves: 70
Как видим, она выдала самое маленькое количество шагов, причем на это ушло меньше вычислений, чем на «manhattan+», но все еще намного больше, чем на просто «manhattan».
Проверка поля на валидность
Решателя пятнашек легко завести в тупик. Для этого достаточно поменять местами числа в любых двух соседних клетках. В этом случае, как бы он ни перемещал числа по полю, он никогда не придет к правильному порядку. В данной программе перед запуском основного алгоритма происходит соответствующая проверка. Если поле ее не прошло, появится следующее сообщение:
This version of puzzle is unsolvable.
Источник: github.com