Дан набор предметов, скажем, номер 1-6. Найдите перестановки (а точнее, количество различных перестановок), используя эти элементы. Каждый предмет можно использовать более одного раза. Ограничение в том, что два соседних элемента не должны совпадать. Я использую '#' для обозначения позиции, в которой можно разместить элемент.
Начнем с примера в одномерном пространстве. Решение простое. У нас есть 6 вариантов для первой позиции и 5 для следующих.
Q: '###'
A: 6*5*5=150
Но мне это очень сложно, если мы рассмотрим ситуацию в 2D-пространстве. В двухмерном пространстве прилагаемый элемент - это тот, который находится сверху, снизу, слева или справа.
Q: '##
# '
A: 6*5*5=150
Этот элемент такой же, как в одномерном пространстве. go сложно.
Q: '###
###'
A: ???
Q: '###
###
###'
A: ???
Я не могу дать решения.
Есть ли эффективный метод решения проблемы? А что, если пространство будет расширено до 100 * 100?
Я пытался решить это с помощью программы, обхода грубой силы 6 ^ n (n - количество позиций). Есть ли другие хорошие идеи?
Любая помощь приветствуется!