Numberlink Solver in Copris
- Top
- Akari
- Fillomino
- Hakyuu
- Hashiwokakero
- Heyawake
- Hitori
- Kakuro
- Kurodoko
- Masyu
- Nonogram
- Numberlink
- Nurikabe
- Polarium
- Shakashaka
- Shikaku
- Slitherlink
- Sokoban
- Sudoku
- Yajilin
Table of Contents
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
- Release of version 2.0
- Release of version 1.1
- First release
Download
- Version 2.0
-
- Scala jar file: ../build/copris-puzzles-2.0.jar (1575981 bytes)
- Source file: ../build/copris-puzzles-src-2.0.zip (29766 bytes)
Requirements
How to use
scala -cp copris-puzzles-2.0.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-puzzles-2.0.jar numberlink.Solver -o multi input_file_name
If you have a SAT solver (such as MiniSat, GlueMiniSat) installed on your computer, you can use it to get better performance. Specify the full path of the SAT solver program with "-s1" or "-s2" option.
scala -cp copris-puzzles-2.0.jar numberlink.Solver -o multi -s2 minisat 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-puzzles-2.0.jar numberlink.Solver -v data/001.a.txt File = data/001.a.txt Solver = Options = Rows = 5 Cols = 5 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 2.0.
- Copris solver was run on Intel Xeon 3.6Hz machine with:
- Ubuntu Linux 20.04 (64 bit)
- Java version "1.8.0_275", OpenJDK Runtime Environment (with "-Xmx2G" option)
- Scala version 2.12.5
- Copris version 2.3.1
- Sugar version 2.3.4
- GlueMiniSat version 2.2.10 (with preprocessing) is used as a SAT solver.
Finding a solution
- We used 280 instances obtainded from http://www.janko.at/Raetsel/Arukone/ (2014-06).
Number of instances | |
---|---|
Solved within 3600s | 278 |
Timeout | 3 |
Error (Memory Over etc.) | 0 |
Total | 281 |
Avg. CPU time | 7.8 |
Max. CPU time | 633.4 |
- See log/results.log for more details.
Source Code
The following shows the source code of the solver (Numberlink.scala).
1: /* 2: * Numberlink Solver in Copris 3: * by Naoyuki Tamura 4: * http://bach.istc.kobe-u.ac.jp/copris/puzzles/numberlink/ 5: */ 6: package numberlink 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: 46: val name = "numberlink.Solver" 47: 48: def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) = 49: Numberlink(m, n, board) 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) 61: add('io(cell) === Add(in)) 62: add('io(cell) === Add(ot)) 63: } else { 64: val numCells = puzzle.numCells(puzzle.num(cell)) 65: if (cell == numCells(0)) { 66: add(Add(in) === 0) 67: add(Add(ot) === 1) 68: } else { 69: add(Add(in) === 1) 70: add(Add(ot) === 0) 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: }
- It should be compiled with ../build/PuzzleSolver.scala.
License
This software is distributed under the BSD 3-Clause License. See LICENSE.
Links
- Copris (Constraint Programming DSL embedded in Scala)
- Sugar (an award winning Constraint Solver)
- Default constraint solver used in Copris
- Sat4j (SAT solver in Java)
- Default SAT solver used in Copris
- Numberlink (by Nikoli)
- Wikipedia:Numberlink
- http://www.janko.at/Raetsel/Arukone/