While reading making unique combinations from the given characters on SO , I was wondering if is this the technique the programs the use Brute-Force method apply ? I mean making 92 combinations to break a userID or a password. A typical windows keyboard has some 92 characters that can be used in a password.
I am not asking how to break a password by this method but wanted to know what method do some sophisticated programs use for a Brute-Force method ?
The Naive way to solve problems using brute force is indeed a simple backtracking, which explore all possibilities, evaluates them, and chose the best.
However, for some problems - you might have more information then "It solves it" or "It doesn't solve it". For example, for the SAT problem (Finding if a boolean formula has a solution) - you can get knowledge on "how exactly did you get the contradiction" (Which variables could not be satisfied with the assignment). Usually we refer this issue as Constraint Propogation. It is applied for SAT under the DPLL algorithm which is often used (in variations) for SAT solvers.
If you are interested - real life programs that use SAT solvers are various, Software verification algorithms are one example that use SAT solvers in order to prove a software (or more commonly hardware) is working as it should.
Another common optimization is Branch and Bound - meaning, you can trim your "search tree" before you reach the leaves. An example will be for Traveling Salesman Problem. If you already found a path of length 100, and you are exploring a new one, and reached 101, no need to keep exploring this possibility.
