Алгоритм соединения стен

Question

Мне нужно выяснить алгоритм, который находит решение для игры Connect the Walls.

В Connect the Wall у нас есть доска прямоугольной формы, разделенная на равные квадратные ячейки.В каждой ячейке мы можем поставить диагональную стенку (направленную из левого верхнего угла в правый нижний или из левого нижнего угла в правый верхний).Мы должны поместить стены во все пустые пространства в соответствии со следующими правилами:

1. Каждая клетка должна содержать стену
2. Стены не должны образовывать замкнутый контур (мы можем't "кирпичик")
3. Количество стен, соединяющихся с колонной, должно соответствовать числу, написанному на колонне
4. Кроме того, некоторые ячейки могут содержать стену, которую мы не можем переместить.

Соедините стены онлайн-игры

Пожалуйста, помогите.

РЕДАКТИРОВАТЬ:

ОК.Мне удалось написать упрощающий алгоритм на C. Мне нужен кто-то, чтобы проверить меня.Пока это работает так: Шаги

Более того, у меня есть вопрос о последнем шаге грубой силы.Могу ли я выбрать случайную ячейку для начала?(может быть, есть более быстрый способ) Алгоритм грубой силы, насколько я понимаю:

1. Выберите первую ячейку и отметьте ее / или \
2. Проверьте, соответствует ли он столбамкритерии и если циклов нет
3. Если все в порядке, перейдите к пустой соседней ячейке, если нет, вернитесь назад и измените направление стены в предыдущей ячейке (если мы не делали этого раньше)
4. Цикл, пока у нас не будет пустых клеток на нашей доске.Это верно?

И еще один вопрос, касающийся проверки быстрого цикла.Я понял, что мог бы использовать непересекающиеся множества и связанные компоненты функций графа.Итак ... Мы сохраняем связные компоненты графа в структуре find-union.Если новый недавно добавленный край (стена) соединяет точки из того же подключенного компонента - это цикл.

Answer 1

Веселая игра.Вроде как подметальная машина.

Вас интересует только способ получить решение?В этом случае это простой поиск по дереву.Вроде как решение лабиринта.Возврат и прочее.Легко обрезать поддеревья, так как ограничения довольно жесткие.

Быстрый способ?Ищите все «2» столба на границе.Заполните их все сначала.Также заполните «1» столбов по углам.Отметьте все стены, соединяющиеся со столбами «0», как невозможные, но отметьте все остальные направления (поскольку все эти квадраты должны быть отмечены).

Затем для каждой колонны, имеющей необходимое количество стен, отметьте все остальные соединительные элементы.Стены к этой колонне как невозможные, отмечают все остальные направленияЗатем пометьте все остальные стены, соединенные с "3" столбами одной невозможной стеной.Отметьте все остальные стены, связанные с "2" столбами с двумя невозможными стенами.Тогда "1" столбов.Цикл.

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