The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely makes sense to consider how you traverse the search space. In general, you will find a lot of literature and discussion on the topic from the field of AI, and in particular e.g. SAT/CSP solving. A quick and gentle introduction is given by the Russell and Norving book.

I like using the Sudoku puzzle as an example. To decide whether a partially filled puzzle has a solution, you can exhaustively check every possible way of completing it. The naive approach is a blind backtracking search. This is extremely wasteful. A better idea is this: for the next cell to assign to, always pick the one with the fewest legal values. In general, this is a "fail-first heuristic", and the intuition is that this choice is most likely to fail soon, and it thereby prunes the search tree aggressively. There is actually a known "wisdom" in the field: "to succeed, you must fail quickly". Roughly, the sooner you fail, the faster you get to concentrate your effort on the hard part of the problem.

It might seem like the above is very problem specific, and only applies to say Sudoku puzzles. Fortunately, this is not the case. It is quite helpful to model your problem, or try to you see your problem, as e.g. a SAT/CSP instance. Then you can immediately apply known tricks to speedup your brute-force, devise better heuristics, and so on. Of course, you might do several magnitudes better by using a good CSP/SAT-solver instead of brute-force. This is beneficial even if nothing considerably better than brute-force is known for your problem. This is due to the fact that instances tend to have structure that is exploitable by smart solvers, and it is difficult to detect the same structure yourself with e.g. brute force.

An older answer of mine gives a bit more concreteness. I think every strategy you mention has been experimented with, most notably randomness. For instance, random restart strategies are very powerful, and are in use in modern solvers.

The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely makes sense to consider how you traverse the search space. In general, you will find a lot of literature and discussion on the topic from the field of AI, and in particular e.g. SAT/CSP solving. A quick and gentle introduction is given by the Russell and Norving book.

I like using the Sudoku puzzle as an example. To decide whether a partially filled puzzle has a solution, you can exhaustively check every possible way of completing it. The naive approach is a blind backtracking search. This is extremely wasteful. A better idea is this: for the next cell to assign to, always pick the one with the fewest legal values. In general, this is a "fail-first heuristic", and the intuition is that this choice is most likely to fail soon, and it thereby prunes the search tree aggressively. There is actually a known "wisdom" in the field: "to succeed, you must fail quickly". Roughly, the sooner you fail, the faster you get to concentrate your effort on the hard part of the problem.

It might seem like the above is very problem specific, and only applies to say Sudoku puzzles. Fortunately, this is not the case. It is quite helpful to model your problem, or try to you see your problem, as e.g. a SAT/CSP instance. Then you can immediately apply known tricks to speedup your brute-force, devise better heuristics, and so on. Of course, you might do several magnitudes better by using a good CSP/SAT-solver instead of brute-force. This is beneficial even if nothing considerably better than brute-force is known for your problem. This is due to the fact that instances tend to have structure that is exploitable by smart solvers, and it is difficult to detect the same structure yourself with e.g. brute force.

An older answer of mine gives a bit more concreteness. I think every strategy you mention has been experimented with, most notably randomness. For instance, random restart strategies are very powerful, and are in use in modern solvers.

The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely makes sense to consider how you traverse the search space. In general, you will find a lot of literature and discussion on the topic from the field of AI, and in particular e.g. SAT/CSP solving. A quick and gentle introduction is given by the Russell and Norving book.

I like using the Sudoku puzzle as an example. To decide whether a partially filled puzzle has a solution, you can exhaustively check every possible way of completing it. The naive approach is a blind backtracking search. This is extremely wasteful. A better idea is this: for the next cell to assign to, always pick the one with the fewest legal values. In general, this is a "fail-first heuristic", and the intuition is that this choice is most likely to fail soon, and it thereby prunes the search tree aggressively. There is actually a known "wisdom" in the field: "to succeed, you must fail quickly". Roughly, the sooner you fail, the faster you get to concentrate your effort on the hard part of the problem.

It might seem like the above is very problem specific, and only applies to say Sudoku puzzles. Fortunately, this is not the case. It is quite helpful to model your problem, or try to you see your problem, as e.g. a SAT/CSP instance. Then you can immediately apply known tricks to speedup your brute-force, devise better heuristics, and so on. Of course, you might do several magnitudes better by using a good CSP/SAT-solver instead of brute-force. This is beneficial even if nothing considerably better than brute-force is known for your problem. This is due to the fact that instances tend to have structure that is exploitable by smart solvers, and it is difficult to detect the same structure yourself with e.g. brute force.

The answer to both of your questions is yes! Definitely, even though in the worst-case you will have to enumerate the whole search space with brute-force (to prove there is no solution), it absolutely makes sense to consider how you traverse the search space. In general, you will find a lot of literature and discussion on the topic from the field of AI, and in particular e.g. SAT/CSP solving. A quick and gentle introduction is given by the Russell and Norving book.

I like using the Sudoku puzzle as an example. To decide whether a partially filled puzzle has a solution, you can exhaustively check every possible way of completing it. The naive approach is a blind backtracking search. This is extremely wasteful. A better idea is this: for the next cell to assign to, always pick the one with the fewest legal values. In general, this is a "fail-first heuristic", and the intuition is that this choice is most likely to fail soon, and it thereby prunes the search tree aggressively. There is actually a known "wisdom" in the field: "to succeed, you must fail quickly". Roughly, the sooner you fail, the faster you get to concentrate your effort on the hard part of the problem.

It might seem like the above is very problem specific, and only applies to say Sudoku puzzles. Fortunately, this is not the case. It is quite helpful to model your problem, or try to you see your problem, as e.g. a SAT/CSP instance. Then you can immediately apply known tricks to speedup your brute-force, devise better heuristics, and so on. Of course, you might do several magnitudes better by using a good CSP/SAT-solver instead of brute-force. This is beneficial even if nothing considerably better than brute-force is known for your problem. This is due to the fact that instances tend to have structure that is exploitable by smart solvers, and it is difficult to detect the same structure yourself with e.g. brute force.

An older answer of mine gives a bit more concreteness. I think every strategy you mention has been experimented with, most notably randomness. For instance, random restart strategies are very powerful, and are in use in modern solvers.