  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 Beta that uses our hardness metrics and novelty to
generate initial states. Experiments show that Beta is able to generate initial
states that are harder to solve by a specialized solver than those designed by
human experts.
