#### A knight’s quest

LYAHFGG:

Here’s a problem that really lends itself to being solved with non-determinism. Say you have a chess board and only one knight piece on it. We want to find out if the knight can reach a certain position in three moves.

Instead of type aliasing a pair, let’s make this into a case class again:

``````scala> case class KnightPos(c: Int, r: Int)
defined class KnightPos``````

Here’s the function to calculate all of the knight’s next positions:

``````scala> case class KnightPos(c: Int, r: Int) {
def move: List[KnightPos] =
for {
KnightPos(c2, r2) <- List(KnightPos(c + 2, r - 1), KnightPos(c + 2, r + 1),
KnightPos(c - 2, r - 1), KnightPos(c - 2, r + 1),
KnightPos(c + 1, r - 2), KnightPos(c + 1, r + 2),
KnightPos(c - 1, r - 2), KnightPos(c - 1, r + 2)) if (
((1 to 8).toList contains c2) && ((1 to 8).toList contains r2))
} yield KnightPos(c2, r2)
}
defined class KnightPos
scala> KnightPos(6, 2).move
res4: List[KnightPos] = List(KnightPos(8,1), KnightPos(8,3), KnightPos(4,1), KnightPos(4,3), KnightPos(7,4), KnightPos(5,4))
scala> KnightPos(8, 1).move
res5: List[KnightPos] = List(KnightPos(6,2), KnightPos(7,3))``````

The answers look good. Now we implement chaining this three times:

``````scala> case class KnightPos(c: Int, r: Int) {
def move: List[KnightPos] =
for {
KnightPos(c2, r2) <- List(KnightPos(c + 2, r - 1), KnightPos(c + 2, r + 1),
KnightPos(c - 2, r - 1), KnightPos(c - 2, r + 1),
KnightPos(c + 1, r - 2), KnightPos(c + 1, r + 2),
KnightPos(c - 1, r - 2), KnightPos(c - 1, r + 2)) if (
((1 to 8).toList contains c2) && ((1 to 8).toList contains r2))
} yield KnightPos(c2, r2)
def in3: List[KnightPos] =
for {
first <- move
second <- first.move
third <- second.move
} yield third
def canReachIn3(end: KnightPos): Boolean = in3 contains end
}
defined class KnightPos
scala> KnightPos(6, 2) canReachIn3 KnightPos(6, 1)
res6: Boolean = true
scala> KnightPos(6, 2) canReachIn3 KnightPos(7, 3)
res7: Boolean = false``````

As it turns out, from `(6, 2)` you can reach `(6, 1)` in three moves, but not `(7, 3)`. As with Pierre’s bird example, one of key aspect of the monadic calculation is that the effect of one move can be passed on to the next.

We’ll pick up from here.