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