Комментарии 36
Иногда получалось решать её очень быстро, но сам не понимал как это сделал.
Один из известных, но не очень честных вариантов: на первом шаге не вычеркивать ни одной пары и сразу переписать всю последовательность второй раз. ЕМНИП решение занимает около 70 символов.
ЕМНИП, дописывать таблицу можно лишь в том случае, когда вычёркивать нечего
Потому и «не очень честных». Но вообще, когда последовательность раздувается до 3-4 строк, к тому же растянутых на всю высоту тетрадной страницы, начинаются ошибки, о которых узнаешь только при переписывании.
Емнип, не обязательно. Очень хорошо помню момент, когда играл на компьютере в нее. Таблица сильно раздута, вроде всё вычеркнул, дописываешь таблицу и видишь, Что В строке подряд идут пары. Значит, где то выше ты их не вычеркнул. Проверяешь, и да, действительно так.
Хм. Попробовать, что ли, прикинуть эвристику да формально применить A*, интересно смотрится...
Помню мое разочарование в крестиках-ноликах на летних каникулах после третьего класса. Днем играл с родителями на песке на пляже. А вечером взял лист бумаги и больше в крестики-нолики не играл. Эту штуку тоже помню и тоже без названия. Было еще заполнение разных фигур на листе в клетку ходом коня, но сами фигуры память не сохранила. И как мы жили без всех этих гаджетов?..)
Лет 10 встетил эту игру, правда на компьютере, называлась она «Семечки». В пояснении было указано, что затягивает как семечки, отсюда и название. Правда или нет, не знаю.
Да, я тоже несколько лет назад ставил из Google play эту игру под названием «Семечки», возможно даже ту же самую, что и у вас.
Но в школе у нас она тоже без названия была.
Автору спасибо за ностальгию и интересный рисёрч :)
Но в школе у нас она тоже без названия была.
Автору спасибо за ностальгию и интересный рисёрч :)
Тоже встречал такую на телефон, с таким же пояснением. А мы еще и играли, беря рандомную последовательность цифр
кажется оптимальное решение можно построить на графах с очередью с приоритетами и обрезкой ветвей. Это будет много изящнее чем брутфорс :) Выглядит похожей на классические пятнашки с точки зрения алгоритма
Так у меня и так перебор на очереди с приоритетами) Только не до конца уверен, что имеется ввиду под обрезкой ветвей. Это как если просто ограничить количество ходов?
Честно говоря, я далёк от графов и иже с ними, но, полагаю, имеется ввиду, что отрезаются варианты, которые приводят к одному решению, так как нет никакого смысла перебирать одно и то же по одному «пути» для разных вариантов, даже если используется кэширование.
Как аналогию можно взять ветки деревьев. Если идти от их концов к стволу — то более мелкие ветки сливаются в одну.
Как аналогию можно взять ветки деревьев. Если идти от их концов к стволу — то более мелкие ветки сливаются в одну.
Предположу, что имеется в виду Alpha-Beta pruning? Если так, то к данной задаче такая обрезка, думаю, не применима. Решение этой задачи не сводится к минимакс-алгоритму.
Ну вот. После вашей статьи у меня осталось на один тайм-киллер меньше…
У нас чаще в морской бой играли.
в своё время старший брат научил играть в эту игру, называл её «матрица». наверно, из схожести с падающими символами фильма)
к короткому решению я шел долго… но когда его увидел, даже растроился. как-то оно очевидно при должном внимании
к короткому решению я шел долго… но когда его увидел, даже растроился. как-то оно очевидно при должном внимании
Хо-хо, школа, последняя парта и «номерки» — сколько тетрадок исписано в поисках короткого решения…
Тоже как-то заморочился лет 7 назад программным поиском решения.
Но мое решение (тоже 8 строк, искал минимальное по строкам, не зачеркиваниям) иное:
Тоже как-то заморочился лет 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)
Было уже =)
habr.com/ru/post/130339
Я для Windows Phone её пилил в то время для автора. До сих пор лежит архив с кодом.
habr.com/ru/post/130339
Я для Windows Phone её пилил в то время для автора. До сих пор лежит архив с кодом.
минимальное количество ходов 23, ищите дальше
Позвольте выразить своё сомнение в том, что решение в статье не самое короткое.
Поддерживаю. Нет решения (полным перебором с ограничениями) короче 8 строк (см. выше). Разумеется, если соблюдать правила. В моем (выше) — 35 ходов, у вас — 33(?).
Ну а почему нет? Это тоже вполне себе метод ветвей и границ. Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.
Это, пмсм, не самое верное решение. Так будет найден локальный минимум. Условно говоря — на данном шаге у нас осталось всего 3 числа, но при последующих дописываниях мы вырастем до 20. А другой вариант оставит 4 числа, но потом сразу «схлопнется» — толку рассматривать первый вариант раньше?
Shersh это же просто игра «в цифре»? У автора данной статьи — поиск короткого решения.
Только не до конца уверен, что имеется ввиду под обрезкой ветвей. Это как если просто ограничить количество ходов?
Ну а почему нет? Это тоже вполне себе метод ветвей и границ. Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.
чтобы перебор был осмысленным и быстрым, лучше использовать очередь с приоритетом. Чем меньше на поле цифр (включая вычеркнутые), тем раньше такую конфигурацию следует рассматривать;
Это, пмсм, не самое верное решение. Так будет найден локальный минимум. Условно говоря — на данном шаге у нас осталось всего 3 числа, но при последующих дописываниях мы вырастем до 20. А другой вариант оставит 4 числа, но потом сразу «схлопнется» — толку рассматривать первый вариант раньше?
Shersh это же просто игра «в цифре»? У автора данной статьи — поиск короткого решения.
Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.
Собственно, я так и поступал.
Это, пмсм, не самое верное решение. Так будет найден локальный минимум.
Знаю, именно поэтому после нахождения первого попавшегося решения я перебирал все более короткие ветки, чтобы узнать, не пропустил ли чего. В начале у меня приоритет в очереди был по другому признаку и первым было найдено решение в 86 цифр.
Наверное, нужно было отразить это в тексте, спасибо!
А я её на Дельфи делал, ещё в доинтернетные времена, никак не распространял, кроме пары знакомых в локальной сети общежития, а потом лет через десять вдруг один случайный знакомый узнав моё имя показал мне мою игру, которую он выудил со спутника и играл.
Я к тому времени уже и правила позабыл.
Я к тому времени уже и правила позабыл.
Мне кажется, или в анимации решения несколько раз вычеркиваются цирфы, стоящие ни последовательно, ни друг над другом? Да хотя бы последние две пары.
Обманул, не за 23 хода, а за 26 можно закончить игру
НЛО прилетело и опубликовало эту надпись здесь
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Тайм-киллер из детства