Exact methods will always find the global optimum and recognize it too. That being said, they don't scale (not even beyond toy problems) and are therefore mostly useless.
The Brute Force algorithm creates and evaluates every possible solution.
Notice that it creates a search tree that explodes as the problem size increases. Brute Force is mostly unusable for a real-world problem due to time limitations.
Depth-First Search is an improvement over Brute Force, as it regularly prunes away an entire subset of
solutions which cannot have a better solution than the best solution already found at that point. for example: at
index 15, it can prune away all unvisited solutions with queen A on row 0, because none will be better than the
solution of index 14 with a score of -1.
Notice that it (much like Brute Force) creates a search tree that explodes as the problem size increases. Depth-First Search is mostly unusable for a real-world NP-complete problem due to time limitations.
Technically, this Backtracking Depth-First Search with pruning is a form of Branch And Bound, although Branch and Bound is often more flexible in its pruning.