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

  • 2020-12-15 Tue Release of version 2.0
  • 2013-10-14 Mon Release of version 1.1
  • 2013-09-01 Sun First release

Download

Version 2.0

Requirements

  • 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)

How to use

scala -cp copris-puzzles-2.0.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-puzzles-2.0.jar hakyuu.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 hakyuu.Solver -o multi -s2 minisat 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-puzzles-2.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
FINISHED CPU 1.62 MEM 4277848 MAXMEM 4277848 STALE 0
<time name="ALL">1690</time>

Performance Evaluation

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.

Finding a solution

Number of instances
Solved within 3600s300
Timeout0
Error (Memory Over etc.)0
Total300
Avg. CPU time3.2
Max. CPU time7.1

Source Code

The following shows the source code of the solver (Hakyuu.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 ../build/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.

Links

Date: 2020-12-18 23:55:54 JST

Author: Naoyuki Tamura

Org version 7.8.02 with Emacs version 25

Validate XHTML 1.0