## 8 Experiments
### Solvers for Numberlink and Slitherlink  
In this subsection, we discuss our experimental results on the comparison of our algorithm for solving Numberlink and Slitherlink with existing methods which are based on CPLEX 12.3 and Sugar. We implemented Algorithm 2 for Numberlink solver and Algorithm 5 for Slitherlink solver in C\(++\) and compiled them by G\(++\) 4.6 with -O3 optimization option. In our implementation, a variable order (an edge order) is lexicographical on sets of two vertices where vertices are labeled such as Figure 6.  
We prepared the benchmark programs. We formulated solving Numberlink [15] and Slitherlink [16] as integer programs and solve them by CPLEX, which is an integer programming solver. Sugar is a SAT based constraint solver [8]. Sugar provides the formulation of Numberlink [17] and Slitherlink [18]. We also compared them with a heuristic solver _slink_[9] specialized for Slitherlink, which is published as a C source code. Table 1 shows the running times of these methods for solving Numberlink. In the table, BN\(x\) denotes the \(x\)th instance in [19]. C88 is the Vol. 88 instance in Puzzle Championships 2010 [20]. Let \(G_{\alpha,\beta}\) denote the \(\alpha\times\beta\) grid graph. In Table 2, we show the running times of these methods with the restriction that requires solutions to cover all vertices (see Remark 7). \begin{table}
\begin{tabular}{l l r r r r} \hline \hline
**Instance** & **Graph** & **Time CPLEX** & **Time Sugar** & \
\begin{tabular}{c} **Time** \\ **Algorithm 2** \\ \end{tabular} &
\begin{tabular}{c} **Memory** \\ **Algorithm 2 (MB)** \\ \end{tabular} \\ \hline BN1 & \(G_{8,8}\) & \(0.02\) & \(1.179\) & \(0.008\) & \(2\) \\ BN15 & \(G_{8,8}\) & \(13.95\) & \(1.336\) & \(0.004\) & \(2\) \\ BN30 & \(G_{10,10}\) & \(88.32\) & \(1.896\) & \(0.016\) & \(5\) \\ BN43 & \(G_{10,10}\) & \(6,410.67\) & \(1.924\) & \(0.072\) & \(18\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Running time in seconds for solving Numberlink. Our algorithm could not solve C88 due to insufficient memory. Figure 6: Grid graph \(G_{b,a}\) and its vertex labels. Table 3 describes the running time of these methods as Slitherlink solvers. BS\(x\) denotes the \(x\)th instance in [21]. S10 is a large sample problem on [22]. C95 is the Vol. 95 instance in Puzzle Championships 2010 [20]. \begin{table}
\begin{tabular}{l c c c c c} \hline \hline
**Instance** & **Graph** & **Time CPLEX** & **Time Sugar** & \
\begin{tabular}{c} **Time** \\ **Algorithm 2** \\ \end{tabular} &
\begin{tabular}{c} **Memory** \\ **Algorithm 2 (MB)** \\ \end{tabular} \\ \hline BN52 & \(G_{10,10}\) & \(0.45\) & \(1.520\) & \(0.012\) & \(3\) \\ BN64 & \(G_{10,10}\) & \(108.07\) & \(1.704\) & \(0.136\) & \(11\) \\ BN72 & \(G_{10,10}\) & \(276.07\) & \(1.388\) & \(0.012\) & \(4\) \\ BN79 & \(G_{10,10}\) & \(15,117.47\) & \(1.496\) & \(0.220\) & \(37\) \\ BN85 & \(G_{20,15}\) & \(>\)\(100,000\) & \(7,213.079\) & \(862.518\) & \(43,846\) \\ BN99 & \(G_{20,15}\) & \(>\)\(100,000\) & \(14.097\) & \(1,658.772\) & \(67,094\) \\ C88 & \(G_{20,36}\) & \(>\)\(100,000\) & \(>\)\(100,000\) & – & – \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Running time in seconds for solving Numberlink with restriction that requires solutions to cover all vertices.