The goal is to place $N$ queens on an $N \times N$ chessboard such that no two queens attack each other. Constraints: No two queens can share the same row, same column, or same diagonal.

We place queens column by column (or row by row). We place Queen 1 in Row 1, Col 1. Then we move to Row 2 and try to place Queen 2. If a placement is attacked, we prune that branch and backtrack to try the next column.

1Algorithm NQueens(k, n):
2// k is current queen, n is total queens
3   For i = 1 to n do:
4      If Place(k, i) is True:
5         x[k] = i // Place queen k at column i
6         If k == n:
7            Print Solution(x)
8         Else:
9            NQueens(k+1, n) // Recurse for next queen

Given a graph $G = (V, E)$ and $m$ colors, assign a color to every vertex such that no two adjacent vertices (connected by an edge) share the same color. If no such coloring exists, return false.

We assign colors to vertices one by one (e.g., Vertex A, then B, then C). For each vertex, we try Color 1. If it doesn't conflict with its neighbors, we move to the next vertex. If we run out of valid colors for a vertex, we backtrack to the previous vertex and change its color.

Because we have $m$ choices of colors for $n$ vertices, the state space tree has $m^n$ leaves. The worst-case time complexity is $O(m^n)$.

A Hamiltonian Cycle is a closed loop in a graph that visits every single vertex exactly once and returns to the starting vertex. Given an adjacency matrix, we must find this cycle using backtracking.

Starting from an arbitrary node (e.g., Vertex A), we explore adjacent vertices. If we pick Vertex B, we add it to our path array. From B, we pick an unvisited neighbor. If we hit a dead end (a vertex with no unvisited neighbors) before visiting all vertices, we backtrack and try a different neighbor.

Let's say the current path is A $\to$ B $\to$ C. To check if D is a valid next step, we must verify two conditions:

1. Matrix[C][D] == 1 (An edge exists between the current vertex and D).
2. D is not already in the path array.

When the path array contains all $V$ vertices, we do one final check: Matrix[Last_Vertex][Start_Vertex] == 1. If an edge connects the last visited node back to the start, a Hamiltonian Cycle is found! If not, we backtrack.

The backtracking approach explores a massive permutation tree. The worst-case time complexity is $O(V!)$ where $V$ is the number of vertices, though pruning impossible edges makes it practically faster than brute force.

The Traveling Salesperson Problem requires a salesperson to visit every city exactly once and return to the starting city, minimizing the total distance. Since we want the absolute minimum distance, we use Branch & Bound.

To prune branches, we must calculate a 'Lower Bound' for the starting node. We do this by reducing the distance matrix:

1. Row Reduction: Find the minimum value in each row and subtract it from all elements in that row. Add these minimums to the bound.
2. Column Reduction: Find the minimum value in each column of the new matrix and subtract it. Add these to the bound. The sum of all subtracted values is the initial Lower Bound cost.

From City A, we can travel to B, C, or D. For each path (e.g., A $\to$ B), we calculate a new cost: Cost(Node) = Parent_Cost + Matrix[A][B] + Reduction_Cost_of_New_Matrix. To create the new matrix for path A $\to$ B, we set row A to $\infty$, column B to $\infty$, and Matrix[B][A] to $\infty$ (preventing immediate return). Then we reduce the matrix again.

We maintain an 'Upper Bound' (the best complete tour found so far). If we calculate a partial path's lower bound (e.g., Path A $\to$ C $\to$ D) and its cost is higher than our Upper Bound, we prune it. We mathematically guarantee that this path can never yield a better solution, saving massive amounts of computation time.