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


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


    Правила


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


    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 символов (то есть только одно решение). Это легко исправить, поигравшись с условиями в коде.


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

    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 36

      +1
      Иногда получалось решать её очень быстро, но сам не понимал как это сделал.
        0
        Один из известных, но не очень честных вариантов: на первом шаге не вычеркивать ни одной пары и сразу переписать всю последовательность второй раз. ЕМНИП решение занимает около 70 символов.
          +1

          ЕМНИП, дописывать таблицу можно лишь в том случае, когда вычёркивать нечего

            0
            Потому и «не очень честных». Но вообще, когда последовательность раздувается до 3-4 строк, к тому же растянутых на всю высоту тетрадной страницы, начинаются ошибки, о которых узнаешь только при переписывании.
              0

              Емнип, не обязательно. Очень хорошо помню момент, когда играл на компьютере в нее. Таблица сильно раздута, вроде всё вычеркнул, дописываешь таблицу и видишь, Что В строке подряд идут пары. Значит, где то выше ты их не вычеркнул. Проверяешь, и да, действительно так.

            +2

            Хм. Попробовать, что ли, прикинуть эвристику да формально применить A*, интересно смотрится...

              +1
              Помню мое разочарование в крестиках-ноликах на летних каникулах после третьего класса. Днем играл с родителями на песке на пляже. А вечером взял лист бумаги и больше в крестики-нолики не играл. Эту штуку тоже помню и тоже без названия. Было еще заполнение разных фигур на листе в клетку ходом коня, но сами фигуры память не сохранила. И как мы жили без всех этих гаджетов?..)
                0

                Если вариант крестиков-ноликов на почти бесконечном поле в виде тетрадного листа (ну или в квадрате типа 19*19, как у японцев) и необходимостью собрать линеечку из пяти клеток для выигрыша.

                  +1
                    +2
                    Рэндзю, но оно обычно играется на доске 15х15.
                    На доске 19х19 играется го.
                  +2
                  Лет 10 встетил эту игру, правда на компьютере, называлась она «Семечки». В пояснении было указано, что затягивает как семечки, отсюда и название. Правда или нет, не знаю.
                    0
                    Да, я тоже несколько лет назад ставил из Google play эту игру под названием «Семечки», возможно даже ту же самую, что и у вас.
                    Но в школе у нас она тоже без названия была.

                    Автору спасибо за ностальгию и интересный рисёрч :)
                      0
                      Тоже встречал такую на телефон, с таким же пояснением. А мы еще и играли, беря рандомную последовательность цифр
                      +2
                      кажется оптимальное решение можно построить на графах с очередью с приоритетами и обрезкой ветвей. Это будет много изящнее чем брутфорс :) Выглядит похожей на классические пятнашки с точки зрения алгоритма
                        0
                        Так у меня и так перебор на очереди с приоритетами) Только не до конца уверен, что имеется ввиду под обрезкой ветвей. Это как если просто ограничить количество ходов?
                          0
                          Честно говоря, я далёк от графов и иже с ними, но, полагаю, имеется ввиду, что отрезаются варианты, которые приводят к одному решению, так как нет никакого смысла перебирать одно и то же по одному «пути» для разных вариантов, даже если используется кэширование.
                          Как аналогию можно взять ветки деревьев. Если идти от их концов к стволу — то более мелкие ветки сливаются в одну.
                            +1
                            Предположу, что имеется в виду Alpha-Beta pruning? Если так, то к данной задаче такая обрезка, думаю, не применима. Решение этой задачи не сводится к минимакс-алгоритму.
                          +2
                          Ну вот. После вашей статьи у меня осталось на один тайм-киллер меньше…
                            0
                            У нас чаще в морской бой играли.
                              0
                              Морской бой нужно вдвоём играть, а это пасьянс для одного.
                              0
                              в своё время старший брат научил играть в эту игру, называл её «матрица». наверно, из схожести с падающими символами фильма)
                              к короткому решению я шел долго… но когда его увидел, даже растроился. как-то оно очевидно при должном внимании
                                0
                                я думаю, что все же из-за того, что это матрица чисел.
                                0
                                Хо-хо, школа, последняя парта и «номерки» — сколько тетрадок исписано в поисках короткого решения…
                                Тоже как-то заморочился лет 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)

                                  0
                                  Было уже =)
                                  habr.com/ru/post/130339

                                  Я для Windows Phone её пилил в то время для автора. До сих пор лежит архив с кодом.
                                    0
                                    минимальное количество ходов 23, ищите дальше
                                      +1
                                      Позвольте выразить своё сомнение в том, что решение в статье не самое короткое.
                                        0
                                        Поддерживаю. Нет решения (полным перебором с ограничениями) короче 8 строк (см. выше). Разумеется, если соблюдать правила. В моем (выше) — 35 ходов, у вас — 33(?).

                                        Только не до конца уверен, что имеется ввиду под обрезкой ветвей. Это как если просто ограничить количество ходов?

                                        Ну а почему нет? Это тоже вполне себе метод ветвей и границ. Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.

                                        чтобы перебор был осмысленным и быстрым, лучше использовать очередь с приоритетом. Чем меньше на поле цифр (включая вычеркнутые), тем раньше такую конфигурацию следует рассматривать;

                                        Это, пмсм, не самое верное решение. Так будет найден локальный минимум. Условно говоря — на данном шаге у нас осталось всего 3 числа, но при последующих дописываниях мы вырастем до 20. А другой вариант оставит 4 числа, но потом сразу «схлопнется» — толку рассматривать первый вариант раньше?

                                        Shersh это же просто игра «в цифре»? У автора данной статьи — поиск короткого решения.
                                          0
                                          Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.

                                          Собственно, я так и поступал.


                                          Это, пмсм, не самое верное решение. Так будет найден локальный минимум.

                                          Знаю, именно поэтому после нахождения первого попавшегося решения я перебирал все более короткие ветки, чтобы узнать, не пропустил ли чего. В начале у меня приоритет в очереди был по другому признаку и первым было найдено решение в 86 цифр.


                                          Наверное, нужно было отразить это в тексте, спасибо!

                                      0
                                      А я её на Дельфи делал, ещё в доинтернетные времена, никак не распространял, кроме пары знакомых в локальной сети общежития, а потом лет через десять вдруг один случайный знакомый узнав моё имя показал мне мою игру, которую он выудил со спутника и играл.
                                      Я к тому времени уже и правила позабыл.
                                        0
                                        Мне кажется, или в анимации решения несколько раз вычеркиваются цирфы, стоящие ни последовательно, ни друг над другом? Да хотя бы последние две пары.
                                          0
                                          Все ходы верны и взяты из расшифровки в конце статьи, только порядок слегка изменён. Последние 2 пары (3, 7) и (2, 8) стоят как раз последовательно.
                                            0
                                            Я понял. Не уловил сразу, что уже зачеркнутые не учитываются.
                                            Спасибо.
                                          0
                                          Обманул, не за 23 хода, а за 26 можно закончить игру
                                          image
                                            0

                                            В вашей версии игры, по какой-то причине, можно переписывать числа в конец даже тогда, когда ещё есть другие доступные ходы. Получается, что у вас другой набор правил, который я никогда не рассматривал. Так что да, при этом условии может существовать более короткое решение, верю.

                                              +1
                                              Все правильно — по классике как в шашках — можно зачеркнуть — надо зачеркнуть. А так-то да, решение в 6 строк — известный читерский вариант.
                                            0
                                            Я тоже играла в эту игру. Забавно было, интересно. И время шло незаметно

                                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                            Самое читаемое