Hard combinatorial optimisation problems deal with the search for the ground state of discrete systems under strong frustration such as spin glasses. A transformation of state variables may enhance computational tractability. It has been argued that these state encodings are to be chosen invertible to retain the original size of the state space. Here we show how redundant non-invertible encodings enhance optimisation by enriching the density of low-energy states. In addition, smooth landscapes may be established on encoded state spaces to guide local search dynamics towards the ground state [e-print arXiv:1104.5024].