Hakyuu Solver in Copris

Table of Contents

Overview

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

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

Input file format

The following is an example of input file.

8
8
1 1:4 2 2 3:3 4:1 4 5
1 6 6:2 7 3 3:2 8 8
1 1 1 9 3 3 8 8:5
10 1 11 9 9 3 8 12
13 13 13 13 14 14:4 14 15
16:3 16 16 13 17 18 14 15
19 16 16:4 18 18 18:6 15 15
20 20 20:3 18:5 18 15 15:6 21
  • The first line gives the number of rows.
  • The second line gives the number of columns.
  • Each region is specified by its name.
  • The number after the region name specifies the hint.

Example Usage

$ scala -cp copris-hakyuu-v1-0.jar hakyuu.Solver -v data/001.a.txt
File = data/001.a.txt
Solver = 
Options = 
Rows = 8
Cols = 8
BEGIN_solution = 1
Solution = Vector(Vector(1, 4, 1, 2, 3, 1, 2, 1), Vector(3, 1, 2, 1, 4, 2, 1, 3), Vector(5, 2, 7, 3, 6, 1, 4, 5), Vector(1, 6, 1, 2, 1, 5, 2, 1), Vector(2, 3, 5, 1, 2, 4, 3, 2), Vector(3, 5, 1, 4, 1, 2, 1, 3), Vector(1, 2, 4, 1, 3, 6, 5, 4), Vector(2, 1, 3, 5, 4, 1, 6, 1))
Size = 8
 1 4 1 2 3 1 2 1
 3 1 2 1 4 2 1 3
 5 2 7 3 6 1 4 5
 1 6 1 2 1 5 2 1
 2 3 5 1 2 4 3 2
 3 5 1 4 1 2 1 3
 1 2 4 1 3 6 5 4
 2 1 3 5 4 1 6 1
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 (Hakyuu-v1-1.scala).

 1:  /*
 2:   * Hakyuu Solver in Copris
 3:   * by Naoyuki Tamura
 4:   * http://bach.istc.kobe-u.ac.jp/copris/puzzles/hakyuu/
 5:   */
 6:  package hakyuu
 7:  
 8:  import jp.kobe_u.copris._
 9:  import jp.kobe_u.copris.dsl._
10:  import puzzle._
11:  
12:  case class Hakyuu(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
13:    def areaName(cell: Cell) = at(cell).split(":")(0)
14:    val areaNames = cells.map(areaName).toSet
15:    val areaCells =
16:      areaNames.map(name => name -> cells.filter(cell => areaName(cell) == name).toSet).toMap
17:    def isHint(cell: Cell) = at(cell).split(":").size >= 2
18:    def hint(cell: Cell) = at(cell).split(":")(1).toInt
19:    def show(sol: Seq[Seq[Int]]) {
20:      for (i <- 0 until m) {
21:        for (j <- 0 until n)
22:          print("%2d".format(sol(i)(j)))
23:        println
24:      }
25:    }
26:  }
27:  
28:  object Solver extends BoardPuzzleSolver[Hakyuu] {
29:    val name = "hakyuu.Solver"
30:  
31:    def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
32:      Hakyuu(m, n, board)
33:  
34:    def define = {
35:      for (cell <- puzzle.cells)
36:        if (puzzle.isHint(cell))
37:          int('x(cell), puzzle.hint(cell))
38:        else
39:          int('x(cell), 1, puzzle.areaCells(puzzle.areaName(cell)).size)
40:      for (name <- puzzle.areaNames)
41:        add(Alldifferent(puzzle.areaCells(name).map('x(_))))
42:      for (cell <- puzzle.cells) {
43:        val values =
44:          if (puzzle.isHint(cell)) Seq(puzzle.hint(cell))
45:          else 1 to puzzle.areaCells(puzzle.areaName(cell)).size
46:        for (x <- values; (di,dj) <- puzzle.dijs; k <- 1 to x) {
47:          val cell1 = puzzle.move(cell, (k*di,k*dj))
48:          if (puzzle.isCell(cell1))
49:            add(('x(cell) =/= x) || ('x(cell1) =/= x))
50:        }
51:      }
52:    }
53:  
54:    def showSolution {
55:      val sol = for (i <- 0 until puzzle.m)
56:                yield (0 until puzzle.n).map(j => solution('x((i,j))))
57:      if (quiet == 0) {
58:        println("Solution = " + sol)
59:        println("Size = " + sol.size)
60:        puzzle.show(sol)
61:      }
62:    }
63:  }
  • It should be compiled with PuzzleSolver.scala.
  • We assume the maximum size of polyomions not appeared as hints does not exceed 20.

License

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

Links

?????

Date: 2013-12-01 10:40:58 JST

Author: Naoyuki Tamura

Org version 7.8.02 with Emacs version 23

Validate XHTML 1.0