Skip to content

Instantly share code, notes, and snippets.

@phderome
Last active February 27, 2018 01:25
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save phderome/b43c56c4ac8e5ce2feecef6d97ea3803 to your computer and use it in GitHub Desktop.
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
Copy link
Author

phderome 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