三维井字棋问题（Three-Demensional Noughts and Crosses）是一个经典的组合优化难题，本文内容涵盖了三维井字棋同色连线最少化问题的背景介绍、整数规划变量与约束建模、求解结果及最优布局展示。
全文共计：971字
预计阅读：4分钟
01 · 问题描述
如下图所示，27个单元格按照的三维数组排列。
如果三个单元格在同一条水平线、垂直线或对角线上，则认为它们在同一直线上。每个水平面和垂直面上都存在对角线，连接着立方体的对角顶点（总共有49条线：横竖+面对角线+4对角线） 给定13个白球（圈）和14个黑球（叉），我们的目标是将它们全部放置到单元格中，使得同色球在同一直线上的数量最小化。
这个问题典型地代表了整数规划问题的组合特性。显然，在三维空间中排列棋子的方式存在无穷可能，这类问题作为整数规划模型求解往往极为困难。采用启发式解法可获显著优势：所得解可作为分支定界树搜索的阈值（详见8.3节）。Williams(1974)曾探讨该问题的两种建模思路，下文将介绍其中更优的方法。
1 · 变量
先按行再按照切面逐个对单元格进行顺序编号，编号为1到27。为每个单元格 j 引入一个 0-1 变量δj。若δj等于1，代表单元格内为黑球，若δj等于0，代表单元格内为白球。
立方体中有49条可能的线。为每条线引入一个0-1变量γi，γi等于1代表线内所有球的颜色相同，反之γi等于0。
2 · 约束
定义每条线 i 的同色标识变量γi，通过以下约束确保其逻辑关系：
（i=1, 2, ..., 49，共49条线，每条线对应3个单元）
实际上，这些约束并不能确保如果γi = 1，线中的所有球都是同一种颜色。当目标被公式化时，将清楚地看到这个条件将由最优性保证。
限制黑球总数：
3 · 目标
最小化同色线的总数：
这个模型总共有99个约束和76个0-1变量。
4 · 结果
同色球连成直线的最小数量为四条。存在多种解法方案，图14.5展示了其中一种。
04 · 视频展示
作者 | 陈鑫
欢迎关注「久章智能」公众号
了解更多智能决策的前沿技术与行业应用
旅行商问题（TSP）及开源代码
本文转载自久章智能微信公众号（原文发布于 2025-09-09），内容保持原貌。扫码关注公众号「久章智能」，第一时间获取智能决策系列文章。阅读原文 ↗