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

  • 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 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-puzzles-2.0.jar shakashaka.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 shakashaka.Solver -o multi -s2 minisat 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-puzzles-2.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((7,1) -> 3, (7,5) -> 0, (1,5) -> 3, (6,7) -> 3, (0,2) -> 2, (5,2) -> 3, (5,1) -> 4, (4,0) -> 4, (6,4) -> 3, (4,7) -> 0, (6,6) -> 4, (3,1) -> 2, (6,1) -> 2, (4,1) -> 0, (6,2) -> 1, (2,0) -> 4, (0,3) -> 0, (4,4) -> 1, (3,0) -> 1, (0,5) -> 2, (3,6) -> 0, (1,1) -> 0, (6,3) -> 0, (3,5) -> 1, (7,3) -> 3, (4,6) -> 3, (4,5) -> 0, (1,4) -> 0, (2,6) -> 1, (0,4) -> 1, (5,7) -> 2, (5,4) -> 0, (3,2) -> 4, (1,3) -> 1, (2,2) -> 1, (5,5) -> 3, (2,7) -> 2, (4,2) -> 2, (2,4) -> 3, (3,7) -> 3, (0,1) -> 1, (5,3) -> 1, (3,3) -> 3, (1,7) -> 0, (2,3) -> 0, (1,2) -> 3, (2,1) -> 3, (6,0) -> 1, (7,2) -> 4, (1,0) -> 1, (5,6) -> 1, (0,6) -> 0, (7,0) -> 4)
Size = 53
#2◤◥□◤◥□■
◤□◢◤□◢■□
◣◢◤□◢#4◤◥
◤◥◣◢#4◤□◢
◣□◥#4◤□◢□
#3◣◢◤□◢◤◥
◤◥◤□◢■◣◢
◣◢◣◢#2□■#1
END_solution = 1
NumOfSolutions >= 1

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 3600s100
Timeout0
Error (Memory Over etc.)0
Total100
Avg. CPU time4.3
Max. CPU time7.3

Source Code

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

Links

Date: 2020-12-18 23:56:14 JST

Author: Naoyuki Tamura

Org version 7.8.02 with Emacs version 25

Validate XHTML 1.0