The Knight’s Tour problem is a classic puzzle where the goal is to move a knight around a chessboard such that it visits every square exactly once. In this solution, we use a backtracking approach to solve the problem.

Program Structure

The program is structured into several key parts:

1. Utility Functions: These include functions to check if the knight can move to a particular square and if the tour is complete.
2. Backtracking Algorithm: This is the heart of the program where the knight’s moves are recursively explored and backtracked if a valid tour is not found.
3. Display Function: This function prints the final tour matrix to the console.
4. Main Function: Initializes the chessboard and starts the backtracking process.

Go Code

        package main

        import (
            "fmt"
            "math"
        )

        // The size of the chessboard
        const N = 8

        // A utility function to check if a position is valid
        // The position is valid if the knight is inside the board
        // and the square is not visited yet
        func isSafe(x, y int, board [N][N]int) bool {
            return x >= 0 && x < N && y >= 0 && y < N && board[x][y] == -1
        }

        // Utility function to print the chessboard
        func printBoard(board [N][N]int) {
            for i := 0; i < N; i++ {
                for j := 0; j < N; j++ {
                    fmt.Printf("%2d ", board[i][j])
                }
                fmt.Println()
            }
        }

        // Utility function to perform the knight's tour using backtracking
        func solveKTUtil(x, y, movei int, board [N][N]int, xMove [8]int, yMove [8]int) bool {
            // Base case: If all squares are visited, return true
            if movei == N*N {
                return true
            }

            // Try all next moves from the current coordinate
            for i := 0; i < 8; i++ {
                newX := x + xMove[i]
                newY := y + yMove[i]
                if isSafe(newX, newY, board) {
                    // Make the move
                    board[newX][newY] = movei
                    // Recur to see if the tour can be completed
                    if solveKTUtil(newX, newY, movei+1, board, xMove, yMove) {
                        return true
                    }
                    // Backtrack if the move does not lead to a solution
                    board[newX][newY] = -1
                }
            }
            return false
        }

        // Function to solve the Knight Tour problem using backtracking
        func solveKnightTour() {
            // Initialize the board with -1 (unvisited squares)
            var board [N][N]int
            for i := 0; i < N; i++ {
                for j := 0; j < N; j++ {
                    board[i][j] = -1
                }
            }

            // Define all possible moves of a knight
            xMove := [8]int{2, 1, -1, -2, -2, -1, 1, 2}
            yMove := [8]int{1, 2, 2, 1, -1, -2, -2, -1}

            // Start from the first position (0, 0)
            board[0][0] = 0

            // Start the knight's tour from position (0, 0)
            if !solveKTUtil(0, 0, 1, board, xMove, yMove) {
                fmt.Println("Solution does not exist")
            } else {
                printBoard(board)
            }
        }

        // Main function to drive the program
        func main() {
            fmt.Println("Knight's Tour Problem Solution")
            solveKnightTour()
        }
        

Explanation

This program uses the following strategy:

• Backtracking: The backtracking algorithm tries to move the knight from one square to the next based on the knight’s valid moves. If the move leads to a dead end, it “backtracks” by removing the last move and trying a different path.
• Board Representation: The chessboard is represented as an 8×8 matrix where each square is initialized to -1, indicating it hasn’t been visited by the knight yet. As the knight moves, the matrix is updated with the move number.
• Move Validation: The function isSafe ensures that the knight’s next move is within the board limits and the square hasn’t been visited yet.
• Recursive Backtracking: The function solveKTUtil recursively attempts to complete the knight’s tour by making valid moves. If a solution is found, the board is printed. If no solution exists, the message “Solution does not exist” is printed.

How It Works

The knight starts at position (0, 0) on the chessboard. It then recursively tries each possible move. The recursion proceeds by making a move, then moving to the next valid square, and continues until the knight visits all the squares. If the knight is unable to complete the tour from a given position, the algorithm backtracks and tries another move.

Once a solution is found, the board is printed, showing the sequence of moves made by the knight. If no solution is found, the program prints “Solution does not exist”.

Key Points:

• Backtracking: This is the core algorithm used to find the solution.
• Chessboard Representation: An 8×8 matrix with unvisited squares marked as -1.
• Recursive Search: We attempt every possible move and backtrack if we hit a dead end.
• Output: If a solution exists, the final tour of the knight is printed; otherwise, the program indicates that no solution was found.

The program’s solution prints the knight’s path as a series of move numbers, showing how the knight travels from one square to the next.