Scala program showing Knight’s Tour iterative algorithm using ASCII chars for demonstration
Main.scala

package net.theflyingkeyboard.knightour

// ? 2020 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
object Main extends App {
  val size = 8
  var initialBoard: List[List[Char]] = List.tabulate(size, size)((_, _) => Board.EMPTY)
  initialBoard = initialBoard.updated(0, initialBoard.head.updated(0, Board.KNIGHT))

  var knightPosition = BoardPoint(0, 0)
  var board = Board(initialBoard, knightPosition)
  var possibleMoves = board.possibleMoves(knightPosition)

  println(board)
  println()

  while (possibleMoves.length > 0) {
    val sortedMoves = possibleMoves.map(move => (move, board.possibleMoves(move)))
      .sortBy(moveMoves => moveMoves._2.length)

    knightPosition = sortedMoves(0)._1
    board = board.placeKnight(knightPosition)
    possibleMoves = board.possibleMoves(knightPosition)

    println(board)
    println()
  }
}

BoardPoint.scala

package net.theflyingkeyboard.knightour

// ? 2020 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
case class BoardPoint(x: Int, y: Int)

Board.scala

package net.theflyingkeyboard.knightour

// ? 2020 TheFlyingKeyboard and released under MIT License
// theflyingkeyboard.net
class Board(board: List[List[Char]], knightPosition: BoardPoint) {
  def possibleMoves(nextPosition: BoardPoint): Array[BoardPoint] = {
    Board.KNIGHT_MOVES.map(bP => BoardPoint(bP.x + nextPosition.x, bP.y + nextPosition.y))
      .filter(bP => bP.x < board.head.length && bP.x >= 0)
      .filter(bP => bP.y < board.length && bP.y >= 0)
      .filter(bP => board(bP.y)(bP.x) == Board.EMPTY)
  }

  def placeKnight(position: BoardPoint): Board = {
    def updateBoard(boardToUpdate: List[List[Char]], point: BoardPoint, value: Char): List[List[Char]] = {
      boardToUpdate.updated(point.y, boardToUpdate(point.y).updated(point.x, value))
    }

    val replacedKnight = updateBoard(board, knightPosition, Board.VISITED)
    val newKnightPlaced = updateBoard(replacedKnight, position, Board.KNIGHT)

    Board(newKnightPlaced, position)
  }

  override def toString: String = {
    board.map(row => row.mkString(""))
    .mkString("\n")
  }
}

object Board {
  val EMPTY = '.'
  val VISITED = 'X'
  val KNIGHT = 'K'

  private val KNIGHT_MOVES: Array[BoardPoint] = Array(BoardPoint(2, 1), BoardPoint(1, 2), BoardPoint(-1, 2),
    BoardPoint(-2, 1), BoardPoint(-2, -1), BoardPoint(-1, -2), BoardPoint(1, -2), BoardPoint(2, -1))

  def apply(board: List[List[Char]], knightPosition: BoardPoint): Board = new Board(board, knightPosition)
}

 



Scala Knight’s Tour
Tagged on:             

Leave a Reply

Your email address will not be published. Required fields are marked *

By continuing to use the site, you agree to the use of cookies. You can read more about it the Cookies&Privacy Policy Section Above. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this. You can read more about it the Cookies&Privacy Policy Section.

Close