Problem solving is a critical skill for life and academic success. The identification of problem solving skills early in life requires appropriate assessment tools. However, to date well-structured problem solving tasks that children can both engage with and enjoy are lacking. This study reports on the evaluation of one such task (eFun Castle Adventure) developed as part of a research project that investigated related cognitive constructs (executive functions), a traditional problem solving task (Tower of Hanoi), and academic outcomes. A sample of 260 students aged 6-9 from three primary schools was tested on two problem solving tasks and three executive functions tasks (working memory, inhibition, and cognitive flexibility). Additionally, enjoyment rating with the problem solving tasks and grades were examined. The results showed that students enjoyed playing the new problem solving task more than the traditional task. Furthermore, we found moderate associations between the two problem solving tasks, low intercorrelations with executive function tasks, and low to medium correlations between executive functions and problem solving. Executive functions are related to and predict academic outcomes, whereas the relationship between well-structured problem solving and academic outcomes is less clear and needs further research. The new eFun problem solving and executive function tasks were found to be promising new measures to assess cognitive functions in an easy, accessible, and secure way in the classroom.