Numberlink Solver in Copris

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

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

Download

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.

Finding a solution

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

License

This software is distributed under the BSD 3-Clause License. See LICENSE.txt.

Links

?????

Date: 2013-12-01 10:41:28 JST

Author: Naoyuki Tamura

Org version 7.8.02 with Emacs version 23

Validate XHTML 1.0