title: Improving research methods for problem solving: The example of Sudoku
Creators: name: Behrens, Thea
Publisher: name: UNSPECIFIED
Year: 2024

description: Responding flexibly to new rules or constraints and finding tactics on the fly to achieve arbitrary goals are hallmarks of human intelligence. They allow us to adapt to changes in the environment and to thrive under a wide variety of conditions. Studying the solution strategies in puzzles, i.e., the interaction with novel and arbitrary constraints, is a way to study aspects of these core human abilities. This thesis improves on traditional research methods in the area of problem solving by combining qualitative approaches and quantitative modeling, utilizing a broad range of modeling paradigms: production systems, choice models, and hierarchical Bayesian modeling. The "model organisms" on which we test our methods are digit-placement puzzles, most prominently, Sudoku. Since there are several basic tactics for approaching such puzzles, we can study tactic choice and the factors that might influence it.

We present a series of experiments in which participants fill the entire puzzle freely. Concurrent think-aloud protocols enable us to gain a thorough understanding of the tactics used by participants to fill each digit. The studies demonstrate that various digit-placement puzzles are solved using similar methods, and there are two distinct ways in which participants think about the constraints: cell-based and digit-based. Moreover, participants exhibit clear preferences for specific solution tactics, while also utilizing a diverse range of tactics beyond what is required to solve the puzzles. After analyzing data from more than 200 participants, we discover that preferences for tactics change with experience.


We then conduct experiments in which we limit our participants to filling in only one digit per puzzle. This experimental design allows us to control the applicable tactics for each trial. The response times from two experiments indicate that participants can be biased towards a particular tactic by task instructions and task requirements. Based on our experimental findings, we argue that previous research often used biasing task designs and therefore underestimated participants’ flexibility and overestimated the importance of a problem’s complexity. Furthermore, our experiments demonstrate that participants are able to switch to other tactics if their first attempt does not lead to a solution. We formalize the tactics in a process model and find that the data can only be adequately fitted by including the possibility of switching.

Following up on these experiments, we present a hierarchical Bayesian model for fitting the response times. We demonstrate how to use process models to analyze response time data and obtain parameter estimates that have a clear psychological interpretation. To estimate the duration of each processing step, we assume that each step has a random duration, modeled as draws from a gamma distribution. Modern probabilistic programming tools enable the fitting of Bayesian hierarchical models to data, allowing for the estimation of the duration of a step for each individual participant. This procedure can also be applied when the step count for each trial is latent, as in our Sudoku model. Our model allows us to estimate tactic choices in the Sudoku task for each participant individually. This approach can be applied to other response time experiments where a process model exists, bridging the gap between classical cognitive modeling and statistical inference.

We also demonstrate how problem solving traces can be analyzed statistically using classical production systems. While research on problem solving traditionally relies on think-aloud protocols in single participants, other research areas usually focus on statistical analyses of overt responses pooled over many participants. To obtain sufficient data for fitting quantitative models on the individual participant level, we introduce a new experimental interface which provides enough data to disambiguate rule selections without relying on labor-intensive methods such as the analysis of think-aloud protocols. To account for the probabilistic nature of rule selection, we use standard choice models, such as the Bradley-Terry-Luce model or the elimination-by-aspects model. The model fits confirm that, as expected, spatial and temporal factors influence rule selection in Sudoku. Through clustering, we find that our participants can be divided into four groups with similar rule preferences.

In summary, we believe that a broad range of methodological approaches is necessary in order to make progress in problem solving research. Therefore, this thesis introduces and uses several experimental designs as well as analysis tools and modeling approaches to contribute to understanding how humans solve digit-placement tasks. We show that there is great potential in the combination of these methods to further improve our understanding of general problem solving.