This program implements the backtracking algorithm to solve the Knight's Tour problem on a chessboard.

knight_move.rs

use std::env;
use std::process::Command;
use std::time::Duration;
use std::{thread, vec};

fn print_board(size_x: i32, _size_y: i32, board: &Vec<Vec<i32>>) {
    println!("Knight's Tour Problem");
    println!("Chess Board:");
    print!(" ");
    for _ in 0..size_x {
        print!("___ ");
    }
    println!();
    for i in 0..board.len() {
        for j in 0..board[i].len() {
            print!("| {} ", if (board[i][j]) == -1 { " " } else { "X" });
        }
        println!("|");
        print!(" ");
        for _ in 0..size_x {
            print!("--- ");
        }
        println!();
    }

    println!();
    println!();
    println!();

    println!("Knight's Tour Path:");
    print!(" ");
    for j in 0..size_x {
        print!(
            "{}",
            if board[0][j as usize] < 10 {
                "___ "
            } else {
                "____ "
            }
        );
    }
    println!();
    for i in 0..board.len() {
        for j in 0..board[i].len() {
            print!(
                "| {} ",
                if (board[i][j]) == -1 {
                    " ".to_string()
                } else {
                    board[i][j].to_string()
                }
            );
        }
        println!("|");
        print!(" ");
        for j in 0..size_x {
            print!(
                "{}",
                if board[i][j as usize] < 10 {
                    "--- "
                } else {
                    "---- "
                }
            );
        }
        println!();
    }
}

fn is_valid_move(_size_x: i32, _size_y: i32, board: &Vec<Vec<i32>>, x: i32, y: i32) -> bool {
    return x >= 0
        && x < board.len() as i32
        && y >= 0
        && y < board[0].len() as i32
        && board[x as usize][y as usize] == -1;
}

fn solve_knight_tour(
    mut _solution_board: &mut Vec<Vec<i32>>,
    mut _x_move: [i32; 8],
    mut _y_move: [i32; 8],
    mut _move_count: i32,
    mut _x: i32,
    mut _y: i32,
    size_x: usize,
    size_y: usize,
) -> bool {
    let mut next_x: i32;
    let mut next_y: i32;

    if _move_count == size_x as i32 * size_y as i32 {
        return true;
    }

    for i in 0..8 {
        next_x = _x + _x_move[i];
        next_y = _y + _y_move[i];

        if next_x >= 0 && next_x < size_x as i32 && next_y >= 0 && next_y < size_y as i32 {
            if is_valid_move(
                size_x as i32,
                size_y as i32,
                &_solution_board,
                next_x,
                next_y,
            ) {
                _solution_board[next_x as usize][next_y as usize] = _move_count;

                let _ = Command::new("clear").status();
                print_board(size_x as i32, size_y as i32, &_solution_board);
                thread::sleep(Duration::from_secs_f32(0.2));
                if solve_knight_tour(
                    _solution_board,
                    _x_move,
                    _y_move,
                    _move_count + 1,
                    next_x,
                    next_y,
                    size_x,
                    size_y,
                ) {
                    return true;
                } else {
                    _solution_board[next_x as usize][next_y as usize] = -1;
                }
            }
        }
    }

    return false;
}

fn main() {
    let args: Vec<String> = env::args().collect();

    if args.len() < 3 {
        println!("Please provide size_x and size_y as command line arguments.");
        return;
    }

    let size_x: usize = args[1].parse().unwrap_or(5);
    let size_y: usize = args[2].parse().unwrap_or(6);

    let mut solution_board = vec![vec![-1; size_x]; size_y];
    let possible_x_moves: [i32; 8] = [2, 1, -1, -2, -2, -1, 1, 2];
    let possible_y_moves: [i32; 8] = [1, 2, 2, 1, -1, -2, -2, -1];

    solution_board[0][0] = 0;

    if solve_knight_tour(
        &mut solution_board,
        possible_x_moves,
        possible_y_moves,
        1,
        0,
        0,
        size_x,
        size_y,
    ) == false
    {
        let _ = Command::new("clear").status();
        println!("Solution does not exist for the given board dimensions.");
    } else {
        let _ = Command::new("clear").status();
        print_board(size_x as i32, size_y as i32, &solution_board);
    }
}

Knight's Tour in Rust

This program implements the backtracking algorithm to solve the Knight's Tour problem on a chessboard.

How to Run

• If you have Rust Installed:
  • Open terminal and navigate to the directory where the code is located.
  • Run cargo build to compile the code.
  • Run cargo run -- <board_size> to run the program, replacing <board_size> with the desired size of the chessboard. Example: cargo run -- 5 8

The Knight's Tour Problem

The Knight's Tour problem is like a brainteaser for chess lovers. Imagine a knight on a chessboard, and you want it to visit every square exactly once, but only using its unique "L" shaped move. This program helps you find a solution, so you don't have to spend hours puzzling over it yourself.

Backtracking Algorithm

This program uses backtracking, a kind of like a maze solving strategy. It explores different paths (knight moves) and backtracks when a dead end is reached.

Here's a breakdown of the algorithm:

1. Initialize the board: A chessboard is represented as a grid where each square is empty or has a number showing the knight's visit order.
2. Define knight's moves: An array stores the possible ways a knight can move from any square.
3. Recursive function: The solve_knight_tour function attempts to solve the puzzle. It takes the board, knight move options, current move count, and knight's position as arguments.
   • Base Case: If the knight has visited every square, a solution is found! The function returns true.
   • Iterate through possible moves: It tries each of the eight possible knight moves.
     • Validate move: It checks if the move is within board boundaries and lands on an unvisited square.
     • Place move: If valid, the move number is placed on the board, and the function calls itself recursively with the updated board and knight's new position.
     • Backtrack: If the recursive call doesn't find a solution from that move, the move number is removed from the board (backtracking).
4. Main function:
   • Sets the board size.
   • Defines the knight's possible x and y moves.
   • Places the knight on the starting square (usually (0, 0)) with move number 0.
   • Calls the solve_knight_tour function.
   • If the function returns false, no solution exists, and a message is displayed.
   • Otherwise, the final board configuration, showing the knight's path, is printed.

This was just a weekend project to spend time on [you know how programmers are ;) ]. I hope you find it interesting :)