Kakuro Solver in Copris

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.

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)

• 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)

scala -cp copris-puzzles-2.0.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-puzzles-2.0.jar kakuro.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 kakuro.Solver -o multi -s2 minisat input_file_name

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.

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

• It should be compiled with ../build/PuzzleSolver.scala.

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

• 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
• Kakuro (by Nikoli)
• Wikipedia:Kakuro
• http://www.janko.at/Raetsel/Kakuro/