Fillomino Solver in Copris

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

This Fillomino solver can find a solution of the given Fillomino 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 fillomino.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 fillomino.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 fillomino.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 (Fillomino.scala).

  1:  /*
  2:   * Fillomino Solver in Copris
  3:   * by Naoyuki Tamura
  4:   * http://bach.istc.kobe-u.ac.jp/copris/puzzles/fillomino/
  5:   */
  6:  package fillomino
  7:  
  8:  import jp.kobe_u.copris._
  9:  import jp.kobe_u.copris.dsl._
 10:  import puzzle._
 11:  
 12:  case class Fillomino(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
 13:    def isBlank(cell: Cell) = at(cell) == "-"
 14:    val maxRegionSize = math.max(20, numberCells.map(num(_)).max)
 15:    def show(sol: Seq[Seq[Int]]) {
 16:      for (i <- 0 until m) {
 17:        for (j <- 0 until n)
 18:          print("%3d".format(sol(i)(j)))
 19:        println
 20:      }
 21:    }
 22:  }
 23:  
 24:  object Solver extends BoardPuzzleSolver[Fillomino] {
 25:    import scala.math.Ordering.Implicits._
 26:  
 27:    val name = "fillomino.Solver"
 28:    var badPairOfRegions: Set[(Set[Cell],Set[Cell])] = _
 29:  
 30:    def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
 31:      Fillomino(m, n, board)
 32:  
 33:    def define = {
 34:      // Numbers
 35:      for (cell <- puzzle.cells)
 36:        if (puzzle.isNumber(cell))
 37:          int('x(cell), puzzle.num(cell))
 38:        else
 39:          int('x(cell), 1, puzzle.maxRegionSize)
 40:      // Construct each region as a spanning tree
 41:      for (cell <- puzzle.cells; cell1 <- puzzle.adjCells(cell))
 42:        int('e(cell,cell1), 0, 1)
 43:      for (cell <- puzzle.cells; cell1 <- puzzle.adjCells(cell); if cell < cell1)
 44:        add('e(cell,cell1) + 'e(cell1,cell) <= 1)
 45:      for (cell <- puzzle.cells) {
 46:        val in = puzzle.adjCells(cell).map(cell1 => 'e(cell1,cell))
 47:        int('in(cell), 0, 1)
 48:        add('in(cell) === Add(in))
 49:      }
 50:      // Each region consists of the same number cells
 51:      for (cell <- puzzle.cells; cell1 <- puzzle.adjCells(cell); if cell < cell1)
 52:        add((('e(cell,cell1) === 1) || ('e(cell1,cell) === 1)) ==>
 53:            ('x(cell) === 'x(cell1)))
 54:      // Size of each region should be equal to the number
 55:      for (cell <- puzzle.cells)
 56:        int('s(cell), 1, puzzle.maxRegionSize)
 57:      for (cell <- puzzle.cells) {
 58:        val s = for (cell1 <- puzzle.adjCells(cell))
 59:                yield If('e(cell,cell1) === 0, Num(0), 's(cell1))
 60:        add('s(cell) === Add(s) + 1)
 61:        add(('in(cell) === 0) ==> ('s(cell) === 'x(cell)))
 62:      }
 63:    }
 64:  
 65:    def checkSolution: Boolean = {
 66:      val nodes = puzzle.cells.toSet
 67:      def adjs(cell: Cell) = puzzle.adjCells(cell).toSet.filter {
 68:        cell1 => solution('e(cell,cell1)) > 0 || solution('e(cell1,cell)) > 0
 69:      }
 70:      val arcs = (for (cell <- puzzle.cells) yield cell -> adjs(cell)).toMap
 71:      val components = getComponents(nodes, arcs)
 72:      def bad(r1: Set[Cell], r2: Set[Cell]) =
 73:        r1.exists(cell1 => puzzle.adjCells(cell1).exists(cell2 => r2.contains(cell2)))
 74:      badPairOfRegions = for {
 75:        (size,regions) <- components.groupBy(_.size).toSet
 76:        Seq(r1,r2) <- regions.toSeq.combinations(2); if bad(r1, r2)
 77:      } yield (r1,r2)
 78:      if (verbose >= 2)
 79:        println("badPairOfRegions = " + badPairOfRegions.size)
 80:      badPairOfRegions.isEmpty
 81:    }
 82:    def addNegation {
 83:      if (badPairOfRegions.isEmpty) {
 84:        val cs = for (cell <- puzzle.cells; if ! puzzle.isNumber(cell))
 85:                 yield 'x(cell) =/= solution('x(cell))
 86:        add(Or(cs))
 87:      } else {
 88:        for ((r1,r2) <- badPairOfRegions) {
 89:          val cs = for (cell <- r1 ++ r2; if ! puzzle.isNumber(cell))
 90:                   yield 'x(cell) =/= solution('x(cell))
 91:          add(Or(cs))
 92:        }
 93:      }
 94:    }
 95:    override def findFirstSolution = findIncremental(true, checkSolution, addNegation)
 96:    override def findNextSolution = findIncremental(false, checkSolution, addNegation)
 97:  
 98:    def showSolution {
 99:      val sol = for (i <- 0 until puzzle.m)
100:                yield (0 until puzzle.n).map(j => solution('x((i,j))))
101:      if (quiet == 0) {
102:        println("Solution = " + sol)
103:        println("Size = " + sol.size)
104:        puzzle.show(sol)
105:      }
106:    }
107:  }

• It should be compiled with ../build/PuzzleSolver.scala.
• We assume the maximum size of polyomions not appeared as hints does not exceed 20.

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