Slitherlink 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 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
- 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 slitherlink.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 slitherlink.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 slitherlink.Solver -o multi -s2 minisat 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-puzzles-2.0.jar slitherlink.Solver -v data/001.a.txt File = data/001.a.txt Solver = Options = Rows = 4 Cols = 4 BEGIN_solution = 1 Solution = List((0,2), (1,2), (2,2), (2,3), (3,3), (4,3), (4,2), (3,2), (3,1), (2,1), (1,1), (0,1), (0,2)) Size = 13 + +-+ + + 1| | 0 + + + + + | | + + +-+ + 1| 2|1 + +-+ + + 2|3| + + +-+ + 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 840 instances obtainded from http://www.janko.at/Raetsel/Slitherlink/.
Number of instances | |
---|---|
Solved within 3600s | 840 |
Timeout | 0 |
Error (Memory Over etc.) | 0 |
Total | 840 |
Avg. CPU time | 7.5 |
Max. CPU time | 65.4 |
- See log/results.log for more details.
Source Code
The following shows the source code of the solver (Slitherlink.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: }
- 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
- Slitherlink (by Nikoli)
- Wikipedia:Slitherlink
- http://www.janko.at/Raetsel/Slitherlink/