Knight’s Tour in C++: Warnsdorff’s Rule, Backtracking and a Tour Checker
A tested C++17 knight’s tour: Warnsdorff’s rule, backtracking for the cases it misses, and a checker that would have caught the old program’s bug.
Algorithms are the foundation of all software — the precise, step-by-step instructions that tell a computer how to solve a problem efficiently. Understanding algorithms is not just an academic exercise. It is what separates programmers who write code that works from engineers who write code that works fast, scales under load and handles complex problems elegantly. From sorting a list of names to finding the shortest path across a network, algorithms determine how well your software performs in the real world.
MYCPLUS has been publishing algorithm tutorials and implementation guides since 2004, with a particular focus on practical algorithm implementations in C and C++. This section covers the essential algorithms every programmer should understand — sorting, searching, graph traversal, tree operations and optimisation techniques — alongside the data structures those algorithms are built on, each explained and implemented in code you can compile and study.
Each tutorial explains how the algorithm works, analyses its time and space complexity, and includes working source code you can compile and study. The refreshed tutorials go further: the code is compiled and run for the article, its output is shown as captured, and the source and tests are on GitHub. Whether you are preparing for technical interviews, studying computer science fundamentals or optimising production code — start here.
Why MYCPLUS: Trusted by programmers and computer science students since 2004 — the algorithm tutorials pair each explanation with complexity analysis and source code, and the refreshed ones are compiled, run and tested for the article.
A tested C++17 knight’s tour: Warnsdorff’s rule, backtracking for the cases it misses, and a checker that would have caught the old program’s bug.
Why the puzzle takes 2ⁿ − 1 moves, a timed 30-disk run, five tested implementations, and an iterative solver that computes any move directly.
On 5,000 sorted values a last-element pivot makes 12.5 million comparisons instead of 67,000. Quicksort, measured — with code in five languages.
Shell Sort improves insertion sort by sorting far-apart elements first. See how it works, why gap sequences matter, and tested code in five languages.
Merge sort is stable and O(n log n) on every input. Code in five languages, measured comparisons and allocations, and four mistakes that compile.
Insertion sort moves one element per out-of-order pair. A traced example, code in five languages, and measurements that show what that costs.
Bubble sort explained with a pass table, clean C and C++ code, measured comparison counts, and when qsort or std::sort is the better choice.
Selection sort always makes n(n − 1)/2 comparisons and at most n − 1 swaps. Code in five languages, measured counts, and three mistakes that sort.
Heap sort is O(n log n) in place on every input. How the heap lives in an array, code in five languages, and what the guarantee costs against quicksort.
Complexity, stability and measured comparison counts for seven sorting algorithms, plus qsort, std::sort and std::stable_sort on the same data.
0/1 knapsack in C and C++: the DP recurrence, item recovery, why greedy and an upward loop give wrong answers, and the fractional variant, all tested.
A square-root primality test, the Sieve of Eratosthenes and Miller–Rabin in seven languages, with the four bugs that pass a quick test.