Exhaustive search is a method in AI planning to find a solution for so called Constraint Satisfaction Problems. (CSP). That are problems which have some conditions to fulfill and the solver is trying out all the alternatives. An example CSP problem is the 8-queens problem which has geometrical constraints. The standard method in finding a solution for the 8-queens problem is a backtracking solver. That is an algorithm which generates a tree for the state space to search inside inside the graph.
Apart from practical applications of backtracking search there are some logic-oriented discussions available which are asking on a formal level which kind of problems have a solution and which not. For example to find a solution for the 8-queen problem many millions of iterations of the algorithm are needed. The question is now: which problems are too complex to find a solution. The second problem is, that sometimes the problem itself has no solution, even the complete state space was searched fully.
Let us make an example. At first we construct a problem in which the constraints are so strict that even a backtracking search won't find a solution. One example would be to prove that “1+1=3” another example would be to find a chess sequence, if the game is lost or it is also funny to think about how to arrange nine! queen on a chess table so that they doesn't hurt.
Is there any literature available which is describing Constraint Satisfaction Problems on a theoretical basis in which the constraints of the problem are too strict?
Just wondering - like with a 8-queens problem. If we change it to a 9-queens problem and do a exhaustive search, we will see that there is no solution. Is there a problem in which the search fails to show that a solution does not exist?