Knight's Tour (backtracking solution)

Task:
Write a program that finds a knight's tour on an n × n chessboard. The knight must visit all squares of the board so that every square is visited exactly once, following the rules of how a knight moves in chess.

A tour can be:

  • open – the last square does not attack the first one;
  • closed – the last square attacks the first one, forming a cycle.
This example looks for any valid tour using backtracking.

Input: The number n (5 ≤ n ≤ 10) is read from standard input.
Output: If a solution exists, a matrix is printed in which every square is numbered with the order in which it was visited (from 1 to n×n).

Example:

Input:
5

Output (an example of one tour):
 1  6 15 10 21
14  9 20  5 16
19  2  7 22 11
 8 13 24 17  4
25 18  3 12 23
  

Instructions and idea of the solution

The Knight's Tour is one of the best-known examples of the backtracking algorithm. The idea is the following:

  • We start from the starting square and write down the move number (1, 2, 3, …).
  • The knight has at most 8 possible jumps – we check them in order.
  • If the next square is free and inside the board, we move to it.
  • If there are no more possible jumps → we go back (backtracking).
  • When we have filled n×n squares, we have a valid tour.

Because of the complexity of the problem, the search for a tour relies on depth-first search and smart rejection of positions that lead to a dead end.

Solution in C++


#include <iostream>
#include <vector>
using namespace std;

int n;
vector<vector<int>> board;

// All possible knight jumps
int dx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int dy[8] = { 1, 2,  2,  1, -1, -2, -2, -1 };

// Checks whether a move is valid
bool isValid(int x, int y) {
    return (x >= 0 && x < n && y >= 0 && y < n && board[x][y] == 0);
}

// Recursive function for the knight's tour
bool tour(int x, int y, int step) {
    if (step == n * n)
        return true; // All moves made successfully

    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isValid(nx, ny)) {
            board[nx][ny] = step + 1;

            if (tour(nx, ny, step + 1))
                return true;

            board[nx][ny] = 0; // Backtracking
        }
    }
    return false;
}

int main() {
    cout << "Enter the board size n (5 <= n <= 10): ";
    cin >> n;

    if (n < 5 || n > 10) {
        cout << "Allowed values are from 5 to 10." << endl;
        return 1;
    }

    board.assign(n, vector<int>(n, 0));

    // Starting position of the knight (0, 0)
    board[0][0] = 1;

    if (tour(0, 0, 1)) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << board[i][j] << "\t";
            }
            cout << endl;
        }
    } else {
        cout << "There is no solution for the given board." << endl;
    }

    return 0;
}
  

Code explanation

The program uses the matrix board, which stores the order number of the tour.

  • isValid() checks whether a move is allowed: inside the board and not visited.
  • tour() recursively tries the knight's 8 moves.
  • If n×n moves are filled, a solution has been found.
  • If we reach a dead end → we go back (backtracking).

Comment on efficiency and improvements

Basic backtracking for the Knight's Tour has a very large (exponential) complexity. It works well for small boards, but becomes slow for larger ones.

Possible improvements:

  • Warnsdorff's rule – always choose the move with the fewest continuations. It speeds up the algorithm drastically.
  • Using heuristics to reduce branching.
  • Using bitmaps to optimize the occupancy check.
  • Remembering problematic configurations.

In practice, Warnsdorff's heuristic can find a solution on an 8×8 board in a few milliseconds.

Version 1 — Fully commented C++ solution (brute force + backtracking)

This section contains a fully commented version of the basic backtracking algorithm for the knight's tour problem. The goal is to show clearly what happens in every step of the algorithm.

This is excellent additional material for students who want to understand:

  • what "checking a valid move" means,
  • how recursion works in a backtracking algorithm,
  • how "going back" (undoing a move) is done,
  • what the standard structure of a recursive search looks like.

Fully commented C++ code (Version 1)


// -----------------------------------------------------------
//   KNIGHT'S TOUR – Version 1 (brute force + backtracking)
//   Fully explained version of the code, with line-by-line comments.
// -----------------------------------------------------------

#include <iostream>
#include <vector>
using namespace std;

// All 8 possible knight moves
int dx[8] = { 2, 1, -1, -2, -2, -1,  1, 2 };
int dy[8] = { 1, 2,  2,  1, -1, -2, -2, -1 };

// We check whether it is possible to move to square (x, y)
bool valid(int x, int y, int n, vector<vector<int>>& board) {
    // It must be inside the board
    if (x < 0 || x >= n) return false;
    if (y < 0 || y >= n) return false;

    // The square must be unvisited (0 means not visited)
    if (board[x][y] != 0) return false;

    return true;
}

// Main recursive function
bool tour(int x, int y, int step, int n, vector<vector<int>>& board) {
    // If we have filled all n*n squares → the end!
    if (step == n*n)
        return true;

    // We go through all 8 possible knight moves
    for (int i = 0; i < 8; i++) {

        // We compute the new square
        int nx = x + dx[i];
        int ny = y + dy[i];

        // Checking whether the move is allowed
        if (valid(nx, ny, n, board)) {

            // -------------------------------
            // 1) We place the knight on the new square
            // -------------------------------
            board[nx][ny] = step + 1;

            // -------------------------------
            // 2) We continue the tour recursively
            // -------------------------------
            if (tour(nx, ny, step + 1, n, board))
                return true; // If it succeeds → done

            // -------------------------------
            // 3) BACKTRACKING (going back)
            //    If the recursion did NOT find a solution,
            //    we undo the move and try the next one.
            // -------------------------------
            board[nx][ny] = 0;
        }
    }

    // If no move from this position leads to a solution
    return false;
}

int main() {
    int n;
    cin >> n;

    // The board is initially full of zeros (unvisited squares)
    vector<vector<int>> board(n, vector<int>(n, 0));

    // Starting position: (0,0)
    board[0][0] = 1;

    // We start the backtracking algorithm
    if (tour(0, 0, 1, n, board)) {
        cout << "Solution found:\n";
        for (auto& row : board) {
            for (int cell : row)
                cout << cell << "\t";
            cout << "\n";
        }
    } else {
        cout << "No solution.\n";
    }
}
  

Explanation of the key points in the code

  • valid() checks whether the square is inside the board and has not been visited yet.
  • tour() is the heart of the algorithm:
    • it receives the current position (x, y), the number of steps and the board,
    • in every step it tries all 8 moves,
    • it recursively follows one branch as long as it is valid,
    • if it gets stuck → it goes back (backtracking),
    • when it fills n*n → success.
  • The backtracking part: If the recursion does not succeed, the move is "undone":
    board[nx][ny] = 0;
    This is the key moment – the algorithm goes one position back and tries another path.
  • In main() we only set up the board and the start, and call the function.

Why is this version important?

Although this version is not the fastest, it is the most important educational example. It clearly shows students what:

  • recursion,
  • branching of a search,
  • going back,
  • building a solution step by step

are. Such a detailed commented solution is a step towards understanding more complex heuristics (Version 2, Version 3).

Knight's Tour – Version 2 (optimized backtracking using Warnsdorff's heuristic)

Task:
Write a program that finds a path of a knight on an n × n chessboard so that the knight visits all squares exactly once (Knight's Tour). This version uses an optimized approach that significantly speeds up the execution of the algorithm.

Input: The number n (5 ≤ n ≤ 10) is read.
Output: Print the board with the number of the move with which every square was visited.

Idea of the solution – Warnsdorff's heuristic

Basic backtracking tries all possible knight jumps without any order, which leads to huge branching and slows down the algorithm for larger boards. Warnsdorff's heuristic introduces the following rule:

"In every step, choose the knight move that has the smallest number of further possible moves."

This rule makes the algorithm much more efficient and makes it possible to find a solution for larger boards much faster than pure backtracking.

Steps of the algorithm

  • Define all 8 possible knight jumps.
  • In every step, collect all valid jumps.
  • For every jump, compute its "degree" – how many continuations it has.
  • Sort the moves in ascending order of degree.
  • First try the moves that leave the fewest possibilities.

Solution in C++ (Version 2 – optimized)


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n;
vector<vector<int>> board;

int dx[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int dy[8] = { 1, 2,  2,  1, -1, -2, -2, -1 };

// Checks whether a square is valid for moving
bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < n && board[x][y] == 0;
}

// Computes the "degree" – how many continuations the knight has from this position
int degree(int x, int y) {
    int count = 0;
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (isValid(nx, ny)) count++;
    }
    return count;
}

// Optimized recursive tour
bool tour(int x, int y, int step) {
    if (step == n * n)
        return true;

    vector<pair<int, int>> moves;

    // The set of all possible moves + their degree
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (isValid(nx, ny)) {
            int s = degree(nx, ny);
            moves.push_back({s, i});
        }
    }

    // Warnsdorff: sorting by ascending degree
    sort(moves.begin(), moves.end());

    // Try in the best order
    for (auto &p : moves) {
        int i = p.second;
        int nx = x + dx[i], ny = y + dy[i];

        board[nx][ny] = step + 1;

        if (tour(nx, ny, step + 1))
            return true;

        board[nx][ny] = 0; // going back (backtracking)
    }

    return false;
}

int main() {
    cout << "Enter n (5 <= n <= 10): ";
    cin >> n;

    if (n < 5 || n > 10) {
        cout << "Allowed values are from 5 to 10." << endl;
        return 1;
    }

    board.assign(n, vector<int>(n, 0));

    // The knight starts from the top-left corner
    board[0][0] = 1;

    if (tour(0, 0, 1)) {
        for (auto &row : board) {
            for (int square : row)
                cout << square << "\t";
            cout << endl;
        }
    } else {
        cout << "No solution!" << endl;
    }

    return 0;
}
  

Explanation of the key parts

  • degree(x, y) – computes how many continuations a given move has.
  • moves – a list of valid moves together with the number of future options.
  • sort(moves.begin(), moves.end()) – first tries the hardest squares.
  • This way the algorithm drastically reduces the number of checks.

Why is version 2 much faster?

Instead of wandering through 100–1000 times more branches, Warnsdorff's approach leads the knight along the "most critical path" and makes it more likely that the tour succeeds without going back.

Results in practice

  • For n = 5 → the solution is found almost instantly.
  • For n = 8 (the classic board) → the solution is found in milliseconds.
  • Pure backtracking would take too long for n = 8 without optimizations.

Conclusion

This solution is a significant improvement of the basic backtracking approach. Warnsdorff's heuristic is simple to implement, and it gives a huge speed-up.

This version can serve as an introduction to even more advanced techniques such as iterative improvement (local search) and heuristics based on reasoning.

Knight's Tour – Version 2 (Warnsdorff's heuristic) — additional implementations

Below are two additional implementations of Version 2: Python and C#. Both solutions use Warnsdorff's rule to choose the next move.

Solution in Python (Version 2)


#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000)

dx = [2, 1, -1, -2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

def valid(x, y, n, board):
    return 0 <= x < n and 0 <= y < n and board[x][y] == 0

def degree(x, y, n, board):
    cnt = 0
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if valid(nx, ny, n, board):
            cnt += 1
    return cnt

def tour(x, y, step, n, board):
    if step == n * n:
        return True

    moves = []
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if valid(nx, ny, n, board):
            moves.append((degree(nx, ny, n, board), nx, ny))

    # sort by ascending degree (Warnsdorff)
    moves.sort(key=lambda t: t[0])

    for _, nx, ny in moves:
        board[nx][ny] = step + 1
        if tour(nx, ny, step + 1, n, board):
            return True
        board[nx][ny] = 0  # backtrack

    return False

def main():
    try:
        n = int(input("Enter n (5 <= n <= 10): ").strip())
    except:
        print("Invalid input.")
        return

    if n < 5 or n > 10:
        print("Allowed values are from 5 to 10.")
        return

    board = [[0] * n for _ in range(n)]
    board[0][0] = 1

    if tour(0, 0, 1, n, board):
        for row in board:
            print("\t".join(str(x) for x in row))
    else:
        print("No solution.")

if __name__ == "__main__":
    main()
  

Explanation (Python)

  • degree computes how many valid moves a given square has — this is the criterion for Warnsdorff.
  • In the function tour we collect all valid moves, sort them by degree and try them in that order.
  • The result is printed as a matrix of the order numbers of the tour.

Solution in C# (Version 2)


using System;
using System.Collections.Generic;

class Program {
    static int n;
    static int[,] board;
    static int[] dx = { 2, 1, -1, -2, -2, -1, 1, 2 };
    static int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 };

    static bool Valid(int x, int y) {
        return x >= 0 && x < n && y >= 0 && y < n && board[x, y] == 0;
    }

    static int Degree(int x, int y) {
        int cnt = 0;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (Valid(nx, ny)) cnt++;
        }
        return cnt;
    }

    static bool Tour(int x, int y, int step) {
        if (step == n * n) return true;

        var moves = new List<Tuple<int,int,int>>(); // (degree, nx, ny)
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (Valid(nx, ny)) {
                moves.Add(Tuple.Create(Degree(nx, ny), nx, ny));
            }
        }

        // we sort by degree (ascending)
        moves.Sort((a,b) => a.Item1.CompareTo(b.Item1));

        foreach (var m in moves) {
            int nx = m.Item2, ny = m.Item3;
            board[nx, ny] = step + 1;
            if (Tour(nx, ny, step + 1)) return true;
            board[nx, ny] = 0; // backtrack
        }

        return false;
    }

    static void Main() {
        Console.Write("Enter n (5 <= n <= 10): ");
        if (!int.TryParse(Console.ReadLine(), out n)) return;
        if (n < 5 || n > 10) {
            Console.WriteLine("Allowed values are from 5 to 10.");
            return;
        }

        board = new int[n, n];
        board[0, 0] = 1;

        if (Tour(0, 0, 1)) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    Console.Write(board[i, j] + "\t");
                }
                Console.WriteLine();
            }
        } else {
            Console.WriteLine("No solution.");
        }
    }
}
  

Explanation (C#)

  • The same logic as in the C++ and Python versions: Degree and sorting the moves by degree.
  • A list of tuples is used to sort the moves; then each move is tried in that order.

Knight's Tour – Version 3 (purely heuristic solution, without backtracking)

Unlike Version 1 (brute force) and Version 2 (backtracking + Warnsdorff), this version does not use going back (backtracking) at all.

The algorithm uses only Warnsdorff's rule: in every step it chooses the move that leads to the square with the smallest number of further valid moves.

This purely heuristic approach is very fast (complexity O(n²)) and in practice gives a solution for all boards of size n ≥ 5.

C++ implementation (Version 3)


#include <bits/stdc++.h>
using namespace std;

int dx[8] = {2,1,-1,-2,-2,-1,1,2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};

bool valid(int x, int y, int n, vector<vector<int>>& board) {
    return x >= 0 && x < n && y >= 0 && y < n && board[x][y] == 0;
}

int degree(int x, int y, int n, vector<vector<int>>& board) {
    int cnt = 0;
    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (valid(nx, ny, n, board)) cnt++;
    }
    return cnt;
}

bool warnsdorff(int n, vector<vector<int>>& board, int sx = 0, int sy = 0) {
    int x = sx, y = sy;
    board[x][y] = 1;

    for (int step = 2; step <= n*n; step++) {
        int bestDeg = 9, bestX = -1, bestY = -1;

        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (valid(nx, ny, n, board)) {
                int d = degree(nx, ny, n, board);
                if (d < bestDeg) {
                    bestDeg = d;
                    bestX = nx;
                    bestY = ny;
                }
            }
        }

        if (bestX == -1) return false; // the heuristic failed

        x = bestX;
        y = bestY;
        board[x][y] = step;
    }

    return true; // success
}

int main() {
    int n;
    cin >> n;

    vector<vector<int>> board(n, vector<int>(n, 0));

    if (warnsdorff(n, board)) {
        for (auto& r : board) {
            for (int x : r) cout << x << "\t";
            cout << "\n";
        }
    } else {
        cout << "No solution.\n";
    }
}
  

Python implementation (Version 3)


dx = [2,1,-1,-2,-2,-1,1,2]
dy = [1,2,2,1,-1,-2,-2,-1]

def valid(x, y, n, board):
    return 0 <= x < n and 0 <= y < n and board[x][y] == 0

def degree(x, y, n, board):
    cnt = 0
    for i in range(8):
        nx, ny = x + dx[i], y + dy[i]
        if valid(nx, ny, n, board):
            cnt += 1
    return cnt

def warnsdorff(n, board, sx=0, sy=0):
    x, y = sx, sy
    board[x][y] = 1

    for step in range(2, n*n + 1):
        bestDeg = 9
        best = None

        for i in range(8):
            nx, ny = x + dx[i], y + dy[i]
            if valid(nx, ny, n, board):
                d = degree(nx, ny, n, board)
                if d < bestDeg:
                    bestDeg = d
                    best = (nx, ny)

        if best is None:
            return False

        x, y = best
        board[x][y] = step

    return True

def main():
    n = int(input("Enter n (>= 5): "))
    board = [[0]*n for _ in range(n)]

    if warnsdorff(n, board):
        for row in board:
            print("\t".join(str(x) for x in row))
    else:
        print("No solution.")

if __name__ == "__main__":
    main()
  

C# implementation (Version 3)


using System;

class Program {
    static int[] dx = { 2, 1, -1, -2, -2, -1, 1, 2 };
    static int[] dy = { 1, 2, 2, 1, -1, -2, -2, -1 };

    static bool Valid(int x, int y, int n, int[,] board) {
        return x >= 0 && x < n && y >= 0 && y < n && board[x, y] == 0;
    }

    static int Degree(int x, int y, int n, int[,] board) {
        int cnt = 0;
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (Valid(nx, ny, n, board)) cnt++;
        }
        return cnt;
    }

    static bool Warnsdorff(int n, int[,] board, int sx = 0, int sy = 0) {
        int x = sx, y = sy;
        board[x, y] = 1;

        for (int step = 2; step <= n * n; step++) {
            int bestDeg = 9;
            int bestX = -1, bestY = -1;

            for (int i = 0; i < 8; i++) {
                int nx = x + dx[i], ny = y + dy[i];
                if (Valid(nx, ny, n, board)) {
                    int d = Degree(nx, ny, n, board);
                    if (d < bestDeg) {
                        bestDeg = d;
                        bestX = nx;
                        bestY = ny;
                    }
                }
            }

            if (bestX == -1)
                return false;

            x = bestX;
            y = bestY;
            board[x, y] = step;
        }

        return true;
    }

    static void Main() {
        int n = int.Parse(Console.ReadLine());
        int[,] board = new int[n, n];

        if (Warnsdorff(n, board)) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    Console.Write(board[i, j] + "\t");
                }
                Console.WriteLine();
            }
        } else {
            Console.WriteLine("No solution.");
        }
    }
}
  

Characteristics of Version 3

  • An extremely fast solution — practically O(n²).
  • No going back: every move is final.
  • It always gives a solution for n ≥ 5 (except for rare pathological combinations of the starting position, which can be avoided by rotation/symmetry).
  • Minimal code and an extremely elegant heuristic.

Note and additional resource

If you are interested in a more advanced use of the knight on a chessboard, see also the page Knight attacks – analysis and solutions .

The article explains how to use the knight to attack on the board, shows different algorithmic approaches and optimizations, including the use of unions in C++ for more efficient tracking of positions. By reading this article you can gain better insight into knight movement strategies and improve your understanding of backtracking in the context of chess.

In short, while the Knight's Tour task focuses on visiting all squares, the article Knight attacks shows how the knight can be used in attacking situations and how algorithmic approaches can be optimized for practical applications.

Sources and references

Some tasks and algorithm ideas were inspired by the following sources, but all code and explanations are original and adapted for SvetProgramiranja:

Note: all code was created specifically for SvetProgramiranja and adapted for educational use.


Previous
​|<Preparation for the national competition and SIO (SR)