/* * Kurodoko Solver in Copris * by Naoyuki Tamura * http://bach.istc.kobe-u.ac.jp/copris/puzzles/kurodoko/ */ package kurodoko import jp.kobe_u.copris._ import jp.kobe_u.copris.dsl._ import puzzle._ case class Kurodoko(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle { def show(sol: Seq[Seq[Int]]) { for (i <- 0 until m) { for (j <- 0 until n) { val cell = (i,j) if (isNumber(cell)) print("%3d".format(num(cell))) else if (sol(i)(j) == 0) print(" ..") else print(" ##") } println } } } object Solver extends BoardPuzzleSolver[Kurodoko] { import scala.math.Ordering.Implicits._ val name = "kurodoko.Solver" var whiteComponents: Set[Set[Cell]] = _ def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) = Kurodoko(m, n, board) def define = { for (cell <- puzzle.cells) { // 'x(cell): = 0 white, = 1 black if (puzzle.isNumber(cell)) int('x(cell), 0) else int('x(cell), 0, 1) for (dij <- puzzle.dijs) { // 'c(cell, dij); the number of white cells from cell to dij int('c(cell,dij), 0, math.max(puzzle.m, puzzle.n)) } } for (cell <- puzzle.cells; cell1 <- puzzle.adjCells(cell); if cell < cell1) add(('x(cell) === 0) || ('x(cell1) === 0)) for (cell <- puzzle.cells; dij <- puzzle.dijs) { add(('x(cell) > 0) ==> ('c(cell,dij) === 0)) val cell1 = puzzle.move(cell, dij) if (puzzle.isCell(cell1)) add(('x(cell) === 0) ==> ('c(cell,dij) === 'c(cell1,dij) + 1)) else add(('x(cell) === 0) ==> ('c(cell,dij) === 1)) } for (cell <- puzzle.cells; if puzzle.isNumber(cell)) { val s = for (dij <- puzzle.dijs) yield 'c(cell,dij) add(Add(s) - 3 === puzzle.num(cell)) } } def checkSolution: Boolean = { val nodes = puzzle.cells.filter(cell => solution('x(cell)) == 0).toSet def nextCells(cell: Cell) = puzzle.adjCells(cell).filter(cell1 => solution('x(cell1)) == 0).toSet val arcs = nodes.map(cell => cell -> nextCells(cell)).toMap whiteComponents = getComponents(nodes, arcs) if (verbose >= 2) println("Components = " + whiteComponents.size) whiteComponents.size == 1 } def addNegation { for (whites <- whiteComponents) { val blacks = for (cell <- whites; cell1 <- puzzle.adjCells(cell); if solution('x(cell1)) > 0) yield cell1 add(Or(blacks.map(cell => 'x(cell) === 0))) } } override def findFirstSolution = findIncremental(true, checkSolution, addNegation) override def findNextSolution = findIncremental(false, checkSolution, addNegation) def showSolution { val sol = for (i <- 0 until puzzle.m) yield (0 until puzzle.n).map(j => solution('x((i,j)))) if (quiet == 0) { println("Solution = " + sol) println("Size = " + sol.size) puzzle.show(sol) } } }