How to resolve the algorithm Knight's tour step by step in the R programming language

Published on 12 May 2024 09:40 PM
#R

How to resolve the algorithm Knight's tour step by step in the R programming language

Table of Contents

Problem Statement

Problem: you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once. Note that it is not a requirement that the tour be "closed"; that is, the knight need not end within a single move of its start position. Input and output may be textual or graphical, according to the conventions of the programming environment. If textual, squares should be indicated in algebraic notation. The output should indicate the order in which the knight visits the squares, starting with the initial position. The form of the output may be a diagram of the board with the squares numbered according to visitation sequence, or a textual list of algebraic coordinates in order, or even an actual animation of the knight moving around the chessboard. Input: starting square Output: move sequence

Let's start with the solution:

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

Source code in the r programming language

#!/usr/bin/Rscript
 
# M x N Chess Board.
M = 8; N = 8; board = matrix(0, nrow = M, ncol = N)
 
# Get/Set value on a board position.
getboard = function (position)    { board[position[1], position[2]] }
setboard = function (position, x) { board[position[1], position[2]] <<- x }
 
# (Relative) Hops of a Knight.
hops = cbind(c(-2, -1), c(-1, -2), c(+1, -2), c(+2, -1),
             c(+2, +1), c(+1, +2), c(-1, +2), c(-2, +1))
 
# Validate a move.
valid = function (move) {
    all(1 <= move & move <= c(M, N)) && (getboard(move) == 0)
}
 
# Moves possible from a given position.
explore = function (position) {
    moves = position + hops
    cbind(moves[, apply(moves, 2, valid)])
}
 
# Possible moves sorted according to their Wornsdorff cost.
candidates = function (position) {
    moves = explore(position)
 
    # No candidate moves available.
    if (ncol(moves) == 0) { return(moves) }
 
    wcosts = apply(moves, 2, function (position) { ncol(explore(position)) })
    cbind(moves[, order(wcosts)])
}
 
# Recursive function for touring the chess board.
knightTour = function (position, moveN) {
 
    # Tour Complete.
    if (moveN > (M * N)) {
        print(board)
        quit()
    }
 
    # Available moves.
    moves = candidates(position) 
 
    # None possible. Backtrack.
    if (ncol(moves) == 0) { return() }
 
    # Make a move, and continue the tour.
    apply(moves, 2, function (position) {
                        setboard(position, moveN)
                        knightTour(position, moveN + 1)
                        setboard(position, 0)
                    })
}
 
# User Input: Starting position (in algebraic notation).
square = commandArgs(trailingOnly = TRUE)
 
# Convert into board co-ordinates.
row      = M + 1 - as.integer(substr(square, 2, 2))
ascii    = function (ch) { as.integer(charToRaw(ch)) }
col      = 1 + ascii(substr(square, 1, 1)) - ascii('a')
position = c(row, col)
 
# Begin tour.
setboard(position, 1); knightTour(position, 2)

You may also check:How to resolve the algorithm EKG sequence convergence step by step in the J programming language
You may also check:How to resolve the algorithm Parsing/RPN calculator algorithm step by step in the F# programming language
You may also check:How to resolve the algorithm Sum of elements below main diagonal of matrix step by step in the Phix programming language
You may also check:How to resolve the algorithm Execute a system command step by step in the BQN programming language
You may also check:How to resolve the algorithm Multi-dimensional array step by step in the Java programming language