Warnsdorff’s rule, the standard shortcut for the knight’s tour, finds a tour on an 8 × 8 board from 63 of the 64 starting squares. From the 64th, row 4 and column 2, it walks into a dead end with four squares still unvisited, and nothing in the rule warns you. A program that trusts it will be right almost every time, which is exactly what makes the one failure easy to miss.
This guide explains the knight’s tour, implements Warnsdorff’s rule in modern C++, and adds the two things the original lacked: a fallback that backtracks when the rule leads into a dead end, and a checker that proves the output is a tour. Every program was compiled for this article on Ubuntu 24.04 with GCC 13.3 and Clang 18.1.3 under -std=c++17 and -std=c++20, with -Wall -Wextra -pedantic -Werror and no warnings, and run clean under AddressSanitizer and UndefinedBehaviorSanitizer. Every output block is captured verbatim, and the code is in a GitHub repository whose workflow repeats these checks, plus an MSVC build, on every commit.
What Is the Knight’s Tour?
The knight’s tour is a chess puzzle: move a knight around an empty board so that it lands on every square exactly once. A knight moves in an L shape, two squares in one direction and one square at a right angle. If the knight’s last square is one move from its first, the tour is closed; otherwise it is open.
Tours exist on every square board from 5 × 5 upward, and closed tours on every even board from 6 × 6 upward; 2 × 2, 3 × 3 and 4 × 4 have none. The standard 8 × 8 board has more than 26 trillion directed closed tours, according to the knight’s tour article on Wikipedia, so the problem is not finding one in principle but finding one quickly. Trying moves blindly takes millions of steps; a good rule takes 63.
The puzzle is old, discussed by Euler in 1759 and centuries earlier in Indian verse, and still a common programming exercise because it combines a two-dimensional board, recursion and a heuristic in one short program. Chess.com’s overview of the knight’s tour covers its history for chess players.
How Warnsdorff’s Rule Works
H. C. von Warnsdorff described the rule in 1823. It is a greedy choice made once per move:
- Place the knight on the starting square and number it 1.
- List the unvisited squares the knight can jump to next.
- For each one, count its exits: the unvisited squares a knight could jump to from there.
- Move to the square with the fewest exits, and number it.
- Repeat until every square is numbered, or until no move is possible.
The idea is to visit awkward squares, such as corners and edges, while they can still be reached, instead of leaving them stranded for later. The rule says nothing about ties, and nothing about what to do when the square with the fewest exits has none at all. Both gaps matter, as the measurements below show.
The Source Code
The search lives in a header, knights_tour.hpp. Board stores the move numbers in a single std::vector<int> indexed by row and column, the same layout as a two-dimensional array described in the guide to arrays in C and C++, but sized at run time so one program handles any board size. warnsdorff() is the rule alone, never undoing a move, and find_tour() is a depth-first search that tries moves in Warnsdorff order and backtracks when it gets stuck.
// knights_tour.hpp - knight's tours by Warnsdorff's rule, with and without
// backtracking, plus a checker. Header-only, C++17.
#ifndef KNIGHTS_TOUR_HPP
#define KNIGHTS_TOUR_HPP
#include <algorithm>
#include <array>
#include <cstdlib>
#include <vector>
namespace knight {
struct Square {
int row, col;
};
// The eight knight moves, in the order the original MYCPLUS program used.
inline constexpr std::array<Square, 8> moves = {{
{-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}}};
// An n x n board. Each cell holds 0 if unvisited, else the move number 1..n*n.
class Board {
public:
explicit Board(int n) : n_(n), cells_(static_cast<std::size_t>(n) * n, 0) {}
int size() const noexcept { return n_; }
bool inside(Square s) const noexcept
{
return s.row >= 0 && s.row < n_ && s.col >= 0 && s.col < n_;
}
int at(Square s) const { return cells_[index(s)]; }
void set(Square s, int step) { cells_[index(s)] = step; }
bool is_free(Square s) const { return inside(s) && at(s) == 0; }
// Free squares a knight on s could move to next: Warnsdorff's measure.
int exits(Square s) const
{
int count = 0;
for (const Square m : moves)
if (is_free({s.row + m.row, s.col + m.col}))
++count;
return count;
}
private:
std::size_t index(Square s) const
{
return static_cast<std::size_t>(s.row) * static_cast<std::size_t>(n_) +
static_cast<std::size_t>(s.col);
}
int n_;
std::vector<int> cells_;
};
// Pure Warnsdorff: always move to the free square with the fewest exits,
// never undo a move. Ties go to the first or last such square in move order.
// Returns the number of squares visited; n*n means a complete tour.
enum class Ties { first, last };
inline int warnsdorff(Board& b, Square start, Ties ties)
{
int step = 1;
b.set(start, step);
for (Square at = start; step < b.size() * b.size(); ++step) {
Square best{};
int best_exits = 9;
for (const Square m : moves) {
const Square next{at.row + m.row, at.col + m.col};
if (!b.is_free(next))
continue;
const int e = b.exits(next);
if (e < best_exits || (ties == Ties::last && e == best_exits)) {
best = next;
best_exits = e;
}
}
if (best_exits == 9)
break; // no free square: stuck
b.set(best, step + 1);
at = best;
}
return step;
}
// Depth-first search for a tour. With `ordered`, moves are tried in
// Warnsdorff order and dead ends are skipped; without it, in plain move order.
// Gives up after `limit` squares have been placed.
struct Search {
bool found = false;
bool gave_up = false;
long long placed = 0; // squares placed, retries included
};
namespace detail {
// Squared distance from the center, in half-squares, so it stays an integer.
// Ties in Warnsdorff's rule go to the square nearer the edge.
inline int center_distance(int n, Square s)
{
const int dr = 2 * s.row - (n - 1), dc = 2 * s.col - (n - 1);
return dr * dr + dc * dc;
}
inline bool extend(Board& b, Square at, int step, bool ordered, long long limit, Search& s)
{
const int last = b.size() * b.size();
if (step == last)
return true;
std::array<Square, 8> next{};
std::array<int, 8> exits{}, distance{};
int count = 0;
for (const Square m : moves) {
const Square sq{at.row + m.row, at.col + m.col};
if (!b.is_free(sq))
continue;
const int e = ordered ? b.exits(sq) : 0;
if (ordered && e == 0 && step + 1 != last)
continue; // a dead end before the last square
next[count] = sq;
exits[count] = e;
distance[count] = ordered ? center_distance(b.size(), sq) : 0;
++count;
}
std::array<int, 8> order{0, 1, 2, 3, 4, 5, 6, 7};
std::stable_sort(order.begin(), order.begin() + count, [&](int a, int c) {
if (exits[a] != exits[c])
return exits[a] < exits[c]; // Warnsdorff: fewest exits first
return distance[a] > distance[c]; // tie: nearer the edge first
});
for (int i = 0; i < count; ++i) {
if (s.placed >= limit) {
s.gave_up = true;
return false;
}
const Square sq = next[order[i]];
b.set(sq, step + 1);
++s.placed;
if (extend(b, sq, step + 1, ordered, limit, s))
return true;
b.set(sq, 0); // undo and try the next move
if (s.gave_up)
return false;
}
return false;
}
} // namespace detail
inline Search find_tour(Board& b, Square start, bool ordered, long long limit)
{
Search s;
b.set(start, 1);
s.placed = 1;
s.found = detail::extend(b, start, 1, ordered, limit, s);
return s;
}
// True if the board holds 1..n*n exactly once, each step a knight move.
inline bool is_tour(const Board& b)
{
const int n = b.size();
std::vector<Square> where(static_cast<std::size_t>(n) * n + 1, Square{-1, -1});
for (int r = 0; r < n; ++r)
for (int c = 0; c < n; ++c) {
const int v = b.at({r, c});
if (v < 1 || v > n * n || where[static_cast<std::size_t>(v)].row != -1)
return false;
where[static_cast<std::size_t>(v)] = {r, c};
}
for (std::size_t v = 1; v < where.size() - 1; ++v) {
const int dr = std::abs(where[v].row - where[v + 1].row);
const int dc = std::abs(where[v].col - where[v + 1].col);
if (!((dr == 1 && dc == 2) || (dr == 2 && dc == 1)))
return false;
}
return true;
}
// A tour is closed if the last square is a knight move from the first.
inline bool is_closed(const Board& b)
{
const int n = b.size();
Square first{-1, -1}, last{-1, -1};
for (int r = 0; r < n; ++r)
for (int c = 0; c < n; ++c) {
if (b.at({r, c}) == 1) first = {r, c};
if (b.at({r, c}) == n * n) last = {r, c};
}
const int dr = std::abs(first.row - last.row), dc = std::abs(first.col - last.col);
return (dr == 1 && dc == 2) || (dr == 2 && dc == 1);
}
} // namespace knight
#endiffind_tour() differs from the bare rule in three ways:
- It skips dead ends. A square with no exits can only be the last square of a tour, so it is never tried earlier.
- It breaks ties toward the edge. Among squares with equal exits, the one farther from the center goes first.
std::stable_sortkeeps the original move order for any remaining ties, so the result is the same on every compiler. - It backtracks. If every move from a square fails, it clears that square and returns, and the previous level tries its next choice. The recursion is one level per square, so at most 900 deep on the largest board it accepts.
The program reads the board size and starting square from the command line, rejects anything out of range, and prints the board:
// knights_tour.cpp - finds a knight's tour and prints the board.
// Usage: knights_tour [N [ROW COL]] N is 1 to 30, ROW and COL are 0 to N-1.
// Defaults: an 8 x 8 board, starting in the corner (0, 0).
#include <charconv>
#include <iomanip>
#include <iostream>
#include <string_view>
#include <system_error>
#include "knights_tour.hpp"
namespace {
constexpr int max_size = 30;
bool parse(std::string_view text, int low, int high, int& out)
{
int v = 0;
const auto [end, ec] = std::from_chars(text.data(), text.data() + text.size(), v);
if (ec != std::errc{} || end != text.data() + text.size() || v < low || v > high)
return false;
out = v;
return true;
}
} // namespace
int main(int argc, char** argv)
{
int n = 8;
knight::Square start{0, 0};
const bool ok = (argc == 1) ||
(argc == 2 && parse(argv[1], 1, max_size, n)) ||
(argc == 4 && parse(argv[1], 1, max_size, n) &&
parse(argv[2], 0, n - 1, start.row) && parse(argv[3], 0, n - 1, start.col));
if (!ok) {
std::cerr << "usage: knights_tour [N [ROW COL]] (N is 1 to " << max_size
<< ", ROW and COL are 0 to N-1)\n";
return 2;
}
std::cout << "Knight's tour, " << n << " x " << n << " board, starting at (" << start.row
<< ", " << start.col << "):\n";
// On an odd board a tour alternates colors and has one more square of
// the corner color, so it must start on a square of that color.
if (n % 2 == 1 && (start.row + start.col) % 2 == 1) {
std::cout << "No tour starts here: on an odd board it must start on a square "
"the color of the corners.\n";
return 1;
}
knight::Board board(n);
const knight::Search s = knight::find_tour(board, start, true, 100'000'000);
if (!s.found) {
std::cout << (s.gave_up ? "Gave up" : "No tour exists") << " (searched "
<< s.placed << " placements).\n";
return 1;
}
const int width = n * n >= 100 ? 4 : 3;
for (int r = 0; r < n; ++r) {
for (int c = 0; c < n; ++c)
std::cout << std::setw(width) << board.at({r, c});
std::cout << '\n';
}
std::cout << (knight::is_closed(board) ? "Closed" : "Open") << " tour: " << n * n - 1
<< " moves, " << s.placed - n * n << " backtracked.\n";
return knight::is_tour(board) ? 0 : 3;
}Build and Run
g++ -std=c++17 -Wall -Wextra -pedantic -O2 -Iinclude src/knights_tour.cpp -o knights_tour
./knights_tourWith no arguments it solves the standard board from the corner:
Knight's tour, 8 x 8 board, starting at (0, 0):
1 34 3 18 37 32 13 16
4 19 36 33 14 17 38 31
35 2 49 52 47 40 15 12
20 5 64 41 50 53 30 39
57 42 51 48 59 46 11 26
6 21 58 63 54 27 60 29
43 56 23 8 45 62 25 10
22 7 44 55 24 9 28 61
Open tour: 63 moves, 0 backtracked.
Every square holds the move number that reached it, so following 1, 2, 3 … 64 traces the tour. “0 backtracked” means Warnsdorff order found it without undoing a single move. The same program solves a 5 × 5 board with ./knights_tour 5:
Knight's tour, 5 x 5 board, starting at (0, 0):
1 10 21 16 7
20 15 8 11 22
9 2 25 6 17
14 19 4 23 12
3 24 13 18 5
Open tour: 24 moves, 0 backtracked.
Bad input is rejected rather than used. The original program read the starting square with cin and wrote to board[row][col] without checking, so entering 8 8 wrote outside the array; UndefinedBehaviorSanitizer reported index 8 out of bounds for type 'int [8][8]'. Here std::from_chars parses each argument, and anything that is not a whole number in range ends the program with a usage message and exit status 2:
$ ./knights_tour 9 9 9
usage: knights_tour [N [ROW COL]] (N is 1 to 30, ROW and COL are 0 to N-1)Where Warnsdorff’s Rule Fails
tour_stats runs the rule from every possible starting square on boards from 5 × 5 to 12 × 12, first on its own with the original program’s tie rule, then inside find_tour():
Board Starts Warnsdorff alone With backtracking Most squares placed
5x5 13 12 13 25
6x6 36 35 36 36
7x7 25 18 25 982160
8x8 64 63 64 64
9x9 41 41 41 81
10x10 100 98 100 100
11x11 61 61 61 136
12x12 144 138 144 144
Warnsdorff alone on 8x8 from (4, 2): stuck after 60 of 64 squaresThe rule alone fails somewhere on six of the eight board sizes. On 7 × 7 it fails from 7 of 25 starts, and on 8 × 8 from exactly one: (4, 2), the square where the original program went wrong. With backtracking every start succeeds, usually without undoing a single move; the “Most squares placed” column equals the number of squares wherever no move was ever undone. The exception is 7 × 7, where one start needs 982,160 placements, still well under a second.
The figure shows the failure. After move 59, the knight can go to a square with two exits or a square with none. Fewest exits wins, and a square with no exits is a dead end with four squares still unvisited. Skipping squares with no exits, unless they are the last square, prevents this particular trap; backtracking handles the rest.
Changing the tie rule changes which starts fail, not whether any do. Sending ties to the first candidate instead of the last fails from the same number of starts on every board from 5 × 5 to 12 × 12, but mostly from different squares: on 8 × 8 it fails from (3, 2) instead of (4, 2). So find_tour() treats Warnsdorff’s rule as a move order to try first, never as a guarantee.
What the Original Program Did When It Got Stuck
A dead end is easy to handle badly. A move function that looks up “the first legal move” in an array can find leftover entries from an earlier step when the current square has none, jump the knight back onto a visited square, and overwrite an earlier move number. The printed board then looks complete apart from one 0, and the program exits normally. AddressSanitizer does not help either, because every read stays inside the arrays: the program is wrong without ever being unsafe. warnsdorff() instead stops and returns how many squares it placed, 60 from (4, 2), and is_tour() rejects any board with a missing or repeated number. The test suite keeps such a broken board and checks that is_tour() rejects it.
Why Plain Backtracking Is Not Enough
Backtracking alone, trying moves in a fixed order with no heuristic, does find a tour, eventually. The last lines of tour_stats count the squares placed before the first tour from the corner:
Backtracking from the corner, squares placed before the first tour:
5x5: 14009 in plain move order, 25 in Warnsdorff order
6x6: 58692 in plain move order, 36 in Warnsdorff order
7x7: 18818 in plain move order, 49 in Warnsdorff order
8x8: 27241113 in plain move order, 64 in Warnsdorff orderOn 8 × 8, plain backtracking places and removes squares more than 27 million times; Warnsdorff order needs 64, one per square. The plain count also jumps around with board size (7 × 7 is faster than 6 × 6) because it depends on how soon the fixed move order happens to stumble onto a tour. The work of exhaustive search grows exponentially, the same reason brute force fails on problems like the knapsack problem; a heuristic does not change that worst case, but it makes the first branch tried almost always the right one.
Odd Boards and the Color Rule
On an odd board, some starting squares can never begin a tour. A knight always moves to a square of the other color, so a tour alternates colors. An odd board such as 5 × 5 has one more square of the corners’ color than of the other, 13 against 12, so a tour of all 25 must start and end on the corners’ color. The program checks this before searching:
$ ./knights_tour 5 0 1
Knight's tour, 5 x 5 board, starting at (0, 1):
No tour starts here: on an odd board it must start on a square the color of the corners.The test suite confirms the rule by exhaustive search on 5 × 5, where all 12 squares of the other color have no tour. On 7 × 7 the same exhaustive search runs past 100 million placements without finishing, which is why the program uses the argument rather than the search. For boards with no tour at all, the search ends quickly: ./knights_tour 4 reports that no tour exists after trying 1,463 placements.
Checking That a Tour Is Valid
is_tour() is short and the most useful function in the header. It checks that the board holds each number from 1 to n² exactly once and that every consecutive pair is a knight move apart, so it catches skipped squares, repeated squares and illegal jumps. is_closed() then checks whether the last square is a knight move from the first.
Running both on the original program’s sample board shows something its page never mentioned: the tour from (1, 1) is closed. Move 64 lands at row 2, column 3, one knight move from the start, so the knight could repeat the whole tour from any square on it. That was luck, not design; Warnsdorff’s rule does not aim for closed tours, and the knights_tour 8 1 1 output in this version, which breaks ties differently, is open.
Key Takeaways
- Warnsdorff’s rule is a heuristic, not an algorithm. Move to the square with the fewest onward exits, and you will usually finish, but not always: alone it failed from 7 of 25 starts on 7 × 7 and from one of 64 on 8 × 8.
- Never move into a square with no exits unless it is the last one; that is the dead end the bare rule walks into from (4, 2).
- Use the rule as a move order inside backtracking. Every start on every board from 5 × 5 to 30 × 30 then succeeds; only 58 of those 7,189 starts needed to undo any move.
- Plain backtracking is correct but slow: 27,241,113 placements on 8 × 8 against 64 in Warnsdorff order.
- On odd boards, only squares the color of the corners can start a tour.
- Check the output. A short
is_tour()function catches a skipped or repeated square at once, so a broken board never gets printed as a tour.
Frequently Asked Questions
Conclusion
The knight’s tour is a small problem with a large lesson: a heuristic that works nearly every time is the most dangerous kind, because nobody tests the case where it does not. One bad starting square in 64 is easy to miss when every board looks alike.
Warnsdorff’s rule is still the right starting point. Used as a move order, with dead ends skipped, backtracking as a safety net and a checker on the result, it finds tours on boards up to 30 × 30 in milliseconds and says so when no tour exists. More searches, sorts and puzzles are in the algorithms section.
Source Code and Tests
All programs on this page are in the recursion/knights-tour directory of the MYCPLUS C++ examples repository.
Build and test:
cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failureWhat the build checks. It compiles with GCC and Clang under C++17 and C++20 on Linux and with MSVC on Windows, warnings as errors, and checks that knights_tour and tour_stats print exactly the output on this page. The unit tests check that is_tour() accepts the original program’s sample board and rejects its broken one, that the bare rule reproduces the original’s sample exactly and gets stuck from (4, 2), that find_tour() finds a valid tour from every possible start on boards 5 × 5 to 10 × 10, and that it proves no tour exists on 2 × 2 to 4 × 4 and from the wrong-colored squares of 5 × 5. Bad arguments must be rejected. A sanitizer build runs everything under AddressSanitizer and UndefinedBehaviorSanitizer. The 13 × 13 to 30 × 30 results quoted above were run once for this article and are not part of the build.
