Я хотел бы знать, изучалась ли ранее простая проблема и известно ли какое-либо решение.
Пусть G - конечная (MxN) сетка, S - подмножество клеток G («крошки»). Говорят, что две крошки (локально) связаны, если их координаты отличаются не более чем на один (т. Е. Если они нарисованы в виде квадратов, они имеют хотя бы одну угловую точку).
Теперь можно попытаться соединить крошки (их набор в целом), переставляя линии и столбцы сетки. Другими словами, цель состоит в том, чтобы придумать перестановку строк и перестановку столбцов так, чтобы любые два крошки в результирующей сетке были связаны цепочкой (локально) связанных крошек.
Вопрос: всегда ли есть решение?
Я не совсем знаю, как на него напасть. Из-за отсутствия лучшей идеи я написал сырую программу, которая ищет решения методом грубой силы (она генерирует случайные перестановки и проверяет, связаны ли крошки в результирующей сетке). До сих пор программа всегда находила решения для маленьких (10x10 или 7x14) сеток, а более крупные сетки явно недосягаемы для своей упрощенной стратегии (слишком бы случайно наткнуться на решение).
Вот пример сетки, решаемой программой:
Начальная сетка (крошки обозначены X, пустые ячейки точками):
0 1 2 3 4 5 6 7 8 9
0 X . X X . X . X X .
1 X . . . . X . . . .
2 . . X . . . . X . X
3 . X . . X . X . . X
4 . . . X . . . . . .
5 X X . . . X X . X .
6 . . . X . . . . X .
7 X . X . . X . . . .
8 X . . . X . . X X .
Решение:
6 1 4 7 8 2 9 3 5 0
1 . . . . . . . . X X
4 . . . . . . . X . .
5 X X . . X . . . X X
8 . . X X X . . . . X
7 . . . . . X . . X X
0 . . . X X X . X X X
3 X X X . . . X . . .
6 . . . . X . . X . .
2 . . . X . X X . . .
Естественно, проблему можно легко обобщить на любое измерение d> 2. Полагаю, можно было бы рассмотреть и другие обобщения.
Заранее спасибо,
Ян Дэвид
Ответы:
Давайте попробуем аналогично аргументу подсчета с более ранней версией моего ответа.
источник