I am aware both
-my question formulation might be ambiguous -the conversion of my question based on the xy-problem might not logical/inconsistent.
Nevertheless here is my attempt:
Do problems with a solution, that are proven to be unsolvable by any logic(/mathematics), exist?
With unsolvable I mean that there is no procedure that guarantees a solution.
Perhaps the question boils down to, "is testing all random potential solutions/options" a logical way of solving the problem?"
Because, my XY-problem was simplified: Suppose we only look from what logic allows us to develop to solve certain problems we might conclude we cannot solve/escape a problem within that framework, even though there might be a random solution that does satisfy the problem.
(E.g. a 2D maze (with internal the problem, external the solution), where logic doesn't allow left hand turns (or an exit), whereas from an external point of view can fold the 2d maze in 3d to bring a solution to the problem.
I apologize if I am not sufficiently correct in formal notation. Kind regards.
It sounds like what you're groping your way towards here is computability theory, a richly developed area on the boundary between mathematics and computer science.
Its fundamental result is: Yes, there are known well-defined problem types that are unsolvable in a very strong sense.
What "unsolvable" here means it that
(Here, "procedure" may sound fuzzy, but it is another main result of computability theory that this concept can be formalized and that all halfway resonable attempts to formalize it turn out to be equivalent. This is Church's thesis).
This is a strong kind of unsolvability, because it says that not only can't we always prove that such-and-such is the correct answer; there is not even a crazy procedure that always happens to give the right answer even though we can't prove that it always does.
The most famous such undecidable problem is the halting problem, which is quite technical to define, and there are many known similar problems that concern idealized computing machines or formal logic.
Examples of some more approachable undecidable problems are
Input: A starting configuration for the Game of Life and a designated cell.
Question: Will this cell ever turn on?
Post's correspondence problem.
Hilbert's tenth problem.
Input: A polynomial equation in several variables with integer coefficients.
Question: Does it have a solution in the integers?
These problems have the common theme that there are infinitely many cases we may need to check before we can be sure of the answer, so simply checking all cases is not a solution procedure.
You also mention problems where you can in principle solve them by checking all cases, because there are finitely many of them -- though the number of cases may be astronomically vast. The question then arises whether there is a smarter solution than checking all cases. This leads into the neighboring area of computational complexity. It turns out that even though we have a fairly good idea of how to formalize that question, the answer is disappointingly often "nobody knows". There is a group of problem types -- the NP-complete problems -- where it is strongly suspected that there is no procedure that completes significantly faster than checking all cases, but nobody has been able to prove this. That is the famous P=NP question.