Fillomino Solver in Copris

Overview

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.

What's New

• 2013-10-13 Sun Release of version 1.1
• 2013-09-01 Sun First release

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-fillomino-v1-1.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-fillomino-v1-1.jar fillomino.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-fillomino-v1-1.jar fillomino.Solver -o multi -s1 glucose input_file_name
```

Input file format

The following is an example of input file.

```5
5
3 - - 5 -
- 1 - - 2
- 4 - 2 -
4 - - 3 -
- 4 - - 4
```
• 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-fillomino-v1-0.jar fillomino.Solver -v data/001.a.txt
File = data/001.a.txt
Solver =
Options =
Rows = 5
Cols = 5
BEGIN_solution = 1
Solution = Vector(Vector(3, 5, 5, 5, 2), Vector(3, 1, 5, 5, 2), Vector(3, 4, 2, 2, 4), Vector(4, 4, 3, 3, 4), Vector(1, 4, 3, 4, 4))
Size = 5
3  5  5  5  2
3  1  5  5  2
3  4  2  2  4
4  4  3  3  4
1  4  3  4  4
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.

Source Code

The following shows the source code of the solver (Fillomino-v1-1.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)
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))
61:        add(('in(cell) === 0) ==> ('s(cell) === 'x(cell)))
62:      }
63:    }
64:
65:    def checkSolution: Boolean = {
66:      val nodes = puzzle.cells.toSet
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)))
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)
81:    }
84:        val cs = for (cell <- puzzle.cells; if ! puzzle.isNumber(cell))
85:                 yield 'x(cell) =/= solution('x(cell))
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))
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 PuzzleSolver.scala.
• We assume the maximum size of polyomions not appeared as hints does not exceed 20.