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

Published on 7 June 2024 03:52 AM

How to resolve the algorithm Knight's tour step by step in the Haskell 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 Haskell programming language

This Haskell code implements a knight's tour algorithm, which finds a sequence of moves for a knight on a chessboard such that it visits every square exactly once.

Here's a detailed explanation of the code:

  1. Type Aliases and Imports:

    • Square is an alias for a tuple representing a square on the chessboard.
    • The code imports several functions from standard Haskell libraries, including Data.Bifunctor, Data.Char, Data.List, Data.Ord, and Control.Monad.
  2. knightTour Function:

    • This is the main function that implements the knight's tour algorithm.
    • It takes a list of squares (moves) representing the current tour and returns a new list of squares representing the complete tour.
    • The algorithm proceeds by choosing the next square to visit (newSquare) based on the following criteria:
      • The square with the fewest possible moves (as determined by the findMoves function).
      • The square is not already in the tour (moves).
      • The square is on the board (checked by the onBoard function).
    • If there are no valid squares to visit (i.e., possibilities is empty), the algorithm returns the reverse of the current tour.
    • Otherwise, it adds newSquare to the beginning of the tour and recursively calls knightTour to find the next move.
  3. findMoves Function:

    • Given a square ((x, y)), this function returns a list of possible moves for the knight.
    • It uses the knightOptions function to generate all possible moves and then filters out the moves that are not on the board (\\ moves).
  4. knightOptions Function:

    • Given a square ((x, y)), this function generates a list of all possible moves for the knight.
    • It uses a list comprehension to generate all combinations of the possible deltas in the x and y directions (knightMoves).
    • For each combination, it applies the go function to filter out invalid moves (those that would move the knight off the board).
  5. go Function:

    • This function is used to filter out invalid moves from the list of possible moves generated by knightOptions.
    • It checks if the move (move) is on the board using the onBoard function.
    • If the move is valid, it returns a singleton list containing the move. Otherwise, it returns an empty list.
  6. knightMoves:

    • This is a list of all possible deltas in the x and y directions for the knight's moves.
    • The list is used in the knightOptions function to generate all possible knight moves.
  7. onBoard Function:

    • This function checks if a given integer n is between 0 and 9 (inclusive), effectively determining if it is a valid position on the chessboard.
  8. both Function:

    • This function is used to combine two functions that take the same argument and return values of the same type.
    • It applies both functions to the argument and returns a tuple containing the results.
  9. Test Code:

    • startPoint is an example starting point for the knight's tour algorithm.
    • algebraic converts a square tuple to its algebraic notation (e.g., "e5").
    • main executes the knight's tour algorithm and prints the results in algebraic notation.

In summary, this code provides an implementation of the knight's tour algorithm, which finds a complete tour for a knight on a chessboard such that it visits every square exactly once.

Source code in the haskell programming language

import Data.Bifunctor (bimap)
import Data.Char (chr, ord)
import Data.List (intercalate, minimumBy, sort, (\\))
import Data.Ord (comparing)
import Control.Monad (join)

---------------------- KNIGHT'S TOUR ---------------------

type Square = (Int, Int)

knightTour :: [Square] -> [Square]
knightTour moves
  | null possibilities = reverse moves
  | otherwise = knightTour $ newSquare : moves
  where
    newSquare =
      minimumBy
        (comparing (length . findMoves))
        possibilities
    possibilities = findMoves $ head moves
    findMoves = (\\ moves) . knightOptions

knightOptions :: Square -> [Square]
knightOptions (x, y) =
  knightMoves >>= go . bimap (+ x) (+ y)
  where
    go move
      | uncurry (&&) (both onBoard move) = [move]
      | otherwise = []

knightMoves :: [(Int, Int)]
knightMoves =
  ((>>=) <*> (\deltas n -> deltas >>= go n)) [1, 2, -1, -2]
  where
    go i x
      | abs i /= abs x = [(i, x)]
      | otherwise = []

onBoard :: Int -> Bool
onBoard = (&&) . (0 <) <*> (9 >)

both :: (a -> b) -> (a,  a) -> (b,  b)
both = join bimap

--------------------------- TEST -------------------------
startPoint :: String
startPoint = "e5"

algebraic :: (Int, Int) -> String
algebraic (x, y) = [chr (x + 96), chr (y + 48)]

main :: IO ()
main =
  printTour $
    algebraic
      <$> knightTour
        [(\[x, y] -> (ord x - 96, ord y - 48)) startPoint]
  where
    printTour [] = return ()
    printTour tour = do
      putStrLn $ intercalate " -> " $ take 8 tour
      printTour $ drop 8 tour


  

You may also check:How to resolve the algorithm Fusc sequence step by step in the Racket programming language
You may also check:How to resolve the algorithm Left factorials step by step in the C programming language
You may also check:How to resolve the algorithm Ascending primes step by step in the Perl programming language
You may also check:How to resolve the algorithm Sorting algorithms/Heapsort step by step in the PL/I programming language
You may also check:How to resolve the algorithm Read a specific line from a file step by step in the Racket programming language