## Overview

This page presents a Numberlink solver written in Copris, a Constraint Programming DSL (Domain-Specific Language) embedded in Scala. Numberlink is a puzzle game developed by Nikoli.

This Numberlink solver can find a solution of the given Numberlink puzzle.

### What's New

• 2013-10-14 Mon Release of version 1.1
• 2013-09-01 Sun First release

Version 1.1
Version 1.0

## Requirements

• Scala version 2.10 to be installed
• Scala version 2.9 is not binary compatible with version 2.10. You need to compile Copris from the source.
• Copris (included in the package)
• Sugar (included in the package)
• Sat4j Core (included in the package)

## How to use

```scala -cp copris-numberlink-v1-1.jar numberlink.Solver input_file_name
```
• The format of the input file is explained below.

To check the uniqueness of the solutions, please use "-o multi" option.

```scala -cp copris-numberlink-v1-1.jar numberlink.Solver -o multi input_file_name
```

If you have a SAT solver (such as clasp, MiniSat, Glucose, GlueMiniSat) installed on your computer, you can use it to get better performance.

```scala -cp copris-numberlink-v1-1.jar numberlink.Solver -o multi -s1 glucose input_file_name
```

### Input file format

The following is an example of input file.

```5
5
7 - - - 3
9 1 3 - -
- - - 7 -
- - - - -
9 - - - 1
```
• The first line gives the number of rows.
• The second line gives the number of columns.
• Number cells are represented by its number.
• Blank cells are represented by "-".

### Example Usage

```\$ scala -cp copris-numberlink-v1-0.jar numberlink.Solver -v data/001.a.txt
File = data/001.a.txt
Rows = 5
Cols = 5
Solver =
Options =
BEGIN_solution = 1
Solution = Set(List((0,0), (0,1), (0,2), (0,3), (1,3), (2,3)), List((0,4), (1,4), (2,4), (3,4), (3,3), (3,2), (2,2), (1,2)), List((1,0), (2,0), (3,0), (4,0)), List((1,1), (2,1), (3,1), (4,1), (4,2), (4,3), (4,4)))
Size = 25
.   .   .   .   .   .
7---+---+---+   3
.   .   .   . | . | .
9   1   3   +   +
. | . | . | . | . | .
+   +   +   7   +
. | . | . | .   . | .
+   +   +---+---+
. | . | .   .   .   .
9   +---+---+---1
.   .   .   .   .   .

END_solution = 1
NumOfSolutions >= 1
```

## Performance Evaluation

Solver performance is measured on version 1.0.

• Copris solver was run on Intel Xeon 3.47GHz machine with:
• Ubuntu Linux 12.04 (32 bit)
• Java version "1.6.0_27", OpenJDK Runtime Environment (with "-Xmx2G" option)
• Scala version 2.9.1
• Copris version 2.0.0
• Sugar version 2.0.0
• Glucose version 2.1 (with preprocessing) is used as a SAT solver.

## Source Code

The following shows the source code of the solver (Numberlink-v1-1.scala).

```  1:  /*
2:   * Numberlink Solver in Copris
3:   * by Naoyuki Tamura
5:   */
7:
8:  import jp.kobe_u.copris._
9:  import jp.kobe_u.copris.dsl._
10:  import puzzle._
11:
12:  case class Numberlink(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
13:    def isBlank(cell: Cell) = at(cell) == "-"
14:    def numCells(num: Int) = cells.filter(cell => at(cell) == num.toString)
15:    def show(sol: Set[Seq[Cell]]) {
16:      val arcs = sol.flatMap(_.sliding(2).map(e => (e(0),e(1))).toSet)
17:      def connected(cell1: Cell, cell2: Cell) =
18:        arcs.contains((cell1,cell2)) || arcs.contains((cell2,cell1))
19:      println("." + "   ." * n)
20:      for (i <- 0 until m) {
21:        print("  ")
22:        for (j <- 0 until n) {
23:          val cell = (i,j); val cell1 = (i,j+1)
24:          val x = if (isBlank(cell)) "+" else at(cell)
25:          val e = if (isCell(cell1) && connected(cell, cell1)) "---"
26:                  else "   "
27:          print((x + e).substring(0, 4))
28:        }
29:        println
30:        print(".")
31:        for (j <- 0 until n) {
32:          val cell = (i,j); val cell1 = (i+1,j)
33:          val e = if (isCell(cell1) && connected(cell, cell1)) " | "
34:                  else "   "
35:          print(e + ".")
36:        }
37:        println
38:      }
39:      println
40:    }
41:  }
42:
43:  object Solver extends BoardPuzzleSolver[Numberlink] {
44:    import scala.math.Ordering.Implicits._
45:
47:
48:    def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
50:
51:    def define = {
52:      for (cell <- puzzle.cells; cell1 <- puzzle.adjCells(cell))
53:        int('e(cell,cell1), 0, 1)
54:      for (cell <- puzzle.cells; cell1 <- puzzle.adjCells(cell); if cell < cell1)
55:        add('e(cell,cell1) + 'e(cell1,cell) <= 1)
56:      for (cell <- puzzle.cells) {
57:        val in = puzzle.adjCells(cell).map(cell1 => 'e(cell1,cell))
58:        val ot = puzzle.adjCells(cell).map(cell1 => 'e(cell,cell1))
59:        if (puzzle.isBlank(cell)) {
60:          int('io(cell), 0, 1)
63:        } else {
64:          val numCells = puzzle.numCells(puzzle.num(cell))
65:          if (cell == numCells(0)) {
68:          } else {
71:          }
72:        }
73:      }
74:      val numbers = puzzle.numberCells.map(puzzle.num(_)).toSet
75:      for (cell <- puzzle.cells) {
76:        if (puzzle.isBlank(cell))
77:          int('x(cell), numbers)
78:        else
79:          int('x(cell), puzzle.num(cell))
80:      }
81:      for (cell <- puzzle.cells; cell1 <- puzzle.adjCells(cell))
82:        add(('e(cell,cell1) === 1) ==> ('x(cell) === 'x(cell1)))
83:    }
84:
85:    def showSolution {
86:      def findPath(cell: Cell): Seq[Cell] =
87:        puzzle.adjCells(cell).find(cell1 => solution('e(cell,cell1)) > 0) match {
88:          case None => Seq(cell)
89:          case Some(cell1) => cell +: findPath(cell1)
90:        }
91:      val numbers = puzzle.numberCells.map(puzzle.num(_)).toSet
92:      val sol = for (num <- numbers; cell = puzzle.numCells(num)(0))
93:                yield findPath(cell)
94:      if (quiet == 0) {
95:        println("Solution = " + sol)
96:        println("Size = " + sol.map(_.size).sum)
97:        puzzle.show(sol)
98:      }
99:    }
100:  }
```