数独与图着色

在本教程中，我们将使用 NetworkX 应用图论解决数独问题。

导入包

import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
import networkx as nx

介绍与直觉

数独是一种流行的数字放置谜题，基于逻辑和组合学。目标是在一个 9 × 9 的网格中填入数字，使得每一列、每一行以及构成网格的九个 3 × 3 子网格都包含从 1 到 9 的所有数字（恰好一次）。通常谜题会被部分填充，以保证唯一解。据我们目前所知，至少需要 17 个提示才能创建一个具有唯一解的谜题。

解决这个谜题的另一种方法如下：

• 将 81 个单元格视为图的节点

• 将连接（位于同一行、列或宫）视为边

这是问题的图论框架，在此之后，我们可以将数独视为一个顶点着色问题，我们将颜色分配给每个数字（1-9），并确保没有两个相同颜色的节点通过边相连（从而满足给定的约束）。

在数独的数学中，数独图是一个无向图，其顶点代表（空白）数独谜题的单元格，其边代表属于同一行、列或宫的单元格对。解决数独谜题的问题可以表示为该图上的预着色扩展。它是一个整凯莱图。

维基百科 - 数独图

这里的 pre-coloring extension（预着色扩展）简单来说就是将现有的提示转化为一个包含 81 个节点的图，为已作为线索给出的节点着色，然后在约束范围内尝试为其余顶点着色。

cayley graph（凯莱图）只是一种将群信息编码到图中的方法，就像我们可以用一个图完全定义数独谜题，而不会遗漏任何逻辑信息或数学性质。

问题形式化

非正式地讲，数独图是一个无向图，其顶点代表单元格，边代表属于同一行、列或宫的单元格对。正式地，这可以定义为：

阶数为 \(n\) 的数独网格是一个 \(n^2 × n^2\) 的网格(\(X_n\))。它由 \(n^2\) 个互不相交的 \(n × n\) 网格组成。\(X_n\) 的图，记为 \(GX_n\)，是 \((V, E)\)，其中数独网格的单元格构成其图的顶点，如果两个单元格位于 \(X_n\) 的同一行、同一列或同一宫，则它们相邻。\(GX_n\) 是一个阶数为 \(n^4\)，边数为 \(\frac{3n^6}{2} − n^5− \frac{n^4}{2})\) 的正则图，度为

\[ 3n^2 − 2n − 1 (1) \]

维基百科 - 数独图

现在，从 (1) 我们可以得出，阶数为 3 的数独网格的图是一个 \((V=81, E=810)\) 的正则图，度为 20。这可以通过非正式的方式验证——标准数独中有 81 个单元格，每个单元格与其所在行的 8 个单元格相邻 + 与其所在列的 8 个单元格相邻，以及与其所在宫的另外 4 个单元格相邻，因此度为 20。这个维基百科图片使得这种可视化更容易理解

让我们举一个数独谜题的例子，我们将使用图论来解决它（以及 NetworkX 和一些很酷的图！）

# Create Sudoku puzzle
puzzle = np.asarray(
    [
        [0, 4, 3, 0, 8, 0, 2, 5, 0],
        [6, 0, 0, 0, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 1, 0, 9, 4],
        [9, 0, 0, 0, 0, 4, 0, 7, 0],
        [0, 0, 0, 6, 0, 8, 0, 0, 0],
        [0, 1, 0, 2, 0, 0, 0, 0, 3],
        [8, 2, 0, 5, 0, 0, 0, 0, 0],
        [0, 0, 0, 0, 0, 0, 0, 0, 5],
        [0, 3, 4, 0, 9, 0, 7, 1, 0],
    ]
)

n = 3
G = nx.sudoku_graph(n)
mapping = dict(zip(G.nodes(), puzzle.flatten()))
pos = dict(zip(list(G.nodes()), nx.grid_2d_graph(n * n, n * n)))

# we map the nodes 1-9 to a colormap
low, *_, high = sorted(mapping.values())
norm = mpl.colors.Normalize(vmin=low, vmax=high, clip=True)
mapper = mpl.cm.ScalarMappable(norm=norm, cmap=mpl.cm.Pastel1)

# draw the graph
plt.figure(figsize=(12, 12))
nx.draw(
    G,
    labels=mapping,
    pos=pos,
    with_labels=True,
    node_color=[mapper.to_rgba(i) for i in mapping.values()],
    width=1,
    node_size=1000,
)
plt.show()

现在这可以使用贪婪图着色算法来解决，这是一个 NP 困难问题，因此某种程度的暴力求解是过程的一部分

图 G 的 k-着色是一种顶点着色，它为图 G 的每个顶点分配 k 种可能的颜色中的一种（即顶点着色），使得没有两个相邻顶点接收相同的颜色。

在这种情况下我们需要多少种颜色？ 9

注意：这不仅仅是直觉，形式上 9 是 \(n^2 * n^2\) 数独图的 2-距离着色问题的色数，你可以在这里了解更多！

让我们生成一个已解决的网格，我们将尝试对其进行可视化

from random import sample


# Generate random sudoku
def generate_random_sudoku(n):
    side = n * n

    def _pattern(r, c):
        return (n * (r % n) + r // n + c) % side

    rBase = range(n)
    rows = [g * n + r for g in sample(rBase, n) for r in sample(rBase, n)]
    cols = [g * n + c for g in sample(rBase, n) for c in sample(rBase, n)]
    nums = sample(range(1, n * n + 1), n * n)
    board = [nums[_pattern(r, c)] for r in rows for c in cols]
    return board

所以现在我们修改节点到这个已解决数独的映射

board = generate_random_sudoku(n)
mapping = dict(zip(G.nodes(), board))

plt.figure(1, figsize=(12, 12))
nx.draw(
    G,
    pos=pos,
    labels=mapping,
    node_size=1000,
    node_color=[mapper.to_rgba(i) for i in mapping.values()],
    with_labels=True,
)

plt.show()

G = nx.sudoku_graph(n=3)

len(G.edges())

810

为了理解和可视化同排、同宫或同列的约束，更仔细地查看边可能会有用

首先，假设我们有这个图 G，现在假设我们想单独检查所有三种不同的约束，需要区分三种不同类型的边（共有 810 条！），让我们来做吧！

让我们快速看一下 networkx 在一个空的（未着色或未标记的）数独图中绘制的内容

plt.figure(figsize=(12, 12))
pos = dict(zip(list(G.nodes()), nx.grid_2d_graph(n * n, n * n)))
nx.draw(G, pos=pos, node_color="white", with_labels=True)
plt.show()

看，所有节点都按列堆栈的方式索引从 0 到 80，现在我们将在这里分离出三种不同类型的边

import itertools


def separate_edges(n):
    G = nx.sudoku_graph(n)
    box_edges = []
    row_edges = []
    column_edges = []
    boxes = []
    for i in range(n):
        for j in range(n):
            box = [
                (n) * i + j * (n * n * n) + (n * n) * k + l
                for k in range(n)
                for l in range(n)
            ]
            boxes.append(box)

    for i in range(n * n):
        row_edges += list(
            itertools.combinations([i + (n * n) * j for j in range(n * n)], 2)
        )
        box_edges += list(itertools.combinations(boxes[i], 2))
        column_edges += list(
            itertools.combinations(list(G.nodes())[i * (n * n) : (i + 1) * (n * n)], 2)
        )
    return row_edges, box_edges, column_edges


def plot_edge_colored_sudoku(n=3, layout="grid"):
    row_edges, box_edges, column_edges = separate_edges(n)
    G = nx.sudoku_graph(n)
    board = generate_random_sudoku(n)
    mapping = dict(zip(G.nodes(), board))

    plt.figure(figsize=(12, 12))
    if layout == "circular":
        pos = nx.circular_layout(G)
    if layout == "grid":
        pos = dict(zip(list(G.nodes()), nx.grid_2d_graph(n * n, n * n)))

    nx.draw(G, pos=pos, labels=mapping, with_labels=True, node_color="orange")
    nx.draw_networkx_edges(G, pos=pos, edgelist=box_edges, edge_color="tab:gray")
    nx.draw_networkx_edges(
        G, pos=pos, edgelist=row_edges, width=2, edge_color="tab:blue"
    )
    nx.draw_networkx_edges(
        G, pos=pos, edgelist=column_edges, width=2, edge_color="tab:green"
    )
    plt.show()

好的，开始绘图吧！！

plot_edge_colored_sudoku()

让我们稍微改变一下布局，看看所有因相互重叠而看不见的边

plot_edge_colored_sudoku(layout="circular")

漂亮！现在，让我们看看如果数独是 16 x 16 的网格而不是 9 x 9 的话，数独图会是什么样子

plot_edge_colored_sudoku(n=4)

参考文献

维基百科 - 数独图