Solving Queens using Refined intervals

Queens

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

  type ChessInterval = Interval.Closed[W.`1`.T, W.`8`.T]
  type Column = Int Refined ChessInterval
  // intentionally 1-based to "fit" language of chess better than 0-7 and also to get a feel for working with Refined intervals.
  type Row = Column
  val maxRow: Row = 8

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

  type Positions = Vector[Position]
  final case class Board(layout: Positions) {
    // chess convention has white at bottom and lower row (1 not 0) at bottom and higher row (8 not 7) at top
    override def toString: String = " " + "_"*16 + "\n" + layout.sortBy(-_.r).mkString("\n") + "\n  A B C D E F G H"
  }

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

  def conflict(p1: Position, p2: Position): Boolean =
    p1.r === p2.r || p1.c === p2.c ||
      (p1.r.value + p2.c.value === p2.r.value + p1.c.value) ||
      (p1.r.value + p1.c.value === p2.r.value + p2.c.value)

  def eligible(positions: Positions, next: Position): Boolean =
    !positions.exists(x => conflict(x, next))

  @SuppressWarnings(Array("org.wartremover.warts.Recursion"))
  def backward(positions: Positions): Option[Positions] = {
    positions match {
      case IndexedSeq() => None
      case prevPositions :+ last =>
        val nextRow = (last.r.value + 1 to maxRow.value).find(r =>
          eligible(prevPositions, last.copy(r = castToRowOrColumn(r))))
        // backtrack more if we still fail, otherwise generate new solution optimistically.
        nextRow.fold(backward(prevPositions))(r =>
          forward(prevPositions, Position(castToRowOrColumn(r), last.c)))
    }
  }

  @tailrec
  def forward(positions: Positions, next: Position): Option[Positions] = {
    val isGoodMove = eligible(positions, next)
    if (positions.length + 1 === maxRow.value && isGoodMove)
      Some(positions :+ next)
    else {
      if (isGoodMove)
        forward(positions :+ next,
                next.copy(r = 1, c = castToRowOrColumn(next.c + 1)))
      else if (next.r === maxRow) backward(positions)
      else forward(positions, next.copy(r = castToRowOrColumn(next.r + 1)))
    }
  }

  forward(Vector.empty[Position], Position.A1) match {
    case None           => println(s"no solution found for ${maxRow.value} queens")
    case Some(solution) => println(Board(solution))
  }
}

Feb 17 18:27 EST, minor edits after the original was shown on Refined gitter.

Basically my question to refined experts would be to look at conflict method, lines 37-40. I am uneasy with it because it mixes Int types (for arithmetic) and refined types. The whole gist would like to work with ranges as relevant to a matrix and do simple arithmetic or comparison on values in those ranges.

Line 50 is also problematic: we come out of Refined range in order to use stdlib find on a stdlib range.

I also have four calls to castToRowOrColumn which use Refined.unsafeApply because I need to apply +1 and for that I need to go to Int. Ideally, I should be able to express increment from range[1, N] onto type range[1, N+1] or decrement from range [N+1, M] to range [N, M] as this is provable mathematically (I guess), but to be fair I don't provide enough context at lines 60-68 for that inference to be obvious. Lines 50-54 would be more hopeful, but here we lack a find method for a refined range (or do we?).

I am wondering if I am very much underusing Refined or this type of numeric usage as shown in this gist much more natural outside of Refined library (and reserve refined usage for whatever other normal applications there may be such as validation).