[Algorithm] Knight's Tour Algorithm

Explanation of Knight’s Tour

The Knight’s Tour problem involves finding a path for a knight on a chessboard that visits every square exactly once according to certain rules. The knight moves in an L-shape in chess, moving two squares in one direction and then one square perpendicular to that direction.

Purpose of the Problem

• The goal is to find a route that allows the knight to visit every square on the chessboard exactly once.
• This problem can be solved using algorithms like Backtracking or Warnsdorff’s Rule.

Advantages

• Path exploration and optimization: It can be applied to game scenarios or path optimization problems and is useful for learning exploration algorithms.
• Mathematical interest: It can be extended to combinatorial problems and graph theory, providing training in mathematical approaches.

Disadvantages

• Complexity: The amount of computation required to solve larger chessboards can be very high.
• Dependence on Backtracking: The backtracking method may not be efficient as it requires several attempts.

JavaScript Example Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const N = 8;
let board = Array.from({ length: N }, () => Array(N).fill(-1));

const movesX = [2, 1, -1, -2, -2, -1, 1, 2];
const movesY = [1, 2, 2, 1, -1, -2, -2, -1];

function isSafe(x, y, board) {
  return x >= 0 && x < N && y >= 0 && y < N && board[x][y] === -1;
}

function solveKnightTour(x, y, move, board) {
  if (move === N * N) return true;

  for (let i = 0; i < 8; i++) {
    const nextX = x + movesX[i];
    const nextY = y + movesY[i];

    if (isSafe(nextX, nextY, board)) {
      board[nextX][nextY] = move;
      if (solveKnightTour(nextX, nextY, move + 1, board)) {
        return true;
      } else {
        board[nextX][nextY] = -1; // Backtracking
      }
    }
  }
  return false;
}

function knightTour() {
  board[0][0] = 0; // Starting position
  if (!solveKnightTour(0, 0, 1, board)) {
    console.log("Cannot solve.");
  } else {
    console.log(board);
  }
}

knightTour();

This code solves the Knight’s Tour using a backtracking algorithm. The solveKnightTour function recursively explores possible paths and backtracks if necessary.

Rust Example Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
const N: usize = 8;
let mut board = [[-1; N]; N];

let moves_x: [isize; 8] = [2, 1, -1, -2, -2, -1, 1, 2];
let moves_y: [isize; 8] = [1, 2, 2, 1, -1, -2, -2, -1];

fn is_safe(x: isize, y: isize, board: &[[i32; N]; N]) -> bool {
    x >= 0 && x < N as isize && y >= 0 && y < N as isize && board[x as usize][y as usize] == -1
}

fn solve_knight_tour(x: isize, y: isize, move_num: i32, board: &mut [[i32; N]; N]) -> bool {
    if move_num == (N * N) as i32 {
        return true;
    }

    for i in 0..8 {
        let next_x = x + moves_x[i];
        let next_y = y + moves_y[i];

        if is_safe(next_x, next_y, board) {
            board[next_x as usize][next_y as usize] = move_num;
            if solve_knight_tour(next_x, next_y, move_num + 1, board) {
                return true;
            } else {
                board[next_x as usize][next_y as usize] = -1; // Backtracking
            }
        }
    }
    false
}

fn knight_tour() {
    board[0][0] = 0;
    if !solve_knight_tour(0, 0, 1, &mut board) {
        println!("Cannot solve.");
    } else {
        for row in board.iter() {
            for cell in row.iter() {
                print!("{:3} ", cell);
            }
            println!();
        }
    }
}

knight_tour();

This Rust code operates in the same manner, using recursion and backtracking to solve the problem.

Use Cases

• Pathfinding problems: It can be used in games or robotics to optimally explore paths.
• Graph theory learning: It is useful for learning about relationships between nodes and pathfinding algorithms.