Уверен, многие из читающих иногда занимались на уроках бесполезной ерундой вместо того, чтобы слушать учителя. Я точно так делал, и одним из способов убить время были игры на бумаге. Особенно интересной мне казалась игра на превью (название которой мне до сих пор неизвестно), а причин тут две: она не требует второго человека и её можно завершить! Правда сделать это удавалось крайне редко. Долгое время мне было интересно, насколько простым может оказаться решение, и сейчас, спустя много лет, не составит труда найти его программным путём.
Правила
Для начала стоит описать правила. Начинается игра со следующего поля:
123456789
111213141
516171819
Здесь посимвольно записаны все числа от 1 до 19, за исключением 10. Цифры расположены слева направо, строка за строкой. Правила довольно просты — на каждом шаге нужно вычеркнуть 2 цифры, соответствующие следующим критериям:
- цифры должны быть либо одинаковыми, либо в сумме давать 10 (1 и 1, 3 и 7, 8 и 2 и т.д.);
- так же они должны либо стоять друг над другом, либо располагаться последовательно. При этом уже вычеркнутые цифры игнорируются.
Ниже показан один из вариантов нескольких первых ходов:
123456789
111213141
516171819
#23456789
#11213141
5161718##
#2345678#
##1213141
5161718##
В тот момент, когда ходов больше нет, все невычеркнутые цифры дописываются в конец. Игра заканчивается, когда всё поле будет вычеркнуто.
#2345678#
##1213141
5161718##
234567812
131415161
718
#2345678#
##1213141
51#171###
23#567#12
131415161
718
#2345678#
##1213#41
5###71###
23#567#12
131415#61
718
...
Количество доступных ходов стремительно увеличивается, игра начинает сильно ветвиться. Зачастую таблица становится настолько длинной, что переполняется на следующую страницу в тетради. Проще начать новую партию. Иногда я из упорства продолжал, но в итоге сдавался.
Тут встаёт резонный вопрос — а насколько быстро можно закончить эту игру? В детстве удавалось найти решение в один столбик на тетрадном листе — это порядка 40 строк или 360 символов.
Гарантированного способа завершить игру мне не известно. Совершенно не понятно, как выбирать стратегию. Можете попробовать сыграть сами, если не пробовали.
Решение
Каким образом ищутся решения у подобных проблем? Не знаю наверняка, но я выбрал обычный перебор.
Нам понадобится очередь, сперва состоящая только из единственной начальной конфигурации. На каждом шаге мы берём следующую конфигурацию из очереди, смотрим все доступные из неё ходы и либо добавляем их все в конец очереди, либо объявляем себя победителем, если таких ходов нет.
123456789 #23456789 12345678# 123456789 123456789 123456789 123456789 ...
111213141 #11213141 #11213141 ##1213141 1##213141 11#213141 11121314# ...
516171819 516171819 516171819 516171819 516171819 516#71819 51617181# ...
Если не останавливаться на первом попавшемся решении, то данный алгоритм будет выдавать все возможные решения (при наличии бесконечного объёма оперативной памяти).
На практике настолько наивный подход совершенно не поможет, как минимум, из-за постоянно появляющихся дубликатов в очереди. Поэтому потребуются некоторые оптимизации, которые я сейчас объясню:
- естественно, конфигурации нужно кэшировать, чтобы не складывать их повторно в очередь. Это сильно увеличит использование памяти, но всё равно не поможет получить решение за приемлемое время. Более того, остро встаёт вопрос сравнения конфигураций. Раз две выигрышные конфигурации одного размера всегда будут состоять только из зачёркнутых чисел, то нужен дополнительный способ их отличать, иначе будут найдены не все решения;
- чтобы перебор был осмысленным и быстрым, лучше использовать очередь с приоритетом. Чем меньше на поле цифр (включая вычеркнутые), тем раньше такую конфигурацию следует рассматривать;
- если нужно не одно решение, а много, то лучше ограничить максимальное количество цифр на поле, перебор станет выдавать решения намного раньше.
Ответ
Если правильно всё закодить, выясняется, что минимальное решение состоит всего из 68 символов или 8 строк!
Приведу его в виде gif-анимации. Некоторые ходы были склеены в один, чтобы уменьшить число кадров:
Буду откровенен, меня поразило, насколько это решение короткое. Но, может быть, это везение и остальные решения встретятся нескоро и будут очень длинными?
Нет, решения совсем не редки. Быстро находятся ответы длиной 72, 74 и 76. А ещё 4 принципиально различных решения длиной 80. Вообще, мне удалось найти 30 решений длиной до 90 (включительно), а если границу увеличить до 100, то решений будет уже 170. Дальше ещё больше, но и искать их становится затратнее.
Под спойлером оптимальное решение расписано подробно:
123456789
111213141
516171819
123456789
111213141
5161718##
123456789
1##213141
5161718##
12345678#
1##21314#
5161718##
#2345678#
###21314#
5161718##
#234567##
####1314#
5161718##
#234567##
####1314#
5161718##
234567131
45161718
#234567##
####1314#
51#1718##
23#567131
45161718
#234567##
####1314#
51#171###
#3#567131
45161718
#234567##
####1314#
51#171###
#3#567#31
451617#8
#234567##
####1314#
51#171###
#3#56###1
451617#8
#234567##
####1314#
5###71###
#3#56###1
451617#8
#234567##
####1314#
5###71###
#3#56###1
451617#82
345671314
571356145
16178
#234567##
####1314#
5###71###
#3#56###1
451617#82
345671314
57#356145
16#78
#234567##
####1314#
5###71###
#3#56###1
451617#82
345671314
5###56145
16#78
#234567##
####1314#
5###71###
#3#56###1
451617#82
345671314
#####6145
16#78
#234567##
####1314#
5###71###
#3#56###1
451617#82
34567131#
######145
16#78
#234567##
####1314#
5###71###
#3#56###1
451617#82
3456713##
#######45
16#78
#234567##
####1314#
5###71###
#3#56###1
451617#82
3#56713##
#######45
1##78
#234567##
####1314#
5###71###
#3#56###1
451617###
3#56713##
#######45
1##78
#234567##
####1314#
5###71###
#3#56###1
45161####
##56713##
#######45
1##78
#234567##
####1314#
5###7####
#3#56###1
45161####
##567#3##
#######45
1##78
#234567##
####1314#
5########
###56###1
45161####
##567#3##
#######45
1##78
#234567##
####1314#
#########
####6###1
45161####
##567#3##
#######45
1##78
#234567##
####1314#
#########
####6###1
45161####
##56#####
#######45
1##78
#234567##
####1314#
#########
####6###1
45161####
##5######
########5
1##78
#234567##
####1314#
#########
####6###1
45161####
#########
#########
1##78
#234567##
####131##
#########
########1
45161####
#########
#########
1##78
#234567##
####13###
#########
#########
45161####
#########
#########
1##78
#234567##
#####3###
#########
#########
4516#####
#########
#########
1##78
#23456###
#########
#########
#########
4516#####
#########
#########
1##78
#2345####
#########
#########
#########
#516#####
#########
#########
1##78
#234#####
#########
#########
#########
##16#####
#########
#########
1##78
#23######
#########
#########
#########
##1######
#########
#########
1##78
#23######
#########
#########
#########
#########
#########
#########
###78
#2#######
#########
#########
#########
#########
#########
#########
####8
#########
#########
#########
#########
#########
#########
#########
#####Мой код решения на Java можно посмотреть по этой ссылке, но предупреждаю, что он ужасен, т.к. изначально писался не для публикации. В текущем виде он находит все решения до 70 символов (то есть только одно решение). Это легко исправить, поигравшись с условиями в коде.
Спасибо за внимание!
Комментарии (34)
knowy
16.10.2019 03:17Один из известных, но не очень честных вариантов: на первом шаге не вычеркивать ни одной пары и сразу переписать всю последовательность второй раз. ЕМНИП решение занимает около 70 символов.
trawl
16.10.2019 04:40ЕМНИП, дописывать таблицу можно лишь в том случае, когда вычёркивать нечего
knowy
16.10.2019 05:13Потому и «не очень честных». Но вообще, когда последовательность раздувается до 3-4 строк, к тому же растянутых на всю высоту тетрадной страницы, начинаются ошибки, о которых узнаешь только при переписывании.
Cerberuser
16.10.2019 04:47Хм. Попробовать, что ли, прикинуть эвристику да формально применить A*, интересно смотрится...
x-tea
16.10.2019 08:00Помню мое разочарование в крестиках-ноликах на летних каникулах после третьего класса. Днем играл с родителями на песке на пляже. А вечером взял лист бумаги и больше в крестики-нолики не играл. Эту штуку тоже помню и тоже без названия. Было еще заполнение разных фигур на листе в клетку ходом коня, но сами фигуры память не сохранила. И как мы жили без всех этих гаджетов?..)
lgorSL
16.10.2019 13:07Если вариант крестиков-ноликов на почти бесконечном поле в виде тетрадного листа (ну или в квадрате типа 19*19, как у японцев) и необходимостью собрать линеечку из пяти клеток для выигрыша.
Drugged_Monkey
16.10.2019 15:10Рэндзю, но оно обычно играется на доске 15х15.
На доске 19х19 играется го.
broken_brain
16.10.2019 08:00Лет 10 встетил эту игру, правда на компьютере, называлась она «Семечки». В пояснении было указано, что затягивает как семечки, отсюда и название. Правда или нет, не знаю.
skymal4ik
16.10.2019 09:12Да, я тоже несколько лет назад ставил из Google play эту игру под названием «Семечки», возможно даже ту же самую, что и у вас.
Но в школе у нас она тоже без названия была.
Автору спасибо за ностальгию и интересный рисёрч :)
Krenodator
16.10.2019 21:10Тоже встречал такую на телефон, с таким же пояснением. А мы еще и играли, беря рандомную последовательность цифр
AlexeyTokar
16.10.2019 12:24+1кажется оптимальное решение можно построить на графах с очередью с приоритетами и обрезкой ветвей. Это будет много изящнее чем брутфорс :) Выглядит похожей на классические пятнашки с точки зрения алгоритма
ibessonov Автор
16.10.2019 12:33Так у меня и так перебор на очереди с приоритетами) Только не до конца уверен, что имеется ввиду под обрезкой ветвей. Это как если просто ограничить количество ходов?
Asethon
16.10.2019 16:47Честно говоря, я далёк от графов и иже с ними, но, полагаю, имеется ввиду, что отрезаются варианты, которые приводят к одному решению, так как нет никакого смысла перебирать одно и то же по одному «пути» для разных вариантов, даже если используется кэширование.
Как аналогию можно взять ветки деревьев. Если идти от их концов к стволу — то более мелкие ветки сливаются в одну.
AndreySitaev
16.10.2019 20:12Предположу, что имеется в виду Alpha-Beta pruning? Если так, то к данной задаче такая обрезка, думаю, не применима. Решение этой задачи не сводится к минимакс-алгоритму.
mctMaks
16.10.2019 15:11в своё время старший брат научил играть в эту игру, называл её «матрица». наверно, из схожести с падающими символами фильма)
к короткому решению я шел долго… но когда его увидел, даже растроился. как-то оно очевидно при должном внимании
MacIn
16.10.2019 17:09Хо-хо, школа, последняя парта и «номерки» — сколько тетрадок исписано в поисках короткого решения…
Тоже как-то заморочился лет 7 назад программным поиском решения.
Но мое решение (тоже 8 строк, искал минимальное по строкам, не зачеркиваниям) иное:
Maximum 8 rows.
Started at 11/3/2012 4:46:22 AM
Step 16@ 11/3/2012 4:46:22 AM 1 of 0
...
Step 3@ 11/3/2012 4:52:44 AM 1 of 7
Found solution - 35 steps.
Finished by 11/3/2012 5:01:55 AM
(1, 1) and (1, 2)
(9, 1) and (2, 2)
(9, 2) and (9, 3)
~2345678~
~~121314~
51617181~
234567812
131451617
181~~~~~~
(3, 3) and (3, 4)
(2, 3) and (4, 3)
(8, 3) and (8, 4)
(7, 3) and (1, 4)
(7, 4) and (9, 4)
(1, 5) and (1, 6)
(6, 4) and (2, 5)
(6, 3) and (6, 5)
(5, 3) and (2, 4)
(2, 1) and (2, 6)
(1, 3) and (4, 4)
(8, 2) and (5, 4)
(7, 2) and (3, 5)
(3, 2) and (3, 6)
(8, 1) and (4, 2)
(4, 1) and (4, 5)
~~3~567~~
~~~~13~~~
~~~~~~~~~
~~~~~~~~~
~~~~5~617
~~~356713
5617~~~~~
(5, 5) and (5, 6)
(8, 5) and (8, 6)
(9, 5) and (9, 6)
(4, 6) and (4, 7)
(7, 5) and (6, 6)
(6, 2) and (7, 6)
~~3~567~~
~~~~1~~~~
~~~~~~~~~
~~~~~~~~~
~~~~~~~~~
~~~~~~~~~
561~35671
561~~~~~~
(1, 7) and (1, 8)
(2, 7) and (2, 8)
(5, 2) and (3, 7)
(7, 1) and (5, 7)
(9, 7) and (3, 8)
~~3~56~~~
~~~~~~~~~
~~~~~~~~~
~~~~~~~~~
~~~~~~~~~
~~~~~~~~~
~~~~~567~
~~~356567
(5, 1) and (5, 8)
(8, 7) and (4, 8)
(7, 7) and (6, 8)
(6, 7) and (7, 8)
(6, 1) and (8, 8)
(3, 1) and (9, 8)
Shersh
16.10.2019 17:48Было уже =)
habr.com/ru/post/130339
Я для Windows Phone её пилил в то время для автора. До сих пор лежит архив с кодом.
Nad73
16.10.2019 18:42минимальное количество ходов 23, ищите дальше
ibessonov Автор
16.10.2019 18:52+1Позвольте выразить своё сомнение в том, что решение в статье не самое короткое.
MacIn
16.10.2019 21:18Поддерживаю. Нет решения (полным перебором с ограничениями) короче 8 строк (см. выше). Разумеется, если соблюдать правила. В моем (выше) — 35 ходов, у вас — 33(?).
Только не до конца уверен, что имеется ввиду под обрезкой ветвей. Это как если просто ограничить количество ходов?
Ну а почему нет? Это тоже вполне себе метод ветвей и границ. Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.
чтобы перебор был осмысленным и быстрым, лучше использовать очередь с приоритетом. Чем меньше на поле цифр (включая вычеркнутые), тем раньше такую конфигурацию следует рассматривать;
Это, пмсм, не самое верное решение. Так будет найден локальный минимум. Условно говоря — на данном шаге у нас осталось всего 3 числа, но при последующих дописываниях мы вырастем до 20. А другой вариант оставит 4 числа, но потом сразу «схлопнется» — толку рассматривать первый вариант раньше?
Shersh это же просто игра «в цифре»? У автора данной статьи — поиск короткого решения.ibessonov Автор
16.10.2019 21:24Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.
Собственно, я так и поступал.
Это, пмсм, не самое верное решение. Так будет найден локальный минимум.
Знаю, именно поэтому после нахождения первого попавшегося решения я перебирал все более короткие ветки, чтобы узнать, не пропустил ли чего. В начале у меня приоритет в очереди был по другому признаку и первым было найдено решение в 86 цифр.
Наверное, нужно было отразить это в тексте, спасибо!
Goodkat
16.10.2019 18:46А я её на Дельфи делал, ещё в доинтернетные времена, никак не распространял, кроме пары знакомых в локальной сети общежития, а потом лет через десять вдруг один случайный знакомый узнав моё имя показал мне мою игру, которую он выудил со спутника и играл.
Я к тому времени уже и правила позабыл.
AlexVic
16.10.2019 21:08Мне кажется, или в анимации решения несколько раз вычеркиваются цирфы, стоящие ни последовательно, ни друг над другом? Да хотя бы последние две пары.
Nad73
17.10.2019 22:27Обманул, не за 23 хода, а за 26 можно закончить игру
ibessonov Автор
17.10.2019 22:31В вашей версии игры, по какой-то причине, можно переписывать числа в конец даже тогда, когда ещё есть другие доступные ходы. Получается, что у вас другой набор правил, который я никогда не рассматривал. Так что да, при этом условии может существовать более короткое решение, верю.
MacIn
17.10.2019 23:52Все правильно — по классике как в шашках — можно зачеркнуть — надо зачеркнуть. А так-то да, решение в 6 строк — известный читерский вариант.
kotov666
Иногда получалось решать её очень быстро, но сам не понимал как это сделал.