Hakyuu Solver in Copris
- Top
- Akari
- Fillomino
- Hakyuu
- Hashiwokakero
- Heyawake
- Hitori
- Kakuro
- Kurodoko
- Masyu
- Nonogram
- Numberlink
- Nurikabe
- Polarium
- Shakashaka
- Shikaku
- Slitherlink
- Sokoban
- Sudoku
- Yajilin
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
- Release of version 2.0
- Release of version 1.1
- First release
Download
- 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)
Requirements
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
- We used 300 instances obtainded from http://www.janko.at/Raetsel/Hakyuu/ (2013-08).
Number of instances | |
---|---|
Solved within 3600s | 300 |
Timeout | 0 |
Error (Memory Over etc.) | 0 |
Total | 300 |
Avg. CPU time | 3.2 |
Max. CPU time | 7.1 |
- See log/results.log for more details.
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
- 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
- Ripple Effect (by Nikoli)
- Wikipedia:Ripple Effect (puzzle)
- http://www.janko.at/Raetsel/Hakyuu/