Electronic Joint Business

Solution for E-Business

graph

用图着色来解决数独问题

在本文中,我将简单介绍图着色(graph coloring) 的概念,并演示如何用这一概念来解决 9×9 的数独(Sudoku Puzzle)。本文假设读者已对图(graph)的概念和表现形式相当熟悉。1

揭秘图着色
图是一组彼此之间互相链接的对象的数学表示。对象表示为顶点(节点),链接则称为边。

图着色则是为图的顶点指定”颜色”,让相邻的两个顶点不能共享相同的颜色。比如在上图中顶点 1 和 2 不能用相同的颜色因为有一条边连接着它们。然而顶点 2 和 3 可以用相同的颜色,因为它们彼此并未连接。下面可能的着色图之一。

很显然,图可以有多种可能的着色。我们的目标是力求使用最少的颜色。图1-3是另外两个可能的着色图。着色图(1)使用了3种颜色,而着色图(2)使用5种颜色,因此 着色图(1)比着色图(2)更好。

对于给定的图,着色是是为了使图可以正常着色的最少颜色数。使用至多 k 种颜色的着色被称为 K-着色(比如上面的例子中,着色图(1)为3-着色,而着色图(2)是5-着色)。

>>> 阅读全文