/* * Hashiwokakero Solver in Copris * by Naoyuki Tamura * http://bach.istc.kobe-u.ac.jp/copris/puzzles/hashiwokakero/ */ package hashiwokakero import jp.kobe_u.copris._ import jp.kobe_u.copris.dsl._ import puzzle._ case class Hashiwokakero(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle { import scala.math.Ordering.Implicits._ def isBlank(cell: Cell) = at(cell) == "-" def edge(cell: Cell, cell1: Cell) = if (cell < cell1) (cell,cell1) else (cell1,cell) def edgesFrom(cell: Cell) = { def findNumberCell(cell1: Cell, dij: Cell): Option[Cell] = if (! isCell(cell1)) None else if (isNumber(cell1)) Some(cell1) else findNumberCell(move(cell1, dij), dij) for (dij <- dijs; cell1 <- findNumberCell(move(cell, dij), dij)) yield edge(cell, cell1) } val edges = numberCells.flatMap(cell => edgesFrom(cell)).toSet def cross(edge1: (Cell,Cell), edge2: (Cell,Cell)) = { val ((i1,j1),(i2,j2)) = edge1; val ((i3,j3),(i4,j4)) = edge2 (i1 == i2 && i3 < i1 && i1 < i4 && j3 == j4 && j1 < j3 && j3 < j2) || (j1 == j2 && j3 < j1 && j1 < j4 && i3 == i4 && i1 < i3 && i3 < i2) } def show(sol: Map[(Cell,Cell),Int]) { val v = (for { (cell1,cell2) <- sol.keySet; if cell1._2 == cell2._2 d = sol((cell1,cell2)); if d > 0 cell <- (cell1._1+1 until cell2._1).map(i => (i,cell1._2)) } yield cell -> d).toMap val h = (for { (cell1,cell2) <- sol.keySet; if cell1._1 == cell2._1 d = sol((cell1,cell2)); if d > 0 cell <- (cell1._2+1 until cell2._2).map(j => (cell1._1,j)) } yield cell -> d).toMap for (i <- 0 until m) { for (j <- 0 until n) { val cell = (i,j) if (isNumber(cell)) print(" " + at(cell) + " ") else if (v.getOrElse(cell, 0) == 1) print(" | ") else if (v.getOrElse(cell, 0) == 2) print(" # ") else if (h.getOrElse(cell, 0) == 1) print("---") else if (h.getOrElse(cell, 0) == 2) print("===") else print(" . ") } println } } } object Solver extends BoardPuzzleSolver[Hashiwokakero] { import scala.math.Ordering.Implicits._ val name = "hashiwokakero.Solver" var bridgeComponents: Set[Set[Cell]] = _ def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) = Hashiwokakero(m, n, board) def define = { for (edge <- puzzle.edges) int('e(edge), 0, 2) for (cell <- puzzle.numberCells) add(Add(puzzle.edgesFrom(cell).map('e(_))) === puzzle.num(cell)) for (edge1 <- puzzle.edges; edge2 <- puzzle.edges if edge1 < edge2 && puzzle.cross(edge1, edge2)) add(('e(edge1) === 0) || ('e(edge2) === 0)) } def checkSolution: Boolean = { val nodes = puzzle.numberCells.toSet val edges = puzzle.edges.filter(edge => solution('e(edge)) > 0) def connectedCells(cell: Cell) = nodes.filter(cell1 => edges.contains(puzzle.edge(cell, cell1))) val arcs = nodes.map(cell => cell -> connectedCells(cell)).toMap bridgeComponents = getComponents(nodes, arcs) if (verbose >= 2) println("Components = " + bridgeComponents.size) bridgeComponents.size == 1 } def addNegation { for (component <- bridgeComponents) { val es = for { cell <- component; edge <- puzzle.edgesFrom(cell) if component.contains(edge._1) && component.contains(edge._2) e = solution('e(edge)); if e > 0 } yield 'e(edge) =/= e add(Or(es)) } } override def findFirstSolution = findIncremental(true, checkSolution, addNegation) override def findNextSolution = findIncremental(false, checkSolution, addNegation) def showSolution { require(bridgeComponents.size == 1) val component = bridgeComponents.head val sol = (for { cell <- component; edge <- puzzle.edgesFrom(cell) if component.contains(edge._1) && component.contains(edge._2) e = solution('e(edge)); if e > 0 } yield edge -> e).toMap if (quiet == 0) { println("Solution = " + sol) println("Size = " + sol.size) puzzle.show(sol) } } }