How to resolve the algorithm Solve a Holy Knight's tour step by step in the Nim programming language

Published on 12 May 2024 09:40 PM
#Nim

How to resolve the algorithm Solve a Holy Knight's tour step by step in the Nim programming language

Table of Contents

Problem Statement

Chess coaches have been known to inflict a kind of torture on beginners by taking a chess board, placing pennies on some squares and requiring that a Knight's tour be constructed that avoids the squares with pennies. This kind of knight's tour puzzle is similar to   Hidato. The present task is to produce a solution to such problems. At least demonstrate your program by solving the following:

Note that the zeros represent the available squares, not the pennies. Extra credit is available for other interesting examples.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Solve a Holy Knight's tour step by step in the Nim programming language

Source code in the nim programming language

import sequtils, strformat

const Moves = [[-1, -2], [1, -2], [-2, -1], [2, -1], [-2, 1], [2, 1], [-1, 2], [1, 2]]

proc solve(pz: var seq[seq[int]]; sx, sy, idx, count: Natural): bool =

  if idx > count: return true

  var x, y: int
  for move in Moves:
    x = sx + move[0]
    y = sy + move[1]
    if x in 0..pz.high and y in 0..pz.high and pz[x][y] == 0:
      pz[x][y] = idx
      if pz.solve(x, y, idx + 1, count): return true
      pz[x][y] = 0


proc findSolution(board: openArray[string]) =
  let sz = board.len
  var pz = newSeqWith(sz, repeat(-1, sz))

  var count = 0
  var x, y: int
  for i in 0..<sz:
    for j in 0..<sz:
      case board[i][j]
      of 'x':
        pz[i][j] = 0
        inc count
      of 's':
        pz[i][j] = 1
        inc count
        (x, y) = (i, j)
      else:
        discard

  if pz.solve(x, y, 2, count):
    for i in 0..<sz:
      for j in 0..<sz:
        if pz[i][j] != -1:
          stdout.write &"{pz[i][j]:02}  "
        else:
          stdout.write "--  "
      stdout.write '\n'

when isMainModule:

  const

    Board1 = [" xxx    ",
              " x xx   ",
              " xxxxxxx",
              "xxx  x x",
              "x x  xxx",
              "sxxxxxx ",
              "  xx x  ",
              "   xxx  "]

    Board2 = [".....s.x.....",
              ".....x.x.....",
              "....xxxxx....",
              ".....xxx.....",
              "..x..x.x..x..",
              "xxxxx...xxxxx",
              "..xx.....xx..",
              "xxxxx...xxxxx",
              "..x..x.x..x..",
              ".....xxx.....",
              "....xxxxx....",
              ".....x.x.....",
              ".....x.x....."]

  Board1.findSolution()
  echo()
  Board2.findSolution()

You may also check:How to resolve the algorithm Sorting algorithms/Quicksort step by step in the ACL2 programming language
You may also check:How to resolve the algorithm Parsing/RPN to infix conversion step by step in the C# programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Pascal programming language
You may also check:How to resolve the algorithm 24 game step by step in the Haskell programming language
You may also check:How to resolve the algorithm Polynomial regression step by step in the REXX programming language