Step by Step solution about How to resolve the algorithm Knight's tour step by step in the Kotlin programming language

Kotlin Code Explanation

Objective: This code demonstrates how to solve the Knight's Tour problem, which involves finding a path for a knight on a chessboard to visit each square exactly once.

Data Structure:

• Square data class: Represents a square on the board with its x and y coordinates.
• board array: A 2D array of Square objects representing the chessboard.

Knight's Moves:

• axisMoves array: Stores the possible moves for the knight in terms of changes in x and y coordinates.
• knightMoves function: Calculates the possible moves for a knight at a given square, excluding invalid moves.

Knight's Tour:

• allPairs function: Generates all possible pairs of elements from an input array.
• knightTour function: Iteratively explores possible moves for the knight and selects the next move with the fewest remaining moves. It continues until all squares are visited.
• knightTourFrom function: Initializes the knight's tour with a starting square.

Main Function:

• In the main function:
  • Generates a knight's tour starting from square (1, 1).
  • Prints the path of the knight's tour, formatting it in an 8x8 grid.

data class Square(val x : Int, val y : Int)

val board = Array(8 * 8, { Square(it / 8 + 1, it % 8 + 1) })
val axisMoves = arrayOf(1, 2, -1, -2)

fun <T> allPairs(a: Array<T>) = a.flatMap { i -> a.map { j -> Pair(i, j) } }

fun knightMoves(s : Square) : List<Square> {
    val moves = allPairs(axisMoves).filter{ Math.abs(it.first) != Math.abs(it.second) }
    fun onBoard(s : Square) = board.any {it == s}
    return moves.map { Square(s.x + it.first, s.y + it.second) }.filter(::onBoard)
}

fun knightTour(moves : List<Square>) : List<Square> {
    fun findMoves(s: Square) = knightMoves(s).filterNot { m -> moves.any { it == m } }
    val newSquare = findMoves(moves.last()).minBy { findMoves(it).size }
    return if (newSquare == null) moves else knightTour(moves + newSquare)
}

fun knightTourFrom(start : Square) = knightTour(listOf(start))

fun main(args : Array<String>) {
    var col = 0
    for ((x, y) in knightTourFrom(Square(1, 1))) {
        System.out.print("$x,$y")
        System.out.print(if (col == 7) "\n" else " ")
        col = (col + 1) % 8
    }
}