In this paper, a new benchmark, for testing the capability of Evolutionary Algorithms to generate maze solving Exploration Strategies is introduced. This benchmark solves three problems commonly found in other benchmarks: small maze set, all mazes belonging to the same kind of maze, and biased methods for choosing starting locations. In this benchmark, the Connectivity Based Maze Generation Algorithm is proposed for building maze sets. Mazes generated using this algorithm exhibit a property called connectivity that indicates how much the walls are connected among them. Connectivity can be used to control the diversity of the sets. Additionally, a new method for choosing starting locations, that takes into account the maze goal positions, is presented. Using the Connectivity Based Maze Generation Algorithm and the new method for choosing starting locations, two problems that test the capability of an Evolutionary Algorithm for solving mazes with similar and different connectivity are built. Example datasets are generated and experiments are performed to validate the proposed benchmark.