Xingdu is an emerging mathematical game about searching for a corresponding
polyline for a given polyline in a 2-dimensional or 3-dimensional mesh grid, meanwhile the
searched polyline should have the same start and end points as those of the given polyline and
the corresponding line segments on the searched and given polylines are perpendicular each
other respectively. Studying from mathematical perspective the problem solving and
designing of Xingdu is helpful of finding a general method for Xingdu problem solving, but
still not attract much more attentions due to the relatively short history of Xingdu. Referring
to the achievements in mathematical methods for Sudoku, we investigated preliminarily the
possibility of using optimization theory to solve the problem of Xingdu. According to the
definition of Xingdu, the points on the given polyline and the solution polyline have to be the
grid nodes in the mesh grid so that their coordinates are integer. In addition, there should not
be any points appearing repeatedly and any three sequential points on the solution polyline
cannot be located on a same line. Due to these constraints, the optimization problem related
to Xingdu belongs to integer programming with nonlinear constraints, which is very difficult
and usually can only be solved by enumerating. For this reason, we solve the related problem
first by neglecting the nonlinear constraints so that it can be converted as an integer
programming with linear constraints only. Afterwards, we can check whether it fulfill the
related nonlinear constraints if a feasible solution is obtained. Based on that, we proposed two
integer programming models for Xingdu problem, which are the model using only line
segments perpendicular property as constraints and the binary integer programming model
using line segments perpendicular property together with no repeated points as constraints.
The test results show that the proposed binary integer programming model has a very good
performance in finding the solution of Xingdu problem. We also discussed the possibility of
using the proposed binary integer programming model together with random simulation to
design a Xingdu problem. Due to the challenge of discriminating the uniqueness of Xingdu
solution, we finally presented an approach, inspired from the branch and bound method for
integer programming, which solves and designs the Xingdu problem by constructing and
pruning a search tree.