Chapter 2 | The Knight's Tour Problem

0:00 Introduction 1:13 Directed, Reversed, Undirected Knight's Tours 1:34 Notations to Represent Knight's Tours 1:57 Open, Closed, Magic Knight's Tours 2:49 Numbers of Directed Knight's Tours 3:47 Chess Graphs 4:43 The n-Queens Problem 5:29 Independent Set of Nodes 6:34 Hamilton Path | Hamilton Cycle 7:12 Definition of an Algorithm 7:52 Decision Problem | Decision, Verification Algorithm 9:52 P | NP | NP-Hard | NP-Complete 12:17 Brute Force 14:16 Backtracking 16:03 Backtracking on a Graph | Example 1 19:20 Backtracking on a Graph | Example 2 20:34 Backtracking on a Knight's Graph | Example 3 21:13 Warnsdorff's Algorithm 22:37 The Intuitive Idea Behind Warnsdorff's Algorithm 23:47 The Power of a Heuristic 25:43 Warnsdorff's Algorithm on a Graph 27:55 Warnsdorff's Algorithm for Hamilton Paths? 29:11 Combining Approaches 31:21 Warnsdorff's Algorithm | Backtracking | Brute Force 31:43 The Chromatic Number 34:56 A Connection between Graph Theory and Linear Algebra 38:49 Warnsdorff's Algorithm Python Implementation Animations have been created with Manim and Adobe Premiere Pro. Manim: https://docs.manim.community/en/stable/ Manim Code to Visualize Warnsdorff's Algorithm: https://github.com/ccAcademycc/Warnsd... Music: ▶ Vincent Rubinetti Download the music on Bandcamp: https://vincerubinetti.bandcamp.com/a... Stream the music on Spotify: https://open.spotify.com/playlist/3zN... ▶ Introduction: Bellissimo - Doug Maxwell Sound effects: https://mixkit.co/free-sound-effects/ #graphtheory #graphs #mathematics #chess #chesspuzzle