как таким образом раскрасить грачи в минимальное количество цветов - ни одна горизонтальная и вертикальная линия не содержит двух грачей одного цвета?

Question

Вот проблема (Грачи) просит, чтобы

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

Какой тип решения вы можете предложить?

Спасибо

Answer 1

Сформируйте двудольный граф со строками в одном наборе и столбцами как в другом.

Грачи будут соответствовать ребрам двудольного графа: строки r и столбец c объединяются с помощью ребра, если естьладья в положении (r, c).

Теперь вы ищите раскраску ребер этого двудольного графа.

Можно показать, что (сначала я полагаю, Кёниг), что минимальное числотребуемые цвета такие же, как известны алгоритмы максимальной степени и полиномиального времени (несмотря на общую проблему NP-Complete).Таким образом, в вашем случае минимальное количество требуемых цветов будет максимальным числом грачей в строке или столбце.

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

Здесь представлен алгоритм (и ссылки на более ранние алгоритмы) для двудольных графов, окрашивающих ребра: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.3399&rep=rep1&type=pdf

Answer 2

Ленивый подход для частичных точек .Раскрасьте все в соответствии с этой картой:

1  N  N-1 N-2
2  1  N   N-1
3  2  1   N
4  3  2   1   .  .  .
          .
          .
          .

И если после того, как вы назначите цвета ладьям, останутся неиспользуемые числа, то измените нумерацию раскраски.