Knight Tour with trampoline (in response to other gist that uses mutual recursion)

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 KnightTourSolver extends App {
  @SuppressWarnings(Array("org.wartremover.warts.Equals"))
  implicit final class AnyOps[A](self: A) {
    def ===(other: A): Boolean = self == other
    def =!=(other: A): Boolean = !(===(other))
  }

  type ChessInterval = Interval.Closed[W.`1`.T, W.`8`.T]
  type Column = Int Refined ChessInterval
  type Row = Column
  val maxRow: Row = 8
  val maxCol: Column = maxRow
  val minCol: Column = 1
  val dimension: Int = maxRow.value
  val piecesToPlay: Int = (dimension) * (dimension)

  final case class Position(r: Row, c: Column) {
    override def toString: String =
      s"(${r.value},${r.value})"
  }
  object Position {
    def A1: Position = Position(1, 1)
  }
  type Positions = Vector[Position]

  sealed trait Explore
  final case class Done(solution: Option[Positions]) extends Explore
  final case class Forward(positions: Positions, newEntry: Position)
    extends Explore
  final case class Backward(positions: Positions, failed: Position)
    extends Explore

  final case class Board(layout: Positions) { // its concern is to render itself as a String for 2 dimensional display (toString)
    // because formatting is tedious and full of gotchas,
    val emptyCell = "|__"
    val horizontalLine = " " + "_" * (3 * dimension)
    val bottomLine = "|\n" + horizontalLine + "\n" + ('A' until ('A' + maxCol.value).toChar).mkString("  ", "  ", "")
    override def toString: String = {
      val matrix =  Array.ofDim[String](dimension, dimension)
      for {
        i <- 0 until dimension
        j <- 0 until dimension
      } {
        matrix(i)(j) = emptyCell
        layout.zip(Stream from 1).foreach { case(p, value) =>
          matrix(p.r.value -1)(p.c.value -1) = s"|${(if (value < 10) " " else "") + value.toString }"
        }
      }
      // chess convention has white at bottom and lower row (1 not 0) at bottom and higher row (8 not 8) at top
      matrix.reverse.zipWithIndex.foldLeft(horizontalLine) { case(acc, (row, idx)) =>
        acc + "\n" + (idx+1).toString + row.mkString("") + (if (idx === dimension -1) "" else "|")
      } + bottomLine
    }

  }

  @tailrec
  def run(explore: Explore): Option[Positions] = explore match {
    case Done(positions) => positions
    case Forward(positions, newEntry) =>
      if (positions.length + 1 === piecesToPlay)
        run(Done(Some(positions :+ newEntry)))
      else // more search required
        selectNextForwardMove(positions, newEntry) match {
          case None      => run(Backward(positions, newEntry))
          case Some(pos) => run(Forward(positions :+ newEntry, pos))
        }
    case Backward(positions, failed) =>
      positions match {
        case IndexedSeq() => run(Done(None)) // search ends in failure
        case prevPositions :+ last =>
          val next = selectEligibleOnBacktrack(positions, failed)
            .find(pos => !positions.contains(pos))
          // backtrack more if we still fail, otherwise generate new solution optimistically.
          next match {
            case Some(pos) => run(Forward(positions, pos))
            case None      => run(Backward(prevPositions, last))
          }
      }
  }

  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) => (refineV(x): Either[String, Row]).isRight && (refineV(y): Either[String, Column]).isRight }
        .map {
          case (x, y) => Position(castToRowOrColumn(x), castToRowOrColumn(y))
        }
  }

  def selectNextForwardMove(positions: Positions,
                            success: Position): Option[Position] =
    getAllLegalMoves(success).find(pos => !positions.contains(pos))

  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 one as well right now
    }

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

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

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

}

Trying to find a non-imperative solution (meaning recursive) to Knight Tours. It takes about 2-3 minutes to run, so much slower than an imperative solution, but the trampoline allows to bypass the StackOverFlow error that comes up for dimension 8 (other gist).