First, I have to say that this seems like a pretty small space for a solution: are you sure that brute force is not the easiest way to move forward?
Secondly, you want to say that you need a “pretty good” result at some constant time, or what do you need for the algorithm to be O (1)? I will not say that this is impossible, but ... well, I am almost sure that it is impossible.
In particular, the main difference between GA and SA is that SA is essentially a hill climbing algorithm that searches “out” from the last point of the solution space, while GAs are probabilistic and look for hyperplanes in the solution space,
You are saying two things that make me think that SA is better suited to your problem: iterative construction and impossible states. Because GAs recombine “pretty good” solutions on hyperplanes in the solution space, they tend to “re-discover” dead zones in the solution space. If you are sure that the best solution can be iteratively built from a fairly good solution, you are in a hilly area and SA can fit better.
To be very general, the relative advantage of GA is that they quickly process very large volumes of decision space, but they rely on the fact that there are brief “good ideas” in this decision space. The relative advantage of SA is that it seeks a local decision space “around” its original solution, which tends to efficiently find local improvements. The disadvantage is that SA is sown randomly and therefore ineffective in exploring large decision spaces.