Slitherlink Solver in Copris

Table of Contents

Overview

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

This Slitherlink solver can find a solution of the given Slitherlink 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-slitherlink-v1-1.jar slitherlink.Solver -v 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-slitherlink-v1-1.jar slitherlink.Solver -v -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-slitherlink-v1-1.jar slitherlink.Solver -v -o multi -s1 glucose input_file_name

Input file format

The following is an example of input file.

4
4
1 - - 0
- - - -
1 - 2 1
- 2 3 -
  • 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-slitherlink-v1-0.jar slitherlink.Solver -v data/001.a.txt
File = data/001.a.txt
Rows = 4
Cols = 4
Solver = 
Options = 
BEGIN_solution = 1
Solution = List((4,2), (3,2), (3,1), (2,1), (1,1), (0,1), (0,2), (1,2), (2,2), (2,3), (3,3), (4,3), (4,2))
Size = 13
+ +-+ + + 
 1| |  0 
+ + + + + 
  | |    
+ + +-+ + 
 1|  2|1 
+ +-+ + + 
   2|3|  
+ + +-+ + 
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 (Slitherlink-v1-1.scala).

  1:  /*
  2:   * Slitherlink Solver in Copris
  3:   * by Naoyuki Tamura
  4:   * http://bach.istc.kobe-u.ac.jp/copris/puzzles/slitherlink/
  5:   */
  6:  package slitherlink
  7:  
  8:  import jp.kobe_u.copris._
  9:  import jp.kobe_u.copris.dsl._
 10:  import puzzle._
 11:  
 12:  case class Slitherlink(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
 13:    def isBlank(cell: Cell) = at(cell) == "-"
 14:    def edges(cell: Cell): Seq[(Grid,Grid)] = {
 15:      val (i,j) = cell
 16:      val es = Seq(((i,j),(i,j+1)), ((i,j),(i+1,j)), ((i,j+1),(i+1,j+1)), ((i+1,j),(i+1,j+1)))
 17:      es.flatMap(e => Seq(e,e.swap))
 18:    }
 19:    def show(sol: Seq[Grid]) {
 20:      val arcs = sol.sliding(2).map(e => (e(0),e(1))).toSet
 21:      def connected(grid1: Grid, grid2: Grid) =
 22:        arcs.contains((grid1,grid2)) || arcs.contains((grid2,grid1))
 23:      for (i <- 0 to m) {
 24:        for (j <- 0 to n) {
 25:          print("+")
 26:          if (j+1 <= n && connected((i,j), (i,j+1))) print("-")
 27:          else print(" ")
 28:        }
 29:        println
 30:        if (i < m) {
 31:          for (j <- 0 to n) {
 32:            if (connected((i,j), (i+1,j))) print("|")
 33:            else print(" ")
 34:            if (j < n) {
 35:              if (isNumber((i,j))) print(at((i,j))) else print(" ")
 36:            }
 37:          }
 38:          println
 39:        }
 40:      }
 41:    }
 42:  }
 43:  
 44:  object Solver extends BoardPuzzleSolver[Slitherlink] {
 45:    import scala.math.Ordering.Implicits._
 46:  
 47:    val name = "slitherlink.Solver"
 48:    var cycles: Set[Seq[Grid]] = _
 49:  
 50:    def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
 51:      Slitherlink(m, n, board)
 52:  
 53:    def define = {
 54:      for (grid <- puzzle.grids; grid1 <- puzzle.adjGrids(grid))
 55:        int('e(grid,grid1), 0, 1)
 56:      for (grid <- puzzle.grids; grid1 <- puzzle.adjGrids(grid); if grid < grid1)
 57:        add('e(grid,grid1) + 'e(grid1,grid) <= 1)
 58:      for (grid <- puzzle.grids) {
 59:        val in = puzzle.adjGrids(grid).map(grid1 => 'e(grid1,grid))
 60:        val ot = puzzle.adjGrids(grid).map(grid1 => 'e(grid,grid1))
 61:        int('io(grid), 0, 1)
 62:        add('io(grid) === Add(in))
 63:        add('io(grid) === Add(ot))
 64:      }
 65:      for (cell <- puzzle.cells; if puzzle.isNumber(cell)) {
 66:        val x = puzzle.num(cell)
 67:        add(Add(puzzle.edges(cell).map(edge => 'e(edge._1,edge._2))) === x)
 68:      }
 69:    }
 70:  
 71:    def checkSolution: Boolean = {
 72:      val nodes = puzzle.grids.filter(grid => solution('io(grid)) > 0).toSet
 73:      def nextGrids(grid: Grid) =
 74:        puzzle.adjGrids(grid).filter(grid1 => solution('e(grid,grid1)) > 0).toSet
 75:      val arcs = nodes.map(grid => grid -> nextGrids(grid)).toMap
 76:      cycles = getCycles(nodes, arcs)
 77:      def goodCycle(cycle: Seq[Grid]) = {
 78:        val cycleArcs = cycle.sliding(2).map(e => (e(0),e(1))).toSet
 79:        puzzle.numberCells.forall(cell => {
 80:          val es = for (e <- puzzle.edges(cell))
 81:                   yield if (cycleArcs.contains(e)) 1 else 0
 82:          es.sum == puzzle.num(cell)
 83:        })
 84:      }
 85:      if (verbose >= 2)
 86:        println("Components = " + cycles.size)
 87:      cycles.find(cycle => goodCycle(cycle)) match {
 88:        case None =>
 89:          false
 90:        case Some(cycle) => {
 91:          cycles = Set(cycle); true
 92:        }
 93:      }
 94:    }
 95:    def addNegation {
 96:      for (cycle <- cycles) {
 97:        add(Or(cycle.sliding(2).map(e => 'e(e(0),e(1)) === 0).toSeq))
 98:        add(Or(cycle.reverse.sliding(2).map(e => 'e(e(0),e(1)) === 0).toSeq))
 99:      }
100:    }
101:    override def findFirstSolution = findIncremental(true, checkSolution, addNegation)
102:    override def findNextSolution = findIncremental(false, checkSolution, addNegation)
103:  
104:    def showSolution {
105:      // Cycle
106:      require(cycles.size == 1)
107:      val sol = cycles.head
108:      if (quiet == 0) {
109:        println("Solution = " + sol)
110:        println("Size = " + sol.size)
111:        puzzle.show(sol)
112:      }
113:    }
114:  }

License

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

Links

?????

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

Author: Naoyuki Tamura

Org version 7.8.02 with Emacs version 23

Validate XHTML 1.0