Kakuro Solver in Copris

Table of Contents

Overview

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

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

What's New

  • 2013-10-14 Mon 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-kakuro-v1-1.jar kakuro.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-kakuro-v1-1.jar kakuro.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-kakuro-v1-1.jar kakuro.Solver -o multi -s1 glucose input_file_name

Input file format

The following is an example of input file.

10
12
0\0 0\0 16\0 15\0 0\0 20\0 17\0 0\0 0\0 0\0 6\0 3\0
0\0 23\7 - - 0\16 - - 16\0 0\0 10\4 - -
0\23 - - - 4\23 - - - 4\6 - - -
0\16 - - - - - 14\16 - - - - 0\0
0\13 - - 11\7 - - - 34\3 - - 16\0 0\0
0\0 0\3 - - 17\7 - - - 17\3 - - 17\0
0\0 0\0 10\12 - - 17\23 - - - 24\3 - -
0\0 4\29 - - - - 16\34 - - - - -
0\6 - - - 0\24 - - - 0\23 - - -
0\3 - - 0\0 0\0 0\17 - - 0\10 - - 0\0
  • The first line gives the number of rows, and the row size of each block (optional).
  • The second line gives the number of columns, and the column size of each block (optional).
  • Hint cells are represented by a pair of the sum in row and the sum in column (0 means no hint).
  • Blank cells are represented by "-".

Example Usage

$ scala -cp copris-kakuro-v1-0.jar kakuro.Solver data/001.a.txt
BEGIN_solution = 1
Solution = Map((4,2) -> 4, (5,7) -> 4, (3,4) -> 3, (4,9) -> 2, (7,2) -> 7, (2,11) -> 2, (8,5) -> 8, (3,3) -> 2, (3,5) -> 4, (6,10) -> 1, (6,6) -> 8, (7,9) -> 9, (1,11) -> 1, (3,7) -> 7, (1,3) -> 4, (9,7) -> 8, (7,8) -> 8, (2,10) -> 1, (9,9) -> 7, (7,10) -> 4, (2,6) -> 8, (1,2) -> 3, (2,3) -> 9, (6,11) -> 2, (8,6) -> 7, (8,10) -> 6, (2,5) -> 6, (5,9) -> 1, (9,6) -> 9, (2,1) -> 8, (5,2) -> 2, (4,6) -> 4, (6,7) -> 6, (9,2) -> 2, (8,11) -> 9, (2,9) -> 3, (2,2) -> 6, (3,8) -> 3, (9,1) -> 1, (1,6) -> 9, (3,9) -> 4, (4,4) -> 1, (3,10) -> 2, (4,5) -> 2, (8,3) -> 2, (7,5) -> 9, (5,5) -> 1, (6,3) -> 3, (2,7) -> 9, (3,2) -> 1, (7,7) -> 7, (5,6) -> 2, (6,8) -> 9, (5,10) -> 2, (6,4) -> 9, (5,3) -> 1, (8,2) -> 1, (8,9) -> 8, (8,7) -> 9, (7,11) -> 6, (7,4) -> 8, (3,1) -> 6, (9,10) -> 3, (7,3) -> 5, (4,1) -> 9, (8,1) -> 3, (4,8) -> 1, (1,5) -> 7, (1,10) -> 3)
Size = 69
[ 0\0 ][ 0\0 ][16\0 ][15\0 ][ 0\0 ][20\0 ][17\0 ][ 0\0 ][ 0\0 ][ 0\0 ][ 6\0 ][ 3\0 ]
[ 0\0 ][23\7 ]   3      4   [ 0\16]   7      9   [16\0 ][ 0\0 ][10\4 ]   3      1   
[ 0\23]   8      6      9   [ 4\23]   6      8      9   [ 4\6 ]   3      1      2   
[ 0\16]   6      1      2      3      4   [14\16]   7      3      4      2   [ 0\0 ]
[ 0\13]   9      4   [11\7 ]   1      2      4   [34\3 ]   1      2   [16\0 ][ 0\0 ]
[ 0\0 ][ 0\3 ]   2      1   [17\7 ]   1      2      4   [17\3 ]   1      2   [17\0 ]
[ 0\0 ][ 0\0 ][10\12]   3      9   [17\23]   8      6      9   [24\3 ]   1      2   
[ 0\0 ][ 4\29]   7      5      8      9   [16\34]   7      8      9      4      6   
[ 0\6 ]   3      1      2   [ 0\24]   8      7      9   [ 0\23]   8      6      9   
[ 0\3 ]   1      2   [ 0\0 ][ 0\0 ][ 0\17]   9      8   [ 0\10]   7      3   [ 0\0 ]
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 (Kakuro-v1-1.scala).

 1:  /*
 2:   * Kakuro Solver in Copris
 3:   * by Naoyuki Tamura
 4:   * http://bach.istc.kobe-u.ac.jp/copris/puzzles/kakuro/
 5:   */
 6:  package kakuro
 7:  
 8:  import jp.kobe_u.copris._
 9:  import jp.kobe_u.copris.dsl._
10:  import puzzle._
11:  
12:  case class Kakuro(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
13:    def isBlank(cell: Cell) = at(cell) == "-"
14:    def isHint(cell: Cell) = at(cell).matches("""\d+\\\d+""")
15:    def hint(cell: Cell) = {
16:      val s = at(cell).split("""\\""").map(_.toInt)
17:      (s(0),s(1))
18:    }
19:    def block(cell: Cell, dij: Cell): Seq[Cell] =
20:      if (! isCell(cell) || ! isBlank(cell)) Seq.empty
21:      else cell +: block(move(cell, dij), dij)
22:    val blocks: Set[(Int,Seq[Cell])] = {
23:      val rowBlocks = 
24:        for (cell <- cells; if isHint(cell); (rsum,csum) = hint(cell); if rsum > 0)
25:        yield (rsum, block(move(cell, (1,0)), (1,0)))
26:      val colBlocks = 
27:        for (cell <- cells; if isHint(cell); (rsum,csum) = hint(cell); if csum > 0)
28:        yield (csum, block(move(cell, (0,1)), (0,1)))
29:      rowBlocks.toSet ++ colBlocks.toSet
30:    }
31:    def show(sol: Map[Cell,Int]) {
32:      for (i <- 0 until m) {
33:        for (j <- 0 until n; cell = (i,j)) {
34:          if (isBlank(cell)) print("   " + sol(cell) + "   ")
35:          else {
36:            val (rsum,csum) = hint(cell)
37:            print("[%2d\\%-2d]".format(rsum, csum))
38:          }
39:        }
40:        println
41:      }
42:    }
43:  }
44:  
45:  object Solver extends BoardPuzzleSolver[Kakuro] {
46:    val name = "kakuro.Solver"
47:  
48:    def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
49:      Kakuro(m, n, board)
50:  
51:    def define = {
52:      for (cell <- puzzle.cells; if puzzle.isBlank(cell))
53:        int('x(cell), 1, 9)
54:      for ((sum,block) <- puzzle.blocks) {
55:        val xs = block.map(cell => 'x(cell))
56:        add(Add(xs) === sum)
57:        add(Alldifferent(xs))
58:      }
59:    }
60:  
61:    def showSolution {
62:      val sol = {
63:        for (cell <- puzzle.cells; if puzzle.isBlank(cell))
64:        yield cell -> solution('x(cell))
65:      }.toMap
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:41:12 JST

Author: Naoyuki Tamura

Org version 7.8.02 with Emacs version 23

Validate XHTML 1.0