Skip to content

Instantly share code, notes, and snippets.

@phderome phderome/Queens
Last active Feb 27, 2018

Embed
What would you like to do?
Solving Queens using Refined intervals
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))
}
}
@phderome

This comment has been minimized.

Copy link
Owner Author

commented Feb 17, 2018

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).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.