NonogramSolver

package org.roach.nonogramsolver

import scala.io.Source
import org.apache.logging.log4j.Logger
import org.apache.logging.log4j.LogManager

object NonogramSolver {
  val logger = LogManager.getLogger

  def main(args: Array[String]): Unit = {
    val (size, rows, cols) = {
      val lines = Source.fromFile(args(0)).getLines().filter(l => !l.startsWith("#") && l.length != 0).toList
      val size = lines(0).toInt
      lines(1) // throw away second line of input because we don't need to know the number of columns
      val rows = lines(2).replace("\",\"", ":").replace("\"","").split(":").map(r => Requirement(r.split(",").map(l => l.toInt).toList)).toList
      val cols = lines(3).replace("\",\"", ":").replace("\"","").split(":").map(c => Requirement(c.split(",").map(l => l.toInt).toList)).toList
      (size, rows, cols)
    }

    val filterGrid = Grid(for (col <- cols) yield col.generateFilter(size)).inverse

    // Generate list of all possible potential rows
    logger.debug("Generating potential rows...")
    val potentialRowList = for ((row, filter) <- rows zip filterGrid.contents) yield row.generateRows(size).filter(r => (r compatibleWith filter) && !r.isErrorRow)

    // Generate list of all possible potential columns
    logger.debug("Generating potential columns...")
    val potentialColList = for (col <- cols) yield col.generateRows(size).filter(c => !c.isErrorRow)

    val orderToTryRows: List[Int] = (0 to size - 1).toList

    /*
     * The main engine that solves the given puzzle
     * Substitutes one row into the startGrid and then recursively calls itself
     * with the new startGrid and tries the next row.
     * @param startGrid The solution so far, which starts as all empty cells
     * @param rowList A list of integer lists for each row
     * @param cd The column difference so far.
     * @param rowsToTryNext A list of rows to try for this iteration
     * @param filter The current filter grid
     * @return Some(Grid) which is the solution of the puzzle, or None
     */
    var done = false;
    def solve(
      startGrid: Grid,
      rowList: List[Requirement],
      cd: Int,
      rowsToTryNext: List[Int],
      filter: Grid): Option[Grid] = {
      if (filter.hasErrors) return None
      if (rowsToTryNext != Nil) {
        logger.trace("In solve with " + rowsToTryNext.head)
      }
      rowList match {
        case Nil => Some(startGrid) // If we got this far, then we've solved the puzzle
        case row :: tail =>
          val whichRow = rowsToTryNext.head
          val rowsToTry = potentialRowList(whichRow).filter(r => r compatibleWith filter(whichRow))
          if (rowsToTry == Nil) {
            logger.debug("Stopping because none of " + potentialRowList(whichRow) + " matched " + filter(whichRow) + " for row " + whichRow)
          }
          rowsToTry.foreach { r =>
            // Builds a new grid with r substituted for row #whichRow
            val newGrid = startGrid.updated(whichRow, r)
            val newColumnDiff = newGrid.columnDiff(cols)
            if (cd - newColumnDiff == r.countOs) { // Only try rows where every O counts
              val tGrid = newGrid.inverse
              val allColumnsPossible = (potentialColList, tGrid.contents).zipped.forall(
                (p, filter) => p exists (_ compatibleWith filter))
              val newFilter = (newGrid & filter).applyRules(cols)
              // Only try rows where all columns are possible
              if (allColumnsPossible) {
                val solveTail = solve(newGrid, tail, newColumnDiff, rowsToTryNext.tail, newFilter)
                if (solveTail != None) {
                  return solveTail
                }
              }
            }
          }
          // Only reach here if all tries are exhausted and didn't work
          logger.trace("\nFinal filter:\n" + filter)
          None
      }
    }

    solve(Grid.emptyGrid(size), rows, Grid.emptyGrid(size).columnDiff(cols), orderToTryRows, filterGrid) match {
      case Some(solution) =>
        println(solution)
      case None =>
        println("\n\nRows: " + rows)
        println("Cols: " + cols)
        println("After an exhaustive search I couldn't solve it. :-(")
    }
  }
}