# Chess Knight Shortest Path - Algorithm Question

Hello.

I’m trying to make the Knight short path problem in swift
Based on this code

``````// all 8 possible movements for a knight
fileprivate let knightMoves = [
[ 2, -1],
[ 2,  1],
[-2,  1],
[-2, -1],
[ 1,  2],
[ 1, -2],
[-1,  2],
[-1, -2]
]

struct Node {
let y: Int, x: Int // (x, y) represents chessboard coordinates
let dist: Int // dist represent its minimum distance from the source

init(x: Int, y: Int, dist: Int = 0) {
self.x = x
self.y = y
self.dist = dist
}
}

extension Node: Hashable {
// Using Node struct as a key we need conform to Hashable
var hashValue: Int {
return "\(self.x)\(self.y)".hashValue
}

static func ==(lhs: Node, rhs: Node) -> Bool {
return lhs.x == rhs.x && lhs.y == rhs.y
}
}

enum BfsError: Error {
case shortestPathNotFound
}

// Find minimum number of steps taken by the knight
// from source to destination using BFS
func bfs(src: Node, dest: Node) throws -> Int {
// map to check if matrix cell is visited before or not
var visited = [Node: Bool]()

// Create a queue and enqueue first node
// Queue node used in BFS
var q = Queue(array: [Node]())
q.enqueue(src)

// Run until queue is empty
while (!q.isEmpty) {

// Pop front node and process it
guard let node = q.dequeue() else { break }

let x = node.x
let y = node.y
let dist = node.dist

// If destination is reached, return distance
if (x == dest.x && y == dest.y) { return dist }

// Skip if location is visited
if visited[node] == nil {
visited[node] = true

// Check for all 8 possible movements for a knight
// and enqueue each valid movement
for i in 0..<knightMoves.count {

// Get the new valid position of Knight from current
// position on chessboard and enqueue it in the
// queue with +1 distance
let position = knightMoves[i]
let x1 = x + position
let y1 = y + position

if (isValid(x: x1, y: y1)) {
q.enqueue(Node(x: x1, y: y1, dist: dist + 1))
}
}
}
}
throw BfsError.shortestPathNotFound
}

// Check if (x, y) is valid chessboard cordinate
// Note that a knight cannot go out of the chessboard
fileprivate func isValid(x: Int, y: Int) -> Bool {
guard (x >= 0 && y >= 0 && x < knightMoves.count && y < knightMoves.count) else { return false }
return true
}

fileprivate struct Queue<T> {
fileprivate var array = [T]()

public var isEmpty: Bool {
return self.array.isEmpty
}

public var count: Int {
return self.array.count
}

public mutating func enqueue(_ element: T) {
self.array.append(element)
}

public mutating func dequeue() -> T? {
if self.isEmpty {
return nil
} else {
return self.array.removeFirst()
}
}

public var front: T? {
return self.array.first
}
}

if let a = try? bfs(src: Node(x: 0, y: 0), dest: Node(x: 7, y: 0)) {
print("Minimum number of steps required is \(a).")
}
``````

What is the proper way to trace back the steps that the knight actually made?
And not only the minimum amount of steps?
Thanks a lot for the time!

This topic was automatically closed after 166 days. New replies are no longer allowed.