Knight's Tour

Definition

Definition

The Knight's Tour Algorithm is a method used to solve the puzzle of moving a knight chess piece to visit every square on a chessboard exactly once

Explanation

Starting with an empty chessboard, positioning the knight arbitrarily on one of its squares. Subsequently, it systematically investigates all feasible moves adhering to the regulations of chess. During each iteration, the algorithm favors moves that lead to unvisited squares. If the knight encounters a situation where no further unvisited squares are accessible, it retraces its steps to the previous position, seeking an alternative path. This iterative process persists until either every square has been visited, signifying a successful tour, or all potential moves have been exhausted, resulting in an unsuccessful attempt

Guidance

• Start with an empty chessboard and place the knight on any square
• From the current position, calculate all possible moves according to the knight's movement rules
• Choose one of the unvisited squares reachable from the current position
• Move the knight to the chosen square and mark it as visited
• Repeat steps 2-4 until either all squares are visited or there are no more unvisited squares reachable from the current position
• If all squares are visited, the algorithm terminates successfully. If not, backtrack to the previous position and choose another unvisited square
• Continue backtracking until either a successful tour is found or all possible paths are exhausted

Tips

• prioritize moves that lead to squares with fewer unvisited neighbors to increase the chances of finding a successful tour
• implement a data structure to efficiently track visited squares and available moves
• consider implementing heuristics or optimizations to improve the algorithm's performance, such as Warnsdorff's rule for selecting the next move

Practice

Practice

knight_tour(board, row, col, move_count):
    if move_count == board.size ** 2:
        return true  // All squares visited, tour complete

    for each possible move from (row, col) as (next_row, next_col):
        if is_valid_move(board, next_row, next_col):
            mark_square_as_visited(board, next_row, next_col, move_count)
            if knight_tour(board, next_row, next_col, move_count + 1):
                return true  // Successful tour found
            else:
                unmark_square(board, next_row, next_col) // Backtrack
    return false  // No successful tour found

initialize chessboard
start_row, start_col = choose_starting_position(chessboard)
if knight_tour(chessboard, start_row, start_col, 1):
    print("Successful tour found")
else:
    print("No tour found")

Solution

package main

func getPossibleMoves(chessboard [][]int, position [2]int) [][2]int {
	possibleMoves := [][2]int{
		{-1, -2},
		{-2, -1},
		{1, -2},
		{2, -1},
		{-2, 1},
		{-1, 2},
		{1, 2},
		{2, 1},
	}

	var moves [][2]int
	for _, move := range possibleMoves {
		dx, dy := move[0], move[1]
		x, y := position[0]+dx, position[1]+dy
		boardSize := len(chessboard)
		if x >= 0 && y >= 0 && x < boardSize && y < boardSize {
			moves = append(moves, [2]int{x, y})
		}
	}
	return moves
}

func isMoveAllowed(chessboard [][]int, move [2]int) bool {
	x, y := move[0], move[1]
	return chessboard[x][y] != 1
}

func knightTourRecursive(chessboard [][]int, moves [][2]int, totalMoves int) bool {
	if len(moves) == totalMoves {
		return true
	}

	lastMove := moves[len(moves)-1]
	possibleMoves := getPossibleMoves(chessboard, lastMove)

	for _, currentMove := range possibleMoves {
		if isMoveAllowed(chessboard, currentMove) {
			x, y := currentMove[0], currentMove[1]
			moves = append(moves, currentMove)
			chessboard[x][y] = 1

			if knightTourRecursive(chessboard, moves, totalMoves) {
				return true
			}

			moves = moves[:len(moves)-1]
			chessboard[x][y] = 0
		}
	}

	return false
}

func knightTour(chessboardSize int) [][2]int {
	chessboard := make([][]int, chessboardSize)
	for i := range chessboard {
		chessboard[i] = make([]int, chessboardSize)
	}

	moves := [][2]int{{0, 0}}
	chessboard[0][0] = 1

	totalMoves := chessboardSize * chessboardSize
	solutionWasFound := knightTourRecursive(chessboard, moves, totalMoves)

	if solutionWasFound {
		return moves
	}
	return nil
}

import java.util.ArrayList;
import java.util.List;

public class KnightTour {

  static List<Pair> getPossibleMoves(int[][] chessboard, Pair position) {
    int[][] possibleMoves = {
        {-1, -2},
        {-2, -1},
        {1, -2},
        {2, -1},
        {-2, 1},
        {-1, 2},
        {1, 2},
        {2, 1}
    };

    List<Pair> moves = new ArrayList<>();
    for (int[] move : possibleMoves) {
      int dx = move[0];
      int dy = move[1];
      int x = position.x + dx;
      int y = position.y + dy;
      int boardSize = chessboard.length;
      if (x >= 0 && y >= 0 && x < boardSize && y < boardSize) {
        moves.add(new Pair(x, y));
      }
    }
    return moves;
  }

  static boolean isMoveAllowed(int[][] chessboard, Pair move) {
    int x = move.x;
    int y = move.y;
    return chessboard[x][y] != 1;
  }

  static boolean knightTourRecursive(int[][] chessboard, List<Pair> moves, int totalMoves) {
    if (moves.size() == totalMoves) {
      return true;
    }

    Pair lastMove = moves.get(moves.size() - 1);
    List<Pair> possibleMoves = getPossibleMoves(chessboard, lastMove);

    for (Pair currentMove : possibleMoves) {
      if (isMoveAllowed(chessboard, currentMove)) {
        int x = currentMove.x;
        int y = currentMove.y;
        moves.add(currentMove);
        chessboard[x][y] = 1;

        if (knightTourRecursive(chessboard, moves, totalMoves)) {
          return true;
        }

        moves.remove(moves.size() - 1);
        chessboard[x][y] = 0;
      }
    }

    return false;
  }

  static List<Pair> knightTour(int chessboardSize) {
    int[][] chessboard = new int[chessboardSize][chessboardSize];
    List<Pair> moves = new ArrayList<>();
    moves.add(new Pair(0, 0));
    chessboard[0][0] = 1;

    int totalMoves = chessboardSize * chessboardSize;
    boolean solutionWasFound = knightTourRecursive(chessboard, moves, totalMoves);

    if (solutionWasFound) {
      return moves;
    }
    return new ArrayList<>();
  }

  static class Pair {

    int x, y;

    Pair(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }
}

function getPossibleMoves(chessboard, position) {
  const possibleMoves = [
    [-1, -2],
    [-2, -1],
    [1, -2],
    [2, -1],
    [-2, 1],
    [-1, 2],
    [1, 2],
    [2, 1],
  ];

  return possibleMoves
    .map(([dx, dy]) => [position[0] + dx, position[1] + dy])
    .filter(([x, y]) => {
      const boardSize = chessboard.length;
      return x >= 0 && y >= 0 && x < boardSize && y < boardSize;
    });
}

function isMoveAllowed(chessboard, move) {
  const [x, y] = move;
  return chessboard[x][y] !== 1;
}

function knightTourRecursive(chessboard, moves, totalMoves) {
  if (moves.length === totalMoves) {
    return true;
  }

  const lastMove = moves[moves.length - 1];
  const possibleMoves = getPossibleMoves(chessboard, lastMove);

  for (const currentMove of possibleMoves) {
    if (isMoveAllowed(chessboard, currentMove)) {
      const [x, y] = currentMove;
      moves.push(currentMove);
      chessboard[x][y] = 1;

      if (knightTourRecursive(chessboard, moves, totalMoves)) {
        return true;
      }

      moves.pop();
      chessboard[x][y] = 0;
    }
  }

  return false;
}

function knightTour(chessboardSize) {
  const chessboard = Array(chessboardSize)
    .fill(null)
    .map(() => Array(chessboardSize).fill(0));

  const moves = [[0, 0]];
  chessboard[0][0] = 1;

  const totalMoves = chessboardSize * chessboardSize;
  const solutionWasFound = knightTourRecursive(chessboard, moves, totalMoves);

  return solutionWasFound ? moves : [];
}

fun getPossibleMoves(chessboard: Array<IntArray>, position: IntArray): List<IntArray> {
    val possibleMoves = arrayOf(
            intArrayOf(-1, -2),
            intArrayOf(-2, -1),
            intArrayOf(1, -2),
            intArrayOf(2, -1),
            intArrayOf(-2, 1),
            intArrayOf(-1, 2),
            intArrayOf(1, 2),
            intArrayOf(2, 1)
    )

    val moves = mutableListOf<IntArray>()
    for ((dx, dy) in possibleMoves) {
        val x = position[0] + dx
        val y = position[1] + dy
        val boardSize = chessboard.size
        if (x >= 0 && y >= 0 && x < boardSize && y < boardSize) {
            moves.add(intArrayOf(x, y))
        }
    }
    return moves
}

fun isMoveAllowed(chessboard: Array<IntArray>, move: IntArray): Boolean {
    val (x, y) = move
    return chessboard[x][y] != 1
}

fun knightTourRecursive(chessboard: Array<IntArray>, moves: MutableList<IntArray>, totalMoves: Int): Boolean {
    if (moves.size == totalMoves) {
        return true
    }

    val lastMove = moves.last()
    val possibleMoves = getPossibleMoves(chessboard, lastMove)

    for (currentMove in possibleMoves) {
        if (isMoveAllowed(chessboard, currentMove)) {
            val (x, y) = currentMove
            moves.add(currentMove)
            chessboard[x][y] = 1

            if (knightTourRecursive(chessboard, moves, totalMoves)) {
                return true
            }

            moves.removeAt(moves.size - 1)
            chessboard[x][y] = 0
        }
    }

    return false
}

fun knightTour(chessboardSize: Int): List<IntArray> {
    val chessboard = Array(chessboardSize) { IntArray(chessboardSize) }
    val moves = mutableListOf(intArrayOf(0, 0))
    chessboard[0][0] = 1

    val totalMoves = chessboardSize * chessboardSize
    val solutionWasFound = knightTourRecursive(chessboard, moves, totalMoves)

    return if (solutionWasFound) moves else emptyList()
}

def get_possible_moves(chessboard, position):
    possible_moves = [
        (-1, -2),
        (-2, -1),
        (1, -2),
        (2, -1),
        (-2, 1),
        (-1, 2),
        (1, 2),
        (2, 1),
    ]

    board_size = len(chessboard)
    moves = []
    for dx, dy in possible_moves:
        x = position[0] + dx
        y = position[1] + dy
        if 0 <= x < board_size and 0 <= y < board_size:
            moves.append((x, y))
    return moves


def is_move_allowed(chessboard, move):
    x, y = move
    return chessboard[x][y] != 1


def knight_tour_recursive(chessboard, moves, total_moves):
    if len(moves) == total_moves:
        return True

    last_move = moves[-1]
    possible_moves = get_possible_moves(chessboard, last_move)

    for current_move in possible_moves:
        if is_move_allowed(chessboard, current_move):
            x, y = current_move
            moves.append(current_move)
            chessboard[x][y] = 1

            if knight_tour_recursive(chessboard, moves, total_moves):
                return True

            moves.pop()
            chessboard[x][y] = 0

    return False


def knight_tour(chessboard_size):
    chessboard = [[0] * chessboard_size for _ in range(chessboard_size)]
    moves = [(0, 0)]
    chessboard[0][0] = 1

    total_moves = chessboard_size * chessboard_size
    solution_was_found = knight_tour_recursive(chessboard, moves, total_moves)

    return moves if solution_was_found else []

fn get_possible_moves(chessboard: &Vec<Vec<i32>>, position: &(usize, usize)) -> Vec<(usize, usize)> {
    let possible_moves = vec![
        (-1, -2),
        (-2, -1),
        (1, -2),
        (2, -1),
        (-2, 1),
        (-1, 2),
        (1, 2),
        (2, 1),
    ];

    let board_size = chessboard.len();
    let mut moves = Vec::new();
    for (dx, dy) in possible_moves {
        let x = position.0 as i32 + dx;
        let y = position.1 as i32 + dy;
        if x >= 0 && y >= 0 && x < board_size as i32 && y < board_size as i32 {
            moves.push((x as usize, y as usize));
        }
    }
    moves
}

fn is_move_allowed(chessboard: &Vec<Vec<i32>>, move: &(usize, usize)) -> bool {
    let (x, y) = *move;
    chessboard[x][y] != 1
}

fn knight_tour_recursive(chessboard: &mut Vec<Vec<i32>>, moves: &mut Vec<(usize, usize)>, total_moves: usize) -> bool {
    if moves.len() == total_moves {
        return true;
    }

    let last_move = *moves.last().unwrap();
    let possible_moves = get_possible_moves(chessboard, &last_move);

    for current_move in possible_moves {
        if is_move_allowed(chessboard, &current_move) {
            let (x, y) = current_move;
            moves.push(current_move);
            chessboard[x][y] = 1;

            if knight_tour_recursive(chessboard, moves, total_moves) {
                return true;
            }

            moves.pop();
            chessboard[x][y] = 0;
        }
    }

    false
}

fn knight_tour(chessboard_size: usize) -> Vec<(usize, usize)> {
    let mut chessboard = vec![vec![0; chessboard_size]; chessboard_size];
    let mut moves = vec![(0, 0)];
    chessboard[0][0] = 1;

    let total_moves = chessboard_size * chessboard_size;
    let solution_was_found = knight_tour_recursive(&mut chessboard, &mut moves, total_moves);

    if solution_was_found {
        moves
    } else {
        Vec::new()
    }
}

function getPossibleMoves(
  chessboard: number[][],
  position: [number, number],
): [number, number][] {
  const possibleMoves: [number, number][] = [
    [-1, -2],
    [-2, -1],
    [1, -2],
    [2, -1],
    [-2, 1],
    [-1, 2],
    [1, 2],
    [2, 1],
  ];

  const boardSize = chessboard.length;
  return possibleMoves
    .map(([dx, dy]) => [position[0] + dx, position[1] + dy])
    .filter(([x, y]) => x >= 0 && y >= 0 && x < boardSize && y < boardSize);
}

function isMoveAllowed(
  chessboard: number[][],
  move: [number, number],
): boolean {
  const [x, y] = move;
  return chessboard[x][y] !== 1;
}

function knightTourRecursive(
  chessboard: number[][],
  moves: [number, number][],
  totalMoves: number,
): boolean {
  if (moves.length === totalMoves) {
    return true;
  }

  const lastMove = moves[moves.length - 1];
  const possibleMoves = getPossibleMoves(chessboard, lastMove);

  for (const currentMove of possibleMoves) {
    if (isMoveAllowed(chessboard, currentMove)) {
      const [x, y] = currentMove;
      moves.push(currentMove);
      chessboard[x][y] = 1;

      if (knightTourRecursive(chessboard, moves, totalMoves)) {
        return true;
      }

      moves.pop();
      chessboard[x][y] = 0;
    }
  }

  return false;
}

function knightTour(chessboardSize: number): [number, number][] {
  const chessboard: number[][] = Array.from({ length: chessboardSize }, () =>
    Array(chessboardSize).fill(0),
  );
  const moves: [number, number][] = [[0, 0]];
  chessboard[0][0] = 1;

  const totalMoves = chessboardSize * chessboardSize;
  const solutionWasFound = knightTourRecursive(chessboard, moves, totalMoves);

  return solutionWasFound ? moves : [];
}