7x7 chessboard Knight Tour

Knights.scala

package code

import eu.timepit.refined._
import eu.timepit.refined.api.Refined
import eu.timepit.refined.auto._
import eu.timepit.refined.numeric._

import scala.annotation.tailrec

object Utils1 {
  @SuppressWarnings(Array("org.wartremover.warts.Equals"))
  implicit final class AnyOps[A](self: A) {
    def ===(other: A): Boolean = self == other
    def =!=(other: A): Boolean = !(===(other))
  }
}

object KnightInMotion1 {
  import Utils1._
  import Knights._

  val maxRow: Row = 6
  val maxCol: Column = maxRow
  val piecesToPlay: Int = (maxRow.value+1) * (maxRow.value +1)

  def onBoard(x: Int, y: Int): Boolean =
    (0 to 6).contains(x) && (0 to 6).contains(y)

  def chooseValid(positions: Positions, candidates: Seq[Position]): Option[Position] =
    candidates.find(pos => !positions.contains(pos))

  @tailrec
  final def backward(positions: Positions, failed: Position): Option[Positions] = {
    positions match {
      case IndexedSeq() => None // search ends in failure
      case prevPositions :+ last =>
        val next = chooseValid(positions, selectEligibleOnBacktrack(positions, failed))
        // backtrack more if we still fail, otherwise generate new solution optimistically.
        next match {
          case Some(pos) => forward(positions, pos)
          case None => backward(prevPositions, last)
        }
    }
  }

  @tailrec
  final def forward(positions: Positions, newEntry: Position): Option[Positions] = {
    if (positions.length + 1 === piecesToPlay)
      Some(positions :+ newEntry)
    else  // more search required
      selectNextForwardMove(positions, newEntry) match {
        case None => backward(positions, newEntry)
        case Some(pos) => forward(positions :+ newEntry, pos)
      }
  }

  def getAllLegalMoves(from: Position): Seq[Position] = from match {
    case Position(row, col) =>
      val (r, c) = (row.value, col.value)
      Seq((r + 2, c - 1),
          (r + 1, c - 2),
          (r - 1, c - 2),
          (r - 2, c - 1),
          (r - 2, c + 1),
          (r - 1, c + 2),
          (r + 1, c + 2),
          (r + 2, c + 1))
        .filter { case (x, y) => onBoard(x, y) }
        .map {
          case (x, y) => Position(castToRowOrColumn(x), castToRowOrColumn(y))
        }
  }

  def selectNextForwardMove(positions: Positions,
                            success: Position): Option[Position] =
    chooseValid(positions, getAllLegalMoves(success))

  def selectEligibleOnBacktrack(positions: Positions,
                                failed: Position): Seq[Position] =
    positions match {
      case IndexedSeq() => Nil // search ends in failure
      case _ :+ previous =>
        getAllLegalMoves(previous)
          .dropWhile(p => p =!= failed) // removes those that would/should have been tried before
          .drop(1) // removes failed as well
    }
}

object Knights extends App {
  import Utils._

  type ChessInterval = Interval.Closed[W.`0`.T, W.`6`.T]
  type Column = Int Refined ChessInterval
  type Row = Column
  val maxRow: Row = 6
  val maxCol: Column = maxRow

  final case class Position(r: Row, c: Column) {
    override def toString: String =
      r.value.toString + "|_" * c + "|*" + "|_" * (maxRow.value - c) + "|"
  }
  object Position {
    def A1: Position = Position(0, 0)
  }

  type Positions = Vector[Position]
  final case class Board(layout: Positions) {
    def label(p: Position): String = {
      val lbl = layout.zipWithIndex
        .find { case (pos, i) => pos === p }
        .map(pair => (pair._2 + 1).toString)
        .getOrElse("**")
      if (lbl.lengthCompare(1) <= 0) s" $lbl" else lbl
    }
    // chess convention has white at bottom and lower row (1 not 0) at bottom and higher row (7 not 7) at top
    // override def toString: String = layout.map(p => s"(${p.r.value},${p.c.value})").mkString(":")
    override def toString: String = {
      val emptyCell = "|__"
      def emptySeries(c: Int): String = emptyCell*c
      def emptyRow: String = emptySeries(1 + maxRow.value)
      def emptyRowSeries(c: Int, initRow: Int): String = (initRow to initRow -c +1 by -1).map(r => s"${r}$emptyRow|\n").mkString("")
      val innerAndRow = layout
        .sortBy(p => -7 * p.r.value + p.c.value)
        .foldLeft(("7", 6: Int, 0: Int)) {
          case (s, pos) =>
            val posLabel = label(pos)
            val tmp = (pos.r.value, pos.c.value) match {
              case (row, y) if row === s._2 =>
                s._1 + emptySeries(pos.c.value - s._3 - 1) + "|" + posLabel
              case (row, y) =>
                val header = s._1 + (if(s._1 === "7")  emptySeries(maxRow.value - s._3 + 1) else emptySeries(maxRow.value - s._3))
                header + "|\n" + emptyRowSeries(s._2 -row -1, s._2) + (pos.r.value+1).toString + emptySeries(pos.c.value) + "|" + posLabel
            }
            (tmp, pos.r.value, pos.c.value)
        }
      if (layout.nonEmpty)
      " " + "_" * (3 * 7) + "\n" + innerAndRow._1 + emptySeries(maxRow.value - innerAndRow._3) + "|\n  A  B  C  D  E  F  G"  //  F  G  H"
      else
        " " + "_" * (3 * 7) + "\n" + emptyRowSeries(maxRow.value + 1, maxRow.value + 1) + "|\n  A  B  C  D  E  F  G" //  F  G  H"
    }
  }

  def castToRowOrColumn(x: Int): Refined[Int, ChessInterval] =
    Refined.unsafeApply[Int, ChessInterval](x)

  val solution: Option[Positions] = KnightInMotion1.forward(Vector.empty[Position], Position.A1)

  solution match {
    case None =>
      println(s"no solution found for dimension ${maxRow.value}")
    case Some(solution) =>
      println(s"Solution found for dimension ${maxRow.value}")
      println(Board(solution))
  }

}

Curiously, this gets a stack overflow when changing parameter from 7 to 8 and even at 7 when using debug mode, one can see enormous amount of stack frames active upon finding the solution.