This paper investigates the efficacy of the Neuro-Evolution of Augmenting Topologies (NEAT) algorithm on PSPACE-complete problems, specifically utilizing the Sokoban puzzle. NEAT, which evolves both neural network topologies and weights, provides a promising approach for solving complex problems without predefined network architectures. We implemented NEAT using the neat-python library and tested it against several reinforcement learning (RL) algorithms, including Deep Q-Network (DQN) and Proximal Policy Optimization (PPO), within the OpenAI gym-sokoban environment. Our experiments involved extensive configuration variations to identify optimal settings for NEAT. Key findings indicate that NEAT solved the Sokoban problem, outperforming traditional RL variants. Our results highlight the importance of incremental structural growth and the protection of topological innovations. This study confirms NEAT’s applicability to PSPACE-complete problems.