We present a planner for underactuated hyper-redundant robots, such as humanoid robots, for which the movement can only be initiated by taking contacts with the environment. We synthesize our previous work on the subject and go further into details to give an in-depth description of the contact planning problem and the mechanisms of our contact planner. We highlight the structure of the problem with a simple example, present the contact space and the heuristics we use for planning, and explain thoroughly the implementation of the different parts of the planner. Finally we give examples of planning results for complex scenarios with the humanoid robot HRP-2.