Physical puzzle solving is often seen as a difficult task due to the wide range of possible configurations of puzzles, and the need to reason about multiple abstract concepts. However, we would like to show that random search, with a little help from simple heuristics and optimization methods, is capable of solving these kinds of puzzles in a sample efficient manor. We use the PHYRE (PHYsical REasoning) benchmark, a set of simple mechanics puzzles in a 2D environment, to test our methods.