# 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.

By | July 30, 2024

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 usageconst N = 5; // Example for a 5x5 boardconsole.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 = 0def 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 countdef 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] = Falsedef is_valid(x, y, N, visited):    return 0 <= x < N and 0 <= y < N and not visited[x][y]# Example usageN = 5 # Example for a 5x5 boardprint("Number of Knight's Tours:", count_knights_tours(N))``