Алгоритм решения тетравекса

Question

Ну, я думал о создании программы для решения Tetravex, чтобы практиковать свои навыки написания кода (язык, вероятно, будет Visual Basic), и мне нужна помощь в поиске алгоритма для ее решения. Для тех, кто не знает, что такое тетравекс, см. http://en.wikipedia.org/wiki/TetraVex. Единственный алгоритм, который я могу придумать, - это метод грубой силы, случайным образом поместить плитку в один угол и попробовать все возможные плитки рядом с ним, и продолжить тот же процесс, если он достигнет тупика, вернуться в предыдущее состояние и поместить другое плитка. Так может кто-нибудь придумать лучший алгоритм? Спасибо за ваше время.

Answer 1

вот несколько идей.

Алгоритм грубой силы ванили попытался бы рекурсивно заполнить сетку, перечислив позиции сетки в фиксированном порядке (например, мажор строки) и всегда пытаясь уместить все возможные фигуры в текущей позиции, а затем рекурсивно. Это то, что вы упомянули, и это очень неэффективно.

Улучшение состоит в том, чтобы всегда считать для каждой свободной позиции количество фигур, которые там помещаются, а затем возвращаться к позиции, которая имеет наименьших посадок ; если у вас ноль штук, немедленно возвращайтесь; если есть один, где подходит только один кусок, заполните и продолжите (ветвь не создана); в противном случае выберите тот, который имеет наименее подходящие элементы (& ge; 2), и продолжайте оттуда.

Как только вы установите этот алгоритм, следующий вопрос заключается в том, как вы можете еще больше сократить пространство поиска. Если есть, скажем, кусочки A с «1» в верхнем положении и куски B с «1» в нижнем положении и A> B, то вы знаете, что по крайней мере A - B из кусочков «1 в верхнем положении» должен быть фактически размещен в верхнем ряду, чтобы вы могли исключить их из любой другой позиции. Это помогает уменьшить фактор ветвления и раньше находить тупики.

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

Существует также стратегия, называемая «не хронологическим отслеживанием» или «обратным переходом», которая исходит из исследований по решению SAT. Это поможет вам вернуться более чем на один уровень за раз, когда вы зашли в тупик; если вы хотите, вы можете найти эти термины в Google, чтобы найти больше, но вам нужно проделать определенную умственную работу, чтобы отобразить концепцию в проблемном пространстве.

Answer 2

На любой данной частично решенной доске я бы

• найдите место, где ни одна из оставшихся плиток не может быть сыграна. Если доска найдена, она должна быть размотана до последнего места, где был разложен тайл.

• Ищите место, где легально можно сыграть только 1 из оставшихся плиток. Если найден, поместите эту плитку.

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

В псевдокоде это будет

top:
  evaluate # of tiles that match at each empty square
  if any square has 0 matches, unwind to <prev>
  if any square has 1 match, lay tile, goto top
  save current board as <prev>
  play randomly at square with minimum number of matches, goto top

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

Answer 3

Похоже, что Tetravex является проблемой удовлетворения ограничений , поэтому вы хотите как можно быстрее ограничить свои возможности. Должно быть возможно сделать лучше, чем случайное размещение. Как насчет?

• Создание связей между всеми гранями плиток с их возможными совпадениями.
• Любая плитка с несвязанной гранью должна быть краевой плиткой.
• Любая плитка с двумя смежными несвязанными гранями должна быть угловой плиткой.
• Центральные плитки должны иметь четыре активных ссылки.
• Теперь поместите плитку в правильное местоположение и лишите законной силы используемые ссылки. Если какой-либо неразмещенный тайл содержит три несвязанные грани или несвязанные грани на противоположных сторонах, перемещение является недействительным, и вы можете вернуться назад.
• Вы должны иметь возможность использовать лицевые ссылки плиток для поиска следующей возможной плитки по сравнению с поиском по всем плиткам. Если его нет, вернитесь назад.

Answer 4

Первым улучшением будет подсчет количества совпадающих пар чисел, и если, скажем, есть 5 «1» в верхней части квадратов, но только 4 в нижней части, то должно быть «» 1 "указывает на верхнюю часть сетки.

Answer 5

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

Я начинаю с создания списка всех возможных связей между плитками снизу вверх и спискомвсе возможные соединения между плитками справа налево.

Из этих двух списков я строю список всех возможных допустимых комбинаций 2x2.

Используя список 2x2, я строю список всех возможныхдопустимые комбинации 3x3.

Оттуда я могу перейти 4x4, используя списки 2x2 и 3x3, или сделать 5x5, просто используя список 3x3.

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

---

Это также кажется отличной ситуацией для использования нейронной сети, и я мог бы дать этопопытка следующая.