Shakashaka Solver in Copris

Table of Contents

Overview

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

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

What's New

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

Download

Version 1.0
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-shakashaka-v1-1.jar shakashaka.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-shakashaka-v1-1.jar shakashaka.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-shakashaka-v1-1.jar shakashaka.Solver -o multi -s1 glucose input_file_name

Input file format

The following is an example of input file.

8
8
2 - - - - - - x
- - - - - - x -
- - - - - 4 - -
- - - - 4 - - -
- - - 4 - - - -
3 - - - - - - -
- - - - - x - -
- - - - 2 - x 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" or "5".

Example Usage

$ scala -cp copris-shakashaka-v1-0.jar shakashaka.Solver -v data/001.a.txt
File = data/001.a.txt
Solver = 
Options = 
Rows = 8
Cols = 8
BEGIN_solution = 1
Solution = Map((0,3) -> 0, (4,2) -> 2, (5,7) -> 2, (1,1) -> 0, (7,2) -> 4, (0,5) -> 2, (3,3) -> 3, (0,4) -> 1, (7,1) -> 3, (3,5) -> 1, (6,6) -> 4, (3,7) -> 3, (1,3) -> 1, (4,7) -> 0, (1,0) -> 1, (6,2) -> 1, (2,6) -> 1, (1,2) -> 3, (2,3) -> 0, (2,4) -> 3, (3,6) -> 0, (5,1) -> 4, (2,0) -> 4, (2,1) -> 3, (5,2) -> 3, (4,6) -> 3, (6,7) -> 3, (2,2) -> 1, (0,1) -> 1, (1,7) -> 0, (4,4) -> 1, (4,5) -> 0, (7,5) -> 0, (5,5) -> 3, (6,3) -> 0, (5,4) -> 0, (2,7) -> 2, (3,0) -> 1, (3,2) -> 4, (5,6) -> 1, (7,0) -> 4, (6,4) -> 3, (4,0) -> 4, (5,3) -> 1, (6,1) -> 2, (0,6) -> 0, (3,1) -> 2, (7,3) -> 3, (0,2) -> 2, (1,4) -> 0, (4,1) -> 0, (1,5) -> 3, (6,0) -> 1)
Size = 53
#2◤◥□◤◥□■
◤□◢◤□◢■□
◣◢◤□◢#4◤◥
◤◥◣◢#4◤□◢
◣□◥#4◤□◢□
#3◣◢◤□◢◤◥
◤◥◤□◢■◣◢
◣◢◣◢#2□■#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 (Shakashaka-v1-1.scala).

  1:  /*
  2:   * Shakashaka Solver in Copris
  3:   * by Naoyuki Tamura
  4:   * http://bach.istc.kobe-u.ac.jp/copris/puzzles/shakashaka/
  5:   */
  6:  package shakashaka
  7:  
  8:  import jp.kobe_u.copris._
  9:  import jp.kobe_u.copris.dsl._
 10:  import puzzle._
 11:  
 12:  case class Shakashaka(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
 13:    def isBlank(cell: Cell) = at(cell) == "-"
 14:    def isBlack(cell: Cell) = isNumber(cell) || at(cell) == "x"
 15:    val WH = 0; val NW = 1; val NE = 2; val SE = 3; val SW = 4; val BX = 5
 16:    def show(sol: Map[Cell,Int]) {
 17:      val tiles = Map(WH -> "\u25A1", NW -> "\u25E4", NE -> "\u25E5", SE -> "\u25E2", SW -> "\u25E3", BX -> "\u25A0")
 18:      // val tiles = Map(WH -> "..", NW -> "#/", NE -> "\\#", SE -> "/#", SW -> "#\\", BX -> "##")
 19:      for (i <- 0 until m) {
 20:        for (j <- 0 until n) {
 21:          val cell = (i,j)
 22:          if (isBlank(cell)) print(tiles(sol(cell)))
 23:          else if (isNumber(cell)) print("#" + num(cell))
 24:          else print(tiles(BX))
 25:        }
 26:        println
 27:      }
 28:    }
 29:  }
 30:  
 31:  object Solver extends BoardPuzzleSolver[Shakashaka] {
 32:    val name = "shakashaka.Solver"
 33:  
 34:    def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
 35:      Shakashaka(m, n, board)
 36:  
 37:    def WH = puzzle.WH
 38:    def NW = puzzle.NW; def NE = puzzle.NE; def SE = puzzle.SE; def SW = puzzle.SW
 39:    def BX = puzzle.BX
 40:  
 41:    def define = {
 42:      for (i <- -1 to puzzle.m; j <- -1 to puzzle.n) {
 43:        val cell = (i,j)
 44:        if (! puzzle.isCell(cell) || puzzle.isBlack(cell))
 45:          int('x(cell), BX)
 46:        else
 47:          int('x(cell), Set(WH,NW,NE,SE,SW))
 48:      }
 49:      for (cell <- puzzle.cells; if puzzle.isNumber(cell) && puzzle.num(cell) <= 4) {
 50:        val xs = for (cell1 <- puzzle.adjCells(cell); if puzzle.isBlank(cell1))
 51:                 yield If('x(cell1) =/= WH, Num(1), Num(0))
 52:        add(Add(xs) === puzzle.num(cell))
 53:      }
 54:      def x(cell: Cell, dij: Cell) = 'x(puzzle.move(cell, dij))
 55:      for (cell <- puzzle.cells; if puzzle.isBlank(cell)) {
 56:        add((x(cell,( 0, 0)) === NW) ==> (
 57:           ((x(cell,(-1, 1)) === NW) && (x(cell,( 0, 1)) === WH)) || (x(cell,( 0, 1)) === NE)))
 58:        add((x(cell,( 0, 0)) === NW) ==> (
 59:           ((x(cell,( 1,-1)) === NW) && (x(cell,( 1, 0)) === WH)) || (x(cell,( 1, 0)) === SW)))
 60:        add((x(cell,( 0, 0)) === NE) ==> (
 61:           ((x(cell,(-1,-1)) === NE) && (x(cell,( 0,-1)) === WH)) || (x(cell,( 0,-1)) === NW)))
 62:        add((x(cell,( 0, 0)) === NE) ==> (
 63:           ((x(cell,( 1, 1)) === NE) && (x(cell,( 1, 0)) === WH)) || (x(cell,( 1, 0)) === SE)))
 64:        add((x(cell,( 0, 0)) === SE) ==> (
 65:           ((x(cell,(-1, 1)) === SE) && (x(cell,(-1, 0)) === WH)) || (x(cell,(-1, 0)) === NE)))
 66:        add((x(cell,( 0, 0)) === SE) ==> (
 67:           ((x(cell,( 1,-1)) === SE) && (x(cell,( 0,-1)) === WH)) || (x(cell,( 0,-1)) === SW)))
 68:        add((x(cell,( 0, 0)) === SW) ==> (
 69:           ((x(cell,(-1,-1)) === SW) && (x(cell,(-1, 0)) === WH)) || (x(cell,(-1, 0)) === NW)))
 70:        add((x(cell,( 0, 0)) === SW) ==> (
 71:           ((x(cell,( 1, 1)) === SW) && (x(cell,( 0, 1)) === WH)) || (x(cell,( 0, 1)) === SE)))
 72:      }
 73:      def nEdge(x: Var) = (x === NW) || (x === NE) || (x === BX)
 74:      def eEdge(x: Var) = (x === NE) || (x === SE) || (x === BX)
 75:      def sEdge(x: Var) = (x === SE) || (x === SW) || (x === BX)
 76:      def wEdge(x: Var) = (x === SW) || (x === NW) || (x === BX)
 77:      for (cell <- puzzle.cells) {
 78:        add(((x(cell,(0,0)) === WH) && sEdge(x(cell,(-1, 0)))) ==>
 79:            (sEdge(x(cell,(-1,-1))) || eEdge(x(cell,( 0,-1)))))
 80:        add(((x(cell,(0,0)) === WH) && sEdge(x(cell,(-1, 0)))) ==>
 81:            (sEdge(x(cell,(-1, 1))) || wEdge(x(cell,( 0, 1)))))
 82:        add(((x(cell,(0,0)) === WH) && wEdge(x(cell,( 0, 1)))) ==>
 83:            (wEdge(x(cell,(-1, 1))) || sEdge(x(cell,(-1, 0)))))
 84:        add(((x(cell,(0,0)) === WH) && wEdge(x(cell,( 0, 1)))) ==>
 85:            (wEdge(x(cell,( 1, 1))) || nEdge(x(cell,( 1, 0)))))
 86:        add(((x(cell,(0,0)) === WH) && nEdge(x(cell,( 1, 0)))) ==>
 87:            (nEdge(x(cell,( 1, 1))) || wEdge(x(cell,( 0, 1)))))
 88:        add(((x(cell,(0,0)) === WH) && nEdge(x(cell,( 1, 0)))) ==>
 89:            (nEdge(x(cell,( 1,-1))) || eEdge(x(cell,( 0,-1)))))
 90:        add(((x(cell,(0,0)) === WH) && eEdge(x(cell,( 0,-1)))) ==>
 91:            (eEdge(x(cell,( 1,-1))) || nEdge(x(cell,( 1, 0)))))
 92:        add(((x(cell,(0,0)) === WH) && eEdge(x(cell,( 0,-1)))) ==>
 93:            (eEdge(x(cell,(-1,-1))) || sEdge(x(cell,(-1, 0)))))
 94:      }
 95:    }
 96:  
 97:    def showSolution {
 98:      val sol = {
 99:        for (cell <- puzzle.cells.toSet; if puzzle.isBlank(cell))
100:        yield cell -> solution('x(cell))
101:      }.toMap
102:      if (quiet == 0) {
103:        println("Solution = " + sol)
104:        println("Size = " + sol.size)
105:        puzzle.show(sol)
106:      }
107:    }
108:  }

License

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

Links

?????

Date: 2013-12-01 10:41:39 JST

Author: Naoyuki Tamura

Org version 7.8.02 with Emacs version 23

Validate XHTML 1.0