数墙：把谜题当作格点上的回路来解

本章的内容

数墙是以数字为线索画出一条闭合回路的谜题。回路是连接格点的闭合路径，因此 add_circuit() 可以直接使用。

• 把盘面的格点作为顶点、把线作为边，构成图

• 不进入回路的点，用自环 (i, i) 表示

• 格的四周有几条线，用 sum(...) == 数字 约束

回路、自环、计数这三件事，就是数墙的全部建模内容。

规则

1. 画线

   • 把格点纵横相连画出线，线不能中断、交叉或分叉

2. 数字的含义

   • 格中的数字表示该格周围的线条数，为 0 时一条线也不能画，没有数字的格则不受限制

3. 形成闭合回路

   • 所有线连成一体，构成一个闭合的环

第三条与第一条并不重复：线可以各自闭合而成为多个环，因此还需要一条只造单环的约束。

数墙谜题的网站

https://ja.puzzle-loop.com

用 helper.puzzle.extract_slither_link() 可以取得这个网站上的谜题盘面。打开浏览器的开发者工具，把表示盘面的 <div> 标签的代码复制下来，交给这个函数执行，盘面就会以数组的形式取得。

思路

• 把盘面的格点，即格的角作为顶点。\(h \times w\) 的盘面共有 \((h+1) \times (w+1)\) 个格点

• 连接相邻格点的线是边，两个方向的有向边都要准备

• 并不需要经过所有格点，因此给每个格点加上自环 (i, i)

• 格周围四条线中，被选中的条数要与数字一致

add_circuit() 只造出一条回路，因此环不会分成两个，规则里“所有线连成一体”这一条也就不必另写约束。

from ortools.sat.python import cp_model
import numpy as np
from matplotlib import pyplot as plt
from matplotlib.collections import LineCollection
from collections import defaultdict


def plot_slither_link_board(board, result=None):
    """画出盘面和求解出的回路"""
    h, w = board.shape

    fig, ax = plt.subplots(figsize=(w * 0.3, h * 0.3))
    ax.set_ylim(-0.1, h + 0.1)
    ax.set_xlim(-0.1, w + 0.1)
    ax.invert_yaxis()
    ax.set_aspect("equal")

    all_segments = []      # 所有可以画的线（浅灰色）
    circuit_segments = []  # 被选中的线（绿色）

    if result is not None:
        for (n1, n2), flag in result.items():
            if flag:
                r1, c1 = n1 // (w + 1), n1 % (w + 1)
                r2, c2 = n2 // (w + 1), n2 % (w + 1)
                circuit_segments.append([(c1, r1), (c2, r2)])

    for r, c in np.ndindex(h + 1, w + 1):
        if r + 1 <= h:
            all_segments.append([(c, r), (c, r + 1)])
        if c + 1 <= w:
            all_segments.append([(c, r), (c + 1, r)])

    ax.add_collection(LineCollection(all_segments, color='gray', alpha=0.5))
    ax.add_collection(LineCollection(circuit_segments, color='green', linewidth=2))
    for (i, j), v in np.ndenumerate(board):
        if v != -1:
            ax.text(j + 0.5, i + 0.5, str(v), fontsize=12, va='center', ha='center')
    ax.autoscale_view()
    ax.axis('off')
    return fig, ax


board = np.loadtxt('data/slitherlink01.txt', dtype=np.int8)
plot_slither_link_board(board);

-1 表示没有数字的格。

求解

SlitherLinkSolver 由盘面组装模型并求解。编号、边与自环都在构造函数里一次造好。

class SlitherLinkSolver:
    def __init__(self, board):
        self.board = board
        h, w = self.board.shape

        # 给格子点从 0 开始连续编号
        self.nodes = nodes = np.arange((h + 1) * (w + 1)).reshape(h + 1, w + 1)

        # 连接相邻格子点的有向边（两个方向）
        self.edges = edges = []
        for (r, c), s in np.ndenumerate(nodes):
            if c + 1 <= w:
                e = nodes[r, c + 1]
                edges.extend([(s, e), (e, s)])
            if r + 1 <= h:
                e = nodes[r + 1, c]
                edges.extend([(s, e), (e, s)])

        # 收集每个方格四周的 4 条线（两个方向共 8 条）
        self.cell_edges = cell_edges = defaultdict(set)
        for (r, c), _ in np.ndenumerate(board):
            n1 = nodes[r, c]
            n2 = nodes[r, c + 1]
            n3 = nodes[r + 1, c]
            n4 = nodes[r + 1, c + 1]
            for edge in [(n1, n2), (n1, n3), (n2, n4), (n3, n4)]:
                cell_edges[r, c].add(edge)
                cell_edges[r, c].add(edge[::-1])

        model = cp_model.CpModel()
        variables = {e: model.new_bool_var(f'edge{e}') for e in edges}

        # 表示不经过的格子点的自环
        dummies = [(i, i, model.new_bool_var(f'dummy_{i}'))
                   for i in range((h + 1) * (w + 1))]
        model.add_circuit([(s, e, v) for (s, e), v in variables.items()] + dummies)

        # 方格四周的线数
        for (r, c), count in np.ndenumerate(board):
            if count != -1:
                box_edges = [variables[edge] for edge in cell_edges[r, c]]
                model.add(sum(box_edges) == int(count))

        solver = cp_model.CpSolver()
        if solver.solve(model) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
            raise ValueError("没有找到解")
        self.result = {key: solver.value(val) for key, val in variables.items()}


solver = SlitherLinkSolver(board)
plot_slither_link_board(board, solver.result);

代码的说明

1. 给格点编号

\(h \times w\) 的盘面有 \((h+1) \times (w+1)\) 个格点。保持二维形状处理起来不便，因此用 np.arange() 从 0 开始连续编号，变成一维的 ID。

2. 造出边

从每个格点向右与向下各连一条边，两个方向都要加入，因为 add_circuit() 处理的是有向边，去与回都需要。每条线因此在列表里出现两次，一次正向、一次反向。

3. 收集格周围的线

从格 (r, c) 四角的格点取出上、左、右、下四条线，两个方向各放一条，共八条，这样数选中的条数时就不必考虑方向，因为一条线只会有一个方向被选中，八条边求和就是格周围的线条数。八条边里四条对应格的四条边，另外四条方向相反，两者不会同时为真。

4. 用自环表示不经过的点

并不是所有格点都要用上，加入 (i, i, var) 之后，就可以选择不使用这个点，即用自环把它带过。回路的其余部分因此不必穿过这个格点。

5. 数字的约束

model.add(sum(box_edges) == int(count))

使格周围被选中的线条数与数字一致。

更难的谜题

下面解出题网站上最难的一类谜题。

board = np.loadtxt('data/slitherlink02.txt', dtype=np.int8)
solver = SlitherLinkSolver(board)
plot_slither_link_board(board, solver.result);

验算

确认解出的回路是否满足谜题的条件：数字、连通性与回路形状逐项核对。验算与求解分开写，两者用的是不同的代码。

def check_slither(board, result):
    """确认每个方格的线数，以及回路是否只有一条"""
    h, w = board.shape
    lines = set()
    for (n1, n2), flag in result.items():
        if flag:
            lines.add(tuple(sorted((n1, n2))))

    # 1. 每个方格四周的线数
    for (r, c), count in np.ndenumerate(board):
        if count == -1:
            continue
        n1 = r * (w + 1) + c
        n2, n3, n4 = n1 + 1, n1 + w + 1, n1 + w + 2
        box = [tuple(sorted(e)) for e in [(n1, n2), (n1, n3), (n2, n4), (n3, n4)]]
        if sum(1 for e in box if e in lines) != count:
            return False, f"方格 {(r, c)} 的线数不对"

    # 2. 回路是否只有一条（沿度为 2 的点能否走一圈）
    adj = defaultdict(list)
    for a, b in lines:
        adj[a].append(b)
        adj[b].append(a)
    for node, nb in adj.items():
        if len(nb) != 2:
            return False, f"格子点 {node} 的度不是 2"

    start = next(iter(adj))
    prev, cur, count = None, start, 0
    while True:
        count += 1
        nxt = adj[cur][0] if adj[cur][0] != prev else adj[cur][1]
        prev, cur = cur, nxt
        if cur == start:
            break
    if count != len(adj):
        return False, "回路不是一条"
    return True, f"{count} 个点组成的一条回路"


print(check_slither(solver.board, solver.result))

(True, '782 个点组成的一条回路')

小结

• 把格点作为顶点、线作为边之后，数墙就变成寻找一条回路的问题

• 不经过的点用自环 (i, i) 表示

• 格周围的线可以用八条有向边的和来计数

• add_circuit() 保证只有一条回路，环不会分裂

• 得到的解要用验算代码确认