In the Numberlink puzzle [1] we need to connect end-points by paths over a board with cells such that:
- Each cell is part of a path
- Paths do not cross
E.g. the puzzle on the left has a solution as depicted on the right [1]:
The picture on the left provides the end-points. The solution in the picture on the right can be interpreted as:
The main variable we use is:
The main thought behind solving this model as a math programming model is to look at the neighbors of a cell. The neighbors are the cells immediately on the left, on the right, below or above. If a cell is an end-point of a path then it has exactly one neighbor with the same value. If a cell is not an end-point it is on a path between end-points and has two neighboring cells with the same value.
This leads to the following high-level MIQCP (Mixed Integer Quadratically Constrained Model):
Here is true if and are neighbors and indicates if cell is an end-point with value . The model has no objective: we are just looking for a feasible integer solution. Unfortunately, this is a non-convex model. The global solver Baron can solve this during its initial local search heuristic phase:
Doing local search Cleaning up *** Normal completion *** Wall clock time: 23.73 Total no. of BaR iterations: 1 All done |
Of course we can try to linearize this model so it becomes a MIP model (and thus convex). The product of two binary variables can be linearized by:
We can relax to a continuous variable between 0 and 1. In our model we can exploit some symmetry. This reduces the number of variables and equations:
The non-linear counting equation can now be written as:
Here is the right-hand side of the counting constraint. This solves very fast. Cplex shows:
Tried aggregator 2 times. Root node processing (before b&c): |
Cplex solves this in the root node.
Unique solution
A well-formed puzzle has exactly one solution. We can check this by adding a constraint that forbids the solution we just found. After adding this cut the model should be infeasible. Let be our feasible solution. Then our cut can look like:
where is the number of cells. Indeed, when we add this constraint, the model becomes infeasible. So, we can conclude this is a proper puzzle.
Alternative formulation
In the comments Rob Pratt suggests a formulation that works a better in practice. The counting constraint is replaced by:
where can be replaced by (the number of neighbors of cell ). This is at most 4 so not really a big big-M.
This formulation seems to work better. We can solve with this something like:
This problem has also exactly one solution.
Historical note
In [3] an early version of this puzzle is mentioned, appearing in
Here the goal is to draw paths from each house to its gate without the paths overlapping [4].
Large problems
For larger problems MIP solvers are not the best tool. From notes in [2] it looks like SAT solvers are most suitable for this type problem. In a CP/SAT framework we could use directly an integer variable , and write the counting constraints as something like:
References
- Numberlink, https://en.wikipedia.org/wiki/Numberlink
- Hakan Kjellerstrand, Numberlink puzzle in Picat, https://github.com/hakank/hakank/blob/master/picat/numberlink.pi (shows a formulation in the Picat language)
- Aaron Adcock, Erik D. Demaine, Martin L. Demaine, Michael P. O'Brien, Felix Reidl, Fernando Sanchez Villaamil, and Blair D. Sullivan, Zig-Zag Numberlink is NP-Complete, 2014, https://arxiv.org/pdf/1410.5845.pdf
- Facsimiles of The Brooklyn Daily Eagle, http://bklyn.newspapers.com/image/50475607/, https://bklyn.newspapers.com/image/50475838/
- Neng-Fa Zhou, Masato Tsuru, Eitaku Nobuyama, A Comparison of CP, IP, and SAT Solvers through a common interface, 2012, http://www.sci.brooklyn.cuny.edu/~zhou/papers/tai12.pdf
Yeah a bit late I know, but it would be cool if you could write it more detailed so that the uninitiated like me could understand it. Otherwise good visualisations :D
ReplyDelete