Комментарии 36
ЕМНИП, дописывать таблицу можно лишь в том случае, когда вычёркивать нечего
Емнип, не обязательно. Очень хорошо помню момент, когда играл на компьютере в нее. Таблица сильно раздута, вроде всё вычеркнул, дописываешь таблицу и видишь, Что В строке подряд идут пары. Значит, где то выше ты их не вычеркнул. Проверяешь, и да, действительно так.
Хм. Попробовать, что ли, прикинуть эвристику да формально применить A*, интересно смотрится...
Но в школе у нас она тоже без названия была.
Автору спасибо за ностальгию и интересный рисёрч :)
Как аналогию можно взять ветки деревьев. Если идти от их концов к стволу — то более мелкие ветки сливаются в одну.
к короткому решению я шел долго… но когда его увидел, даже растроился. как-то оно очевидно при должном внимании
Тоже как-то заморочился лет 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 её пилил в то время для автора. До сих пор лежит архив с кодом.
Только не до конца уверен, что имеется ввиду под обрезкой ветвей. Это как если просто ограничить количество ходов?
Ну а почему нет? Это тоже вполне себе метод ветвей и границ. Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.
чтобы перебор был осмысленным и быстрым, лучше использовать очередь с приоритетом. Чем меньше на поле цифр (включая вычеркнутые), тем раньше такую конфигурацию следует рассматривать;
Это, пмсм, не самое верное решение. Так будет найден локальный минимум. Условно говоря — на данном шаге у нас осталось всего 3 числа, но при последующих дописываниях мы вырастем до 20. А другой вариант оставит 4 числа, но потом сразу «схлопнется» — толку рассматривать первый вариант раньше?
Shersh это же просто игра «в цифре»? У автора данной статьи — поиск короткого решения.
Решение ушло слишком далеко по строкам — отметаем, возвращаемся к другой ветке.
Собственно, я так и поступал.
Это, пмсм, не самое верное решение. Так будет найден локальный минимум.
Знаю, именно поэтому после нахождения первого попавшегося решения я перебирал все более короткие ветки, чтобы узнать, не пропустил ли чего. В начале у меня приоритет в очереди был по другому признаку и первым было найдено решение в 86 цифр.
Наверное, нужно было отразить это в тексте, спасибо!
Я к тому времени уже и правила позабыл.
В вашей версии игры, по какой-то причине, можно переписывать числа в конец даже тогда, когда ещё есть другие доступные ходы. Получается, что у вас другой набор правил, который я никогда не рассматривал. Так что да, при этом условии может существовать более короткое решение, верю.
Тайм-киллер из детства