A knight’s tour is a sequence of moves by a knight on a chessboard such that all squares are visited once. Given N, write a function to return the number of knight’s tours on an N by N chessboard.

Java:

public class KnightsTour {
    private static final int[] dx = {2, 2, 1, 1, -1, -1, -2, -2};
    private static final int[] dy = {1, -1, 2, -2, 2, -2, 1, -1};
    private static int count = 0;
    public static int countKnightsTours(int N) {
        boolean[][] visited = new boolean[N][N];
        count = 0;
        knightsTour(0, 0, 1, N, visited);
        return count;
    }
    private static void knightsTour(int x, int y, int moveCount, int N, boolean[][] visited) {
        if (moveCount == N * N) {
            count++;
            return;
        }
        visited[x][y] = true;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (isValid(nx, ny, N, visited)) {
                knightsTour(nx, ny, moveCount + 1, N, visited);
            }
        }
        visited[x][y] = false;
    }
    private static boolean isValid(int x, int y, int N, boolean[][] visited) {
        return x >= 0 && x < N && y >= 0 && y < N && !visited[x][y];
    }
    public static void main(String[] args) {
        int N = 5; // Example for a 5x5 board
        System.out.println("Number of Knight's Tours: " + countKnightsTours(N));
    }
}

Javascript

const dx = [2, 2, 1, 1, -1, -1, -2, -2];
const dy = [1, -1, 2, -2, 2, -2, 1, -1];
let count = 0;
function countKnightsTours(N) {
    count = 0;
    const visited = Array.from({ length: N }, () => Array(N).fill(false));
    knightsTour(0, 0, 1, N, visited);
    return count;
}
function knightsTour(x, y, moveCount, N, visited) {
    if (moveCount === N * N) {
        count++;
        return;
    }
    visited[x][y] = true;
    for (let i = 0; i < 8; i++) {
        const nx = x + dx[i];
        const ny = y + dy[i];
        if (isValid(nx, ny, N, visited)) {
            knightsTour(nx, ny, moveCount + 1, N, visited);
        }
    }
    visited[x][y] = false;
}
function isValid(x, y, N, visited) {
    return x >= 0 && x < N && y >= 0 && y < N && !visited[x][y];
}
// Example usage
const N = 5; // Example for a 5x5 board
console.log("Number of Knight's Tours: " + countKnightsTours(N));

Python:

dx = [2, 2, 1, 1, -1, -1, -2, -2]
dy = [1, -1, 2, -2, 2, -2, 1, -1]
count = 0
def count_knights_tours(N):
    global count
    count = 0
    visited = [[False for _ in range(N)] for _ in range(N)]
    knights_tour(0, 0, 1, N, visited)
    return count
def knights_tour(x, y, move_count, N, visited):
    global count
    if move_count == N * N:
        count += 1
        return
    visited[x][y] = True
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if is_valid(nx, ny, N, visited):
            knights_tour(nx, ny, move_count + 1, N, visited)
    visited[x][y] = False
def is_valid(x, y, N, visited):
    return 0 <= x < N and 0 <= y < N and not visited[x][y]
# Example usage
N = 5 # Example for a 5x5 board
print("Number of Knight's Tours:", count_knights_tours(N))

Asked by: Google