Akari Solver in Copris

Table of Contents

Overview

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

This Akari solver can find a solution of the given Akari puzzle.

What's New

  • 2013-10-13 Sun 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-akari-v1-1.jar akari.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-akari-v1-1.jar akari.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-akari-v1-1.jar akari.Solver -o multi -s1 glucose input_file_name

Input file format

The following is an example of input file.

10
10
1 - - - - - - - - 1
- - - x - - - - - -
- x - - - 2 - - x -
- - - - - - - 1 - -
- - - 4 - - - - - -
- - - - - - 2 - - -
- - 2 - - - - - - -
- x - - 2 - - - x -
- - - - - - 0 - - -
1 - - - - - - - - 1
  • 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 "-".
  • Black cells are represented by "x".

Example Usage

$ scala -cp copris-akari-v1-0.jar akari.Solver -v data/001.a.txt
File = data/001.a.txt
Rows = 10
Cols = 10
Solver = 
Options = 
BEGIN_solution = 1
Solution = Set((8,4), (4,2), (5,7), (7,2), (3,3), (6,6), (1,0), (2,6), (0,8), (3,8), (9,1), (4,4), (7,5), (5,3), (8,9), (6,1), (1,5))
Size = 17
 1 - - - - - - - @ 1
 @ - - x - @ - - - -
 - x - - - 2 @ - x -
 - - - @ - - - 1 @ -
 - - @ 4 @ - - - - -
 - - - @ - - 2 @ - -
 - @ 2 - - - @ - - -
 - x @ - 2 @ - - x -
 - - - - @ - 0 - - @
 1 @ - - - - - - - 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 (Akari-v1-1.scala).

 1:  /*
 2:   * Akari Solver in Copris
 3:   * by Naoyuki Tamura
 4:   * http://bach.istc.kobe-u.ac.jp/copris/puzzles/akari/
 5:   */
 6:  package akari
 7:  
 8:  import jp.kobe_u.copris._
 9:  import jp.kobe_u.copris.dsl._
10:  import puzzle._
11:  
12:  case class Akari(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
13:    def isBlank(cell: Cell) = at(cell) == "-"
14:    def isBlack(cell: Cell) = at(cell) == "x"
15:    val lines = {
16:      def seq(cell: Cell, dij: Cell): Seq[Cell] =
17:        if (! isCell(cell) || ! isBlank(cell)) Seq.empty
18:        else cell +: seq(move(cell, dij), dij)
19:      val vLines = for ((i,j) <- cells; if ! isCell((i-1,j)) || ! isBlank((i-1,j)))
20:                   yield seq((i,j), (1,0)).toSet
21:      val hLines = for ((i,j) <- cells; if ! isCell((i,j-1)) || ! isBlank((i,j-1)))
22:                   yield seq((i,j), (0,1)).toSet
23:      vLines ++ hLines
24:    }
25:    def show(sol: Set[Cell]) {
26:      for (i <- 0 until m) {
27:        for (j <- 0 until n) {
28:          val cell = (i,j)
29:          if (sol.contains(cell)) print(" @")
30:          else print(" " + at(cell))
31:        }
32:        println
33:      }
34:    }
35:  }
36:  
37:  object Solver extends BoardPuzzleSolver[Akari] {
38:    val name = "akari.Solver"
39:  
40:    def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
41:      Akari(m, n, board)
42:  
43:    def define = {
44:      for (cell <- puzzle.cells; if puzzle.isBlank(cell))
45:        int('x(cell), 0, 1)
46:      for ((cell) <- puzzle.cells; if puzzle.isNumber(cell)) {
47:        val xs = puzzle.adjCells(cell, puzzle.isBlank).map('x(_))
48:        add(Add(xs) === puzzle.num(cell))
49:      }
50:      val lines = puzzle.lines
51:      for (k <- 0 until lines.size) {
52:        int('l(k), 0, 1)
53:        add('l(k) === Add(lines(k).map(cell => 'x(cell))))
54:      }
55:      for (cell <- puzzle.cells; if puzzle.isBlank(cell)) {
56:        val ks = (0 until lines.size).filter(k => lines(k).contains(cell))
57:        add(Or(ks.map(k => 'l(k) === 1)))
58:      }
59:    }
60:  
61:    def showSolution {
62:      // Set of light cell positions
63:      val sol =
64:        for (cell <- puzzle.cells.toSet; if puzzle.isBlank(cell) && solution('x(cell)) > 0)
65:        yield cell
66:      if (quiet == 0) {
67:        println("Solution = " + sol)
68:        println("Size = " + sol.size)
69:        puzzle.show(sol)
70:      }
71:    }
72:  }

License

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

Links

?????

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

Author: Naoyuki Tamura

Org version 7.8.02 with Emacs version 23

Validate XHTML 1.0