ИгрыХабрахабр

Тайм-киллер из детства

Я точно так делал, и одним из способов убить время были игры на бумаге. Уверен, многие из читающих иногда занимались на уроках бесполезной ерундой вместо того, чтобы слушать учителя. Правда сделать это удавалось крайне редко. Особенно интересной мне казалась игра на превью (название которой мне до сих пор неизвестно), а причин тут две: она не требует второго человека и её можно завершить! Долгое время мне было интересно, насколько простым может оказаться решение, и сейчас, спустя много лет, не составит труда найти его программным путём.

Правила

Начинается игра со следующего поля: Для начала стоит описать правила.

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. Нет, решения совсем не редки. Вообще, мне удалось найти 30 решений длиной до 90 (включительно), а если границу увеличить до 100, то решений будет уже 170. А ещё 4 принципиально различных решения длиной 80. Дальше ещё больше, но и искать их становится затратнее.

Под спойлером оптимальное решение расписано подробно:

Скрытый текст

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 символов (то есть только одно решение).

Спасибо за внимание!

Показать больше

Похожие публикации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»