Any problems/games/puzzles in which exhaustive search cannot show that a solution does not exist?

Question

Introduction

Exhaustive search is a method in AI planning to find a solution for so-called Constraint Satisfaction Problems. (CSP). Those are problems that 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 that generates a tree for the state space to search 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 take 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 don'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?

Original posting

Just wondering - like with an 8-queens problem. If we change it to a 9-queens problem and do an 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?

Answer 1

This should be a comment, but I don't have enough reputation to comment. I will remove this answer if question is updated

Your question is not really clear. As I understand it, the definition itself of the exhaustive search show that it's always possible to determine if a solution is valid or not.

Exhaustive search is defined as :

• For a given potential solution, can determine if this solution resolve the problem.
• Test every possible potential solution

From this, there is no problem where every potential solution is tested, but the search cannot show that a solution exist : either it exist and the search found the candidate, or it does not exist because all possible candidates were tested.

---

Maybe what you meant when asking your question is : "Any problems in which exhaustive search cannot be applied ?"

And the answer is yes, there is plenty of problems where the search space is way to big to be integrally searched : for example the Rubik's cube 3*3*3 has 43 252 003 274 489 856 000 combinations (source).

My answer need more source, specifically about the exhaustive search definition. I would be happy to add it if you could share :)

Answer 2

In addition to the problems like Rubik's cube (as described by @Astariul) which are practically too complex to solve exhaustively (due to limitations of speed and memory of our machines), there are other problems which no one has yet been able to show can be solved, like Halting Problem.

Moreover, with the advances in Quantum Machine Learning we may be able to solve problems which are yet impractical to solve with exhaustive search (like Rubik's Cube). Problems like Halting Problem are a different story.