Abstract Procedural generation of initial states of state-space search problems have applications in human and machine learning as well as in the evaluation of planning systems. In this paper we deal with the task of generating hard and solvable initial states of Sokoban puzzles. We propose hardness metrics based on pattern database heuristics and the use of novelty to improve the exploration of search methods in the task of generating initial states. We then present a system called ? that uses our hardness metrics and novelty to generate initial states. Experiments show that ? is able to generate initial states that are harder to solve by a specialized solver than those designed by human experts