Differences between backtracking and brute-force search

Question

I'm currently taking a course in algorithms, and I'm having some difficulty understanding the exact definitions of brute-force search and backtracking. As I understand it, the following is true:

• Brute-force search (BFS) is a type of algorithm which computes every possible solution to a problem and then selects one that fulfills the requirements.

• Explicit constraints give the possible values for each choice (e.g., choices 1-3 are limited to {1, 2}, choice 4 is limited to {3, 4, 5}, etc.), which determines how the search's "execution tree" is shaped.

• Implicit constraints relate the different choices to each other (e.g., choice 2 must be greater than choice 1, etc.), which is used in BFS to remove potential solutions.

• Backtracking is an extension to BFS in which the implicit constraints are evaluated after every choice (as opposed to after all solutions have been generated), which means that potential solutions can be discarded before they have been 'finished'.

Basically, all I'm wondering is whether this is accurate or not, and, if it isn't, I'd really appreciate some clarification. Thanks in advance.

Answer 1

Brute force search

Backtracking

Brute force search only takes the explicit constraints into account which means it assigns all possible values from Si to a variable xi and this for all variables. After it has constructed such a configuration, it verifies that all implicit constraints are satisfied.

Backtracking aims to optimize this process. From the moment that all variables over which an implicit constraint is defined are assigned, it verifies that constraint. If the constraint fails, then it immediately assigns a different value to the variables. The advantage is that if for instance brute force has assigned 2 to x1=2 and 5 to x2=5, and the implicit constraint x1 > x2 fails, then it will not assign values to x3,x4,... only to find out that for all configurations for these values it fails.