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:

\[x_{p,k} = \begin{cases}1 & \text{ if cell $p$ has value $k$}\\ 0 & \text{ otherwise}\end{cases}\] |

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):

\[\bbox[lightcyan,10px,border:3px solid darkblue]
{\begin{align} &\sum_k x_{p,k} = 1\\ &\sum_{q|N(p,q)} \sum_k x_{p,k}\cdot x_{q,k} =\begin{cases} 1&\text{if cell $p$ is an end-point}\\ 2&\text{otherwise}\end{cases}\\ &x_{p,k} = c_{p,k} \>\>\> \text{if cell $p$ is an end-point}\\&x_{p,k}\in \{0,1\}\end{align}}\] |

Here \(N(p,q)\) is true if \(p\) and \(q\) are neighbors and \(c_{p,k}\) indicates if cell \(p\) is an end-point with value \(k\). 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 \(y=x_1\cdot x_2\) can be linearized by:

\[\begin{align} |

We can relax \(y\) to a continuous variable between 0 and 1. In our model we can exploit some symmetry. This reduces the number of variables and equations:

\[\begin{align} |

The non-linear counting equation can now be written as:

\[\sum_{q|N(p,q)} \sum_k \left( y_{p,q,k}|p<q + y_{q,p,k}|q<p \right)= b_{p}\] |

Here \(b_p\) 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 \(\alpha_{p,k} = x^*_{p,k}\) be our feasible solution. Then our cut can look like:

\[\sum_{p,k} \alpha_{p,k} x_{p,k} \le |P|-1\] |

where \(|P|\) 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:

\[\begin{align} &\sum_{q|N(p,q)} x_{q,k}=1 &&\text{if cell $p$ is an end-point with value $k$}\\ &2x_{p,k}\le \sum_{q|N(p,q)} x_{q,k} \le 2x_{p,k}+M_p(1-x_{p,k})&&\text{if cell $p$ is not an end-point} \end{align}\] |

where \(M_p\) can be replaced by \(M_p=|N(p,q)|=\sum_{q|N(p,q)} 1\) (the number of neighbors of cell \(p\)). 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 \(x_p \in \{1,\dots,K\}\), and write the counting constraints as something like:

\[\sum_{q|N(p,q)} 1|(x_p=x_q) = \begin{cases} 1&\text{if cell $p$ is an end-point}\\ 2&\text{otherwise}\end{cases}\] |

##### 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

## No comments:

## Post a Comment