Hashiwokakero Solver in Copris

Table of Contents

Overview

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

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

Input file format

The following is an example of input file.

9
9
- 3 - 3 - - - - 2
- - 3 - - - 1 - -
2 - - 2 - 3 - - 4
- - 3 - 4 - - 2 -
3 - - - - - - - 3
- 2 - - 5 - 3 - -
4 - - 3 - 1 - - 1
- - 1 - - - 2 - -
3 - - - - 3 - 2 -
  • 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-hashiwokakero-v1-0.jar hashiwokakero.Solver -v data/001.a.txt 
File = data/001.a.txt
Rows = 9
Cols = 9
Solver = 
Options = 
BEGIN_solution = 1
Solution = Map(((0,3),(0,8)) -> 1, ((2,5),(2,8)) -> 1, ((1,2),(1,6)) -> 1, ((8,0),(8,5)) -> 2, ((3,7),(8,7)) -> 1, ((6,0),(6,3)) -> 2, ((4,0),(6,0)) -> 1, ((2,0),(4,0)) -> 2, ((0,1),(0,3)) -> 2, ((0,1),(5,1)) -> 1, ((2,8),(4,8)) -> 2, ((5,1),(5,4)) -> 1, ((5,6),(7,6)) -> 1, ((7,2),(7,6)) -> 1, ((6,3),(6,5)) -> 1, ((0,8),(2,8)) -> 1, ((3,4),(5,4)) -> 2, ((8,5),(8,7)) -> 1, ((2,3),(2,5)) -> 2, ((4,8),(6,8)) -> 1, ((1,2),(3,2)) -> 2, ((3,2),(3,4)) -> 1, ((6,0),(8,0)) -> 1, ((5,4),(5,6)) -> 2, ((3,4),(3,7)) -> 1)
Size = 25
 .  3 === 3 ------------ 2 
 .  |  3 --------- 1  .  | 
 2  |  #  2 === 3 ------ 4 
 #  |  3 --- 4 ------ 2  # 
 3  |  .  .  #  .  .  |  3 
 |  2 ------ 5 === 3  |  | 
 4 ====== 3 --- 1  |  |  1 
 |  .  1 --------- 2  |  . 
 3 ============ 3 --- 2  . 
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 (Hashiwokakero-v1-1.scala).

  1:  /*
  2:   * Hashiwokakero Solver in Copris
  3:   * by Naoyuki Tamura
  4:   * http://bach.istc.kobe-u.ac.jp/copris/puzzles/hashiwokakero/
  5:   */
  6:  package hashiwokakero
  7:  
  8:  import jp.kobe_u.copris._
  9:  import jp.kobe_u.copris.dsl._
 10:  import puzzle._
 11:  
 12:  case class Hashiwokakero(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
 13:    import scala.math.Ordering.Implicits._
 14:  
 15:    def isBlank(cell: Cell) = at(cell) == "-"
 16:    def edge(cell: Cell, cell1: Cell) = if (cell < cell1) (cell,cell1) else (cell1,cell)
 17:    def edgesFrom(cell: Cell) = {
 18:      def findNumberCell(cell1: Cell, dij: Cell): Option[Cell] =
 19:        if (! isCell(cell1)) None
 20:        else if (isNumber(cell1)) Some(cell1)
 21:        else findNumberCell(move(cell1, dij), dij)
 22:      for (dij <- dijs; cell1 <- findNumberCell(move(cell, dij), dij))
 23:      yield edge(cell, cell1)
 24:    }
 25:    val edges = numberCells.flatMap(cell => edgesFrom(cell)).toSet
 26:    def cross(edge1: (Cell,Cell), edge2: (Cell,Cell)) = {
 27:      val ((i1,j1),(i2,j2)) = edge1; val ((i3,j3),(i4,j4)) = edge2
 28:      (i1 == i2 && i3 < i1 && i1 < i4 && j3 == j4 && j1 < j3 && j3 < j2) ||
 29:      (j1 == j2 && j3 < j1 && j1 < j4 && i3 == i4 && i1 < i3 && i3 < i2)
 30:    }
 31:    def show(sol: Map[(Cell,Cell),Int]) {
 32:      val v = (for {
 33:        (cell1,cell2) <- sol.keySet; if cell1._2 == cell2._2
 34:        d = sol((cell1,cell2)); if d > 0
 35:        cell <- (cell1._1+1 until cell2._1).map(i => (i,cell1._2))
 36:      } yield cell -> d).toMap
 37:      val h = (for {
 38:        (cell1,cell2) <- sol.keySet; if cell1._1 == cell2._1
 39:        d = sol((cell1,cell2)); if d > 0
 40:        cell <- (cell1._2+1 until cell2._2).map(j => (cell1._1,j))
 41:      } yield cell -> d).toMap
 42:      for (i <- 0 until m) {
 43:        for (j <- 0 until n) {
 44:          val cell = (i,j)
 45:          if (isNumber(cell)) print(" " + at(cell) + " ")
 46:          else if (v.getOrElse(cell, 0) == 1) print(" | ")
 47:          else if (v.getOrElse(cell, 0) == 2) print(" # ")
 48:          else if (h.getOrElse(cell, 0) == 1) print("---")
 49:          else if (h.getOrElse(cell, 0) == 2) print("===")
 50:          else print(" . ")
 51:        }
 52:        println
 53:      }
 54:    }
 55:  }
 56:  
 57:  object Solver extends BoardPuzzleSolver[Hashiwokakero] {
 58:    import scala.math.Ordering.Implicits._
 59:  
 60:    val name = "hashiwokakero.Solver"
 61:    var bridgeComponents: Set[Set[Cell]] = _
 62:  
 63:    def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
 64:      Hashiwokakero(m, n, board)
 65:  
 66:    def define = {
 67:      for (edge <- puzzle.edges)
 68:        int('e(edge), 0, 2)
 69:      for (cell <- puzzle.numberCells)
 70:        add(Add(puzzle.edgesFrom(cell).map('e(_))) === puzzle.num(cell))
 71:      for (edge1 <- puzzle.edges; edge2 <- puzzle.edges
 72:           if edge1 < edge2 && puzzle.cross(edge1, edge2))
 73:        add(('e(edge1) === 0) || ('e(edge2) === 0))
 74:    }
 75:  
 76:    def checkSolution: Boolean = {
 77:      val nodes = puzzle.numberCells.toSet
 78:      val edges = puzzle.edges.filter(edge => solution('e(edge)) > 0)
 79:      def connectedCells(cell: Cell) =
 80:        nodes.filter(cell1 => edges.contains(puzzle.edge(cell, cell1)))
 81:      val arcs = nodes.map(cell => cell -> connectedCells(cell)).toMap
 82:      bridgeComponents = getComponents(nodes, arcs)
 83:      if (verbose >= 2)
 84:        println("Components = " + bridgeComponents.size)
 85:      bridgeComponents.size == 1
 86:    }
 87:    def addNegation {
 88:      for (component <- bridgeComponents) {
 89:        val es = for {
 90:          cell <- component; edge <- puzzle.edgesFrom(cell)
 91:          if component.contains(edge._1) && component.contains(edge._2)
 92:          e = solution('e(edge)); if e > 0
 93:        } yield 'e(edge) =/= e
 94:        add(Or(es))
 95:      }
 96:    }
 97:    override def findFirstSolution = findIncremental(true, checkSolution, addNegation)
 98:    override def findNextSolution = findIncremental(false, checkSolution, addNegation)
 99:  
100:    def showSolution {
101:      require(bridgeComponents.size == 1)
102:      val component = bridgeComponents.head
103:      val sol = (for {
104:        cell <- component; edge <- puzzle.edgesFrom(cell)
105:        if component.contains(edge._1) && component.contains(edge._2)
106:        e = solution('e(edge)); if e > 0
107:      } yield edge -> e).toMap
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:02 JST

Author: Naoyuki Tamura

Org version 7.8.02 with Emacs version 23

Validate XHTML 1.0