Wolf sheep cabbage riddle solver in scala using backtracking

IslandState.scala

case class IslandState(destShore: ShoreSide, initialShore: ShoreSide) {

  override def toString: String = s"dest:$destShore,init:$initialShore"

  import IslandState._

  val isGameOver: Boolean = isFinalStateReached(destShore)

  def getTheOtherShore(ss: ShoreSide): ShoreSide = if (destShore == ss) initialShore else destShore

  def moveBoat(isAtLeftShore: Boolean, boat: Boat): IslandState = {
    def addBoatToShore(shoreSide: ShoreSide) = {
      //move boat to other shore. boat is ready for new animals and is empty
      shoreSide.copy(shoreSide.objects ++ boat.currentAnimalOnBoat + boat.copy(Seq()))
    }

   def removeBoatAndItsAnimalsFromShore(shoreSide: ShoreSide) = shoreSide.copy(
      shoreSide.objects.filterNot(boat.currentAnimalOnBoat.contains).collect {
        case ta: TransferableAnimal => ta
      }
    )

    if (isAtLeftShore) {
      this.copy(
        destShore = removeBoatAndItsAnimalsFromShore(destShore),
        initialShore = addBoatToShore(initialShore)
      )
    } else {
      this.copy(
        destShore = addBoatToShore(destShore),
        initialShore = removeBoatAndItsAnimalsFromShore(initialShore)
      )
    }
  }
}

case object IslandState {
  val desiredEndState: ShoreSide = ShoreSide(Set(Man, Sheep, Wolf, Cabbage, Boat(Seq())))
  val isFinalStateReached: ShoreSide => Boolean = _ == desiredEndState
  
  def isStateValid(states: Seq[IslandState], newState: IslandState): Boolean = {
    def isStateRepeating(states: Seq[IslandState], newState: IslandState): Boolean = (states :+ newState).toSet.size == states.size

    def isShoreOkay(shoreSide: ShoreSide): Boolean = shoreSide.objects match {
      case x if x.contains(Man) => true
      case objectsOnShore: Set[_] =>
        val isSomeoneGoingToBeEaten = objectsOnShore.toList.collect {
          case animal: TransferableAnimal => animal
        }.exists(_.afraidOf.exists(objectsOnShore.contains))
        !isSomeoneGoingToBeEaten
    }

    isShoreOkay(newState.destShore) && isShoreOkay(newState.initialShore) && !isStateRepeating(states, newState)
  }
}

ShoreSide.scala

case class ShoreSide(objects: Set[TransferableObject]) {

  import ShoreSide.getTransferableAnimals

  lazy val transferableAnimals: Set[TransferableAnimal] = getTransferableAnimals(objects)
}

object ShoreSide {
  def getTransferableAnimals(objects: Set[TransferableObject]): Set[TransferableAnimal] = objects.collect {
    case x: TransferableAnimal => x
  }
}

TransferableObjects.scala

sealed trait TransferableObject

sealed trait TransferableAnimal extends TransferableObject {
  def afraidOf: Option[TransferableAnimal]

  def eats: Seq[TransferableAnimal]
}

case class Boat(currentAnimalOnBoat: Seq[TransferableAnimal]) extends TransferableObject

case object Man extends TransferableAnimal {
  override def afraidOf: Option[TransferableAnimal] = None

  override def eats: Seq[TransferableAnimal] = Seq(Wolf, Sheep, Cabbage)
}

case object Wolf extends TransferableAnimal {
  override def afraidOf: Option[TransferableAnimal] = None

  override def eats: Seq[TransferableAnimal] = Seq(Sheep)
}

case object Sheep extends TransferableAnimal {
  override def afraidOf: Option[TransferableAnimal] = Some(Wolf)

  override def eats: Seq[TransferableAnimal] = Seq(Cabbage)
}

case object Cabbage extends TransferableAnimal {
  override def afraidOf: Option[TransferableAnimal] = Some(Sheep)

  override def eats: Seq[TransferableAnimal] = Seq.empty
}

WolfSheepCabbage.scala

object WolfSheepCabbage extends App {

  type Solution = Seq[IslandState]

  //riddle can be solved in more than 1 correct way. hence the Seq[Solution] here.
  def solveRiddle(initialState: IslandState): Seq[Solution] = {

    def helper(acc: Seq[IslandState], currentState: IslandState, isBoatAtLeftShore: Boolean): Seq[Solution] = {
      if (!isStateValid(acc, currentState)) {
        Seq[Solution]()
      } else {
        if (currentState.isGameOver) {
          Seq(acc :+ currentState)
        } else {
          val thisShore = if (isBoatAtLeftShore) currentState.destShore else currentState.initialShore

          val possibleAnimals = thisShore.transferableAnimals.toSeq.filter(_ != Man).map(Seq(Man, _)) ++ Seq(Seq(Man))

          val results = for (animalCombination <- possibleAnimals;
                             newState = currentState.moveBoat(isBoatAtLeftShore, Boat(animalCombination));
                             moves = helper(acc :+ currentState, newState, !isBoatAtLeftShore)
                             if moves.nonEmpty) yield moves
          results flatten
        }
      }
    }
    //we start at rightShore
    helper(Seq(), initialState, isBoatAtLeftShore = false)
  }

  val firstState = IslandState(ShoreSide(Set.empty), ShoreSide(Set(Wolf, Sheep, Cabbage, Man, Boat(Seq.empty))))
  println(s"as expected: initial state validity is : ${isStateValid(Seq(), firstState)}")

  private val possibleSolutions: Seq[Solution] = solveRiddle(firstState)
  possibleSolutions match {
    case Nil => println(s"could not solve riddle. oh no !")
    case list => println(list.map(lst => lst.mkString(System.lineSeparator()))
      .mkString(s"possible solutions: ${System.lineSeparator()}", s"${System.lineSeparator()} another solution is: ${System.lineSeparator()}", ""))
  }


}