/*
 * Slitherlink Solver in Copris
 * by Naoyuki Tamura
 * http://bach.istc.kobe-u.ac.jp/copris/puzzles/slitherlink/
 */
package slitherlink

import jp.kobe_u.copris._
import jp.kobe_u.copris.dsl._
import puzzle._

case class Slitherlink(m: Int, n: Int, board: Seq[Seq[String]]) extends BoardPuzzle {
  def isBlank(cell: Cell) = at(cell) == "-"
  def edges(cell: Cell): Seq[(Grid,Grid)] = {
    val (i,j) = cell
    val es = Seq(((i,j),(i,j+1)), ((i,j),(i+1,j)), ((i,j+1),(i+1,j+1)), ((i+1,j),(i+1,j+1)))
    es.flatMap(e => Seq(e,e.swap))
  }
  def show(sol: Seq[Grid]) {
    val arcs = sol.sliding(2).map(e => (e(0),e(1))).toSet
    def connected(grid1: Grid, grid2: Grid) =
      arcs.contains((grid1,grid2)) || arcs.contains((grid2,grid1))
    for (i <- 0 to m) {
      for (j <- 0 to n) {
	print("+")
	if (j+1 <= n && connected((i,j), (i,j+1))) print("-")
	else print(" ")
      }
      println
      if (i < m) {
	for (j <- 0 to n) {
	  if (connected((i,j), (i+1,j))) print("|")
	  else print(" ")
	  if (j < n) {
	    if (isNumber((i,j))) print(at((i,j))) else print(" ")
	  }
	}
	println
      }
    }
  }
}

object Solver extends BoardPuzzleSolver[Slitherlink] {
  import scala.math.Ordering.Implicits._

  val name = "slitherlink.Solver"
  var cycles: Set[Seq[Grid]] = _

  def puzzleFactory(m: Int, n: Int, board: Seq[Seq[String]]) =
    Slitherlink(m, n, board)

  def define = {
    for (grid <- puzzle.grids; grid1 <- puzzle.adjGrids(grid))
      int('e(grid,grid1), 0, 1)
    for (grid <- puzzle.grids; grid1 <- puzzle.adjGrids(grid); if grid < grid1)
      add('e(grid,grid1) + 'e(grid1,grid) <= 1)
    for (grid <- puzzle.grids) {
      val in = puzzle.adjGrids(grid).map(grid1 => 'e(grid1,grid))
      val ot = puzzle.adjGrids(grid).map(grid1 => 'e(grid,grid1))
      int('io(grid), 0, 1)
      add('io(grid) === Add(in))
      add('io(grid) === Add(ot))
    }
    for (cell <- puzzle.cells; if puzzle.isNumber(cell)) {
      val x = puzzle.num(cell)
      add(Add(puzzle.edges(cell).map(edge => 'e(edge._1,edge._2))) === x)
    }
  }

  def checkSolution: Boolean = {
    val nodes = puzzle.grids.filter(grid => solution('io(grid)) > 0).toSet
    def nextGrids(grid: Grid) =
      puzzle.adjGrids(grid).filter(grid1 => solution('e(grid,grid1)) > 0).toSet
    val arcs = nodes.map(grid => grid -> nextGrids(grid)).toMap
    cycles = getCycles(nodes, arcs)
    def goodCycle(cycle: Seq[Grid]) = {
      val cycleArcs = cycle.sliding(2).map(e => (e(0),e(1))).toSet
      puzzle.numberCells.forall(cell => {
	val es = for (e <- puzzle.edges(cell))
		 yield if (cycleArcs.contains(e)) 1 else 0
	es.sum == puzzle.num(cell)
      })
    }
    if (verbose >= 2)
      println("Components = " + cycles.size)
    cycles.find(cycle => goodCycle(cycle)) match {
      case None =>
	false
      case Some(cycle) => {
	cycles = Set(cycle); true
      }
    }
  }
  def addNegation {
    for (cycle <- cycles) {
      add(Or(cycle.sliding(2).map(e => 'e(e(0),e(1)) === 0).toSeq))
      add(Or(cycle.reverse.sliding(2).map(e => 'e(e(0),e(1)) === 0).toSeq))
    }
  }
  override def findFirstSolution = findIncremental(true, checkSolution, addNegation)
  override def findNextSolution = findIncremental(false, checkSolution, addNegation)

  def showSolution {
    // Cycle
    require(cycles.size == 1)
    val sol = cycles.head
    if (quiet == 0) {
      println("Solution = " + sol)
      println("Size = " + sol.size)
      puzzle.show(sol)
    }
  }
}