Bridg-It 搭桥棋：先手必胜被证明多年后才找到具体策略的经典连接游戏
Bridg-It 由数学家 David Gale 发明、1960年商业化发行，两组交错点阵各自搭桥连对边。它先手必胜的结论早已知晓，具体策略却由 Oliver Gross 用配对法才给出。
游戏怎么玩
Bridg-It（又称 Gale、Game of Gale）由美国数学家 David Gale 发明，最早见于 Martin Gardner 1958年10月在《Scientific American》的专栏。1960年，Hassenfeld Brothers（即后来的孩之宝）把它做成商业棋盘游戏推向市场，名为 Bridg-It。
实体版的组件是：一块塑料板，上面有两组交错排列的长方形基座点阵（一组黄色、一组红色，常见规格为5×6），红黄两色塑料小桥各20枚，以及用于固定的小桩。
规则极其简单：
- 双方轮流行动，每次在自己颜色的两个相邻基座之间架一座桥；
- 桥只能架在正交相邻的两个同色基座之间，且不能与已架的桥交叉；
- 谁先把棋盘上属于自己颜色的两条对边连通，谁就获胜。
用纸笔也能玩：一人用黑笔连黑点、一人用红笔连红点，画线段时不能与已有线段相交。
官方还提供了一个变体：限定每人只有10座桥，全部用完仍未分胜负时，每人每回合可以挪动一座自己已架的桥，直到分出胜负。
一个重要的数学身份
Bridg-It 在数学上等价于 Shannon switching game（香农开关游戏）在矩形网格上的一个特例。
在 Shannon switching game 中，两名玩家轮流给图的边染色：Short（蓝方）想把两个指定顶点 s、t 用蓝色路径连起来，Cut（红方）想选出一个 s-t 边割把所有路径切断。把 Bridg-It 棋盘上其中一个网格的顶点分别收缩成 s 和 t，两者就完全对应：画一条蓝线段，等价于染蓝对应的那条边；画一条红线段，等价于染红唯一与之相交的那条蓝边。
它也可以看成一个 Maker-Breaker 型占位游戏，Maker 的获胜模式就是「连通路径」。
先手必胜：证明先到，策略后到
Bridg-It 有一个著名结论：先手一定存在必胜策略，而且证明方式非常漂亮——策略盗取（strategy stealing）。
理由是这样的：这个游戏是完全信息、确定性的，且不存在和局的终局（棋盘填满后必然有一方连通），因此必定有一方存在必胜策略。假设后手有必胜策略 S，那么先手可以先随便架一座桥，然后「假装自己是后手」按 S 行事；若 S 某一步要求走那座已经占掉的桥，就再随便补一步即可。多出来的一座桥只会是资产而不会是负担，于是先手也能必胜——这与「后手必胜」矛盾。所以必胜的只能是先手。
但策略盗取是非构造性的：它证明了策略存在，却没有告诉你怎么走。多年来人们只知道先手必胜，却拿不出具体下法。
Oliver Gross 的配对策略
突破口来自兰德公司（RAND Corporation）的数学家 Oliver Gross。他给出一个极其简洁的配对策略（pairing strategy）：
- 第一手按图示位置在左下角落一座桥；
- 此后，每当对手的桥跨过某条虚线的一端，你就跨过同一条虚线的另一端。
仅此两条，就足以保证先手获胜（虽然不一定是最少步数取胜）。Gross 自己形容这套策略是「民主的」——对笨对手下得笨，对聪明对手下得聪明，但无论怎样都赢。
这一策略的好处在于规律性强，可以直接推广到任意尺寸的 Bridg-It 棋盘。
还有个细节值得注意：棋盘边缘上的桥对连通毫无贡献，属于废着。如果对手下了一步边缘桥，你可以用一步边缘桥应对，也可以随手下在别处；万一后来策略要求你走那一步，换个地方走即可——多一座桥在盘上永远不是负担。
后续：从存在性到可计算
1964年，Alfred Lehman 用拟阵理论（matroid theory）给出了无向版 Shannon switching game 的显式解：Cut 先手时，若图 G 含有两棵边不相交的生成树，则 Maker 有明确的必胜策略。1970年 Bruno 与 Weinberg 进一步给出构造性的图论解法。
更关键的是复杂度结论：与 Hex 等 PSPACE-hard 的连接游戏不同，Shannon switching game 的胜负判定与最优着法计算都在多项式时间内（可用拟阵划分算法或网络流算法求解）。
与 Hex 的区别
Bridg-It 常被拿来和 Hex 类比，但两者结构完全不同：
- 染色对象不同：Hex 是给六边形格（顶点）染色，6连通；Bridg-It / Shannon switching game 是给边染色。
- 可解性不同：Hex 的一般化版本是 PSPACE-hard，至今没有通用的显式必胜策略；Bridg-It 早在1964年就被完整解决，且能在多项式时间内算出最优着法。
- 机制不同：Hex 只落子；Bridg-It 落的是「桥」，且桥与桥之间不可交叉，交叉关系本身就构成了对抗。
此外还有个三人扩展 Qua：在 N³ 的立方体棋盘上由三人对弈。