Hashiwokakero Solver in Copris

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.

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)

• Scala version 2.12 to be installed
  • Other Scala version is not binary compatible with version 2.12.
• Copris (included in the package)
• Sugar (included in the package)
• Sat4j Core (included in the package)

scala -cp copris-puzzles-2.0.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-puzzles-2.0.jar hashiwokakero.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 hashiwokakero.Solver -o multi -s2 minisat input_file_name

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.

The following shows the source code of the solver (Hashiwokakero.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:  }

• It should be compiled with ../build/PuzzleSolver.scala.

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

• 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
• Hashiwokakero (by Nikoli)
• Wikipedia:Hashiwokakero
• http://www.janko.at/Raetsel/Hashi/