这是 problem (Rooks)问那个
Given a chessboard NxN, on which the rooks are placed. You have to color those rooks in a minimal number of colors in that way – no horizontal and vertical line contains two rooks of the same color.
您可以提供什么类型的解决方案？
谢谢
最佳答案
形成一个二分图，其中行为一组，列为另一组。
车将对应于二分图的边:如果位置 (r,c) 处有车，则行 r 和列 c 由 和 边连接。
现在您正在寻找此二分图的边着色。
可以证明(我首先相信 Konig)所需的最少颜色数与最大度数相同，并且多项式时间算法是已知的(尽管一般问题是 NP-Complete)。因此，在您的情况下，所需的最少颜色数将是一行或一列中的最大车数。
其实边着色对应的是二部图的折线图的顶点着色，已知是一个perfect graph因此最少的颜色数就是最大的度数。为完美图着色的多项式时间算法也是众所周知的，但对于这个问题来说，这太过分了。
此处出现了一种用于边着色二分图的算法(以及对早期算法的引用):http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.144.3399&rep=rep1&type=pdf
关于algorithm - 如何以这种方式用最少数量的颜色给车上色——没有水平和垂直线包含两个相同颜色的车？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6058572/