The three-dimensional tic-tac-toe problem (Three-Demensional Noughts and Crosses) is a classic combinatorial optimization problem. This article covers the background introduction of the three-dimensional tic-tac-toe minimization problem of same-color connections, integer planning variables and constraint modeling, solution results and optimal layout display.
Total text: 971 words
Estimated reading time: 4 minutes
01 · Problem description
As shown in the figure below, 27 cells are arranged in a three-dimensional array.
Three cells are considered to be on the same straight line if they are on the same horizontal, vertical, or diagonal line. There are diagonals on each horizontal and vertical plane, connecting the diagonal vertices of the cube (there are 49 lines in total: horizontal and vertical + diagonal + 4 diagonal). Given 13 white balls (circles) and 14 black balls (crosses), our goal is to place them all into cells so that the number of balls of the same color on the same straight line is minimized.
This problem typically represents the combinatorial nature of integer programming problems. Obviously, there are endless possibilities for arranging chess pieces in three-dimensional space. Such problems are often extremely difficult to solve as an integer programming model. There are significant advantages to using heuristic solutions: the obtained solutions can be used as thresholds for branch-and-bound tree searches (see Section 8.3 for details). Williams (1974) has discussed two modeling ideas for this problem, and the better method will be introduced below.
1 · Variable
Number the cells sequentially first by row and then by section one by one, from 1 to 27. Introduce a 0-1 variable δ for each cell jj. If δjEqual to 1, it means that there is a black ball in the cell. If δjEqual to 0, it means there is a white ball in the cell.
There are 49 possible lines in the cube. Introduce a 0-1 variable γ for each linei，γiEqual to 1 means that all balls in the line have the same color, otherwise γiequal to 0.
2 · Constraints
Define the same color identification variable γ for each line ii, ensuring its logical relationship through the following constraints:
(i=1, 2, ..., 49, 49 lines in total, each line corresponds to 3 units)
Indeed, these constraints do not ensure that if γi= 1, all balls in the line are the same color. When the goal is formulated, it will become clear that this condition will be guaranteed by optimality.
Limit the total number of black balls:
3 · Goals
Minimize the total number of lines of the same color:
This model has a total of 99 constraints and 76 0-1 variables.
4 · Results
The minimum number of balls of the same color connected in a straight line is four. There are many solutions, one of which is shown in Figure 14.5.
04 · Video display
Machine-translated from the Chinese original 三维井字棋问题 Three-Dimensional Noughts and Crosses (published 2025-09-09). WeChat original ↗