Уверен, многие из читающих иногда занимались на уроках бесполезной ерундой вместо того, чтобы слушать учителя. Я точно так делал, и одним из способов убить время были игры на бумаге. Особенно интересной мне казалась игра на превью (название которой мне до сих пор неизвестно), а причин тут две: она не требует второго человека и её можно завершить! Правда сделать это удавалось крайне редко. Долгое время мне было интересно, насколько простым может оказаться решение, и сейчас, спустя много лет, не составит труда найти его программным путём.
Правила
Для начала стоит описать правила. Начинается игра со следующего поля:
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 символов (то есть только одно решение). Это легко исправить, поигравшись с условиями в коде.
Спасибо за внимание!
Автор: ibessonov
