# Schoelles, Gray, & Neth (2008) Schoelles, M. J., Gray, W. D., & Neth, H. (2008). The Sudoku model: A dynamic decision maker. Paper presented at the 13th Annual ACT-R Workshop.

The Sudoku model: A dynamic decision maker

Routine Behavior and Decision Making

While decision-making is often thought to be a product of high-level cognition, we contend that routine interactive behavior at the 300–1000 ms time scale can affect human decisions made at longer time scales. The ACT-R 6.0 Sudoku model is being developed to explore how resource allocation strategies (Gray et al., 2006) used in routine interactive behavior influence decision-making strategies. The model is being developed in conjunction with a series of empirical studies.

Sudoku is a 9-row by 9-column matrix subdivided into 9 3-row by 3-column matrices (called boxes). Each row, column and box must be filled with numbers 1 through 9 with each number appearing only once in each row, column, and box. The puzzle starts out with some of the cells filled in and the solver must fill in the rest. Sudoku is well-suited to study the impact of interactive behavior on decision making, since it requires many decisions based on the interactions of human memory and vision. It is a popular game so the training time is minimal, and it is repetitive. The repetitive nature is important for electroencephalography (EEG) data collection which we will do in future studies. Another advantage of Sudoku is that the level of difficulty of different games can be determined.

Sudoku has been well studied in the Artificial Intelligence (AI) community as a constraint satisfaction problem or logic problem (Simonis 2005). The solutions methods studied include the constraint of difference method, integer programming and graph theory (Suchard et al., 2006; Chlond, 2005). Little attention has been given to the study of the psychology of Sudoku, except for Lee et al. (2006). They report three experiments to determine what types of deductions people use to solve certain Sudoku configurations.

Empirical Studies

We are conducting a series of studies. In the first study, participants played a total of eight games each. The first three were practice games, the next three were games where the difficulty was manipulated and the last two were normal games. The difficulty manipulation was covering up 0, 6 or 8 boxes. This manipulation added a motor component plus increased the amount of interaction between memory and vision. All the games in this study were rated as easy, which means that the game can be solved through constraint satisfaction without any search. We have also written an AI program to solve any Soduku puzzle and verified that these games require only propagation of constraints. This program can determine the level of difficulty of any Sudoku game in terms of the number of constraints propagated and the amount of search required.

The Model

The Sudoku model shows how the difficulty manipulation of the first empirical study influences the decision-making strategy. The current status of the model is that the first version of the model has been written and is being tested on different games. The current model can solve very easy and easy puzzles but the testing has been on only 1 very easy and 1 easy puzzle. The time the model takes is longer than humans but the model can make errors. The current model has been developed only for the manipulation where 0 boxes are covered.

To describe the operation of the model, the term unit will be used to refer to a row, column, or box. The current model scans the puzzle looking for a unit with 4 or fewer empty cells. For each empty cell in the unit it determines what are the possible values and encodes them. To determine a value the model scans the row, column and box for every possible value. If a value is not encountered it can encode it as a possible value. If the model has exhausted all possible values and recalls only one possible value then it will enter the recalled value into the cell. The model uses simple heuristics, for example, if there is only 1 possible value then only the unit needs to be scanned to determine the value. The current model always looks at a cell to determine its value if one exists. A change that we are currently implementing to interact more with memory by trying to recall a cell’s value instead of looking at it.

The next steps in the model development will be to improve the match of model performance to human performance in terms of time and error rates and to solve the puzzle when 6 or 8 boxes are covered. Since the task is very visual, the number of eye movements and time to move visual attention are crucial to model performance. Analysis of eye data collected during the empirical study will be used to improve the design of the model.

References

Gray, W. D., Sims, C. R., Fu, W. T., & Schoelles, M. J. (2006). The soft constraints hypothesis: A rational analysis approach to resource allocation for interactive behavior. Psychological Review, 113(3), 461-482.

Lee, N.Y. Louis, Goodwin, G. P. & Johnson-Laird, P.N. (2006). The Psychology of Su Doku Problems. In Sun, R., & Miyake, N. (Eds.). Proceedings of the 28th annual meeting of the Cognitive Science Society, 2543.

Simonis, H. (2005). Sudoku as a Constaint Problem. In Hnich, B., Prosser P., and Smith B., (eds.),Proceedings 4th Int. Works. Modelling and Reformulating Constraint Satisfaction Problems (pp. 13–27). Suchard, E, Yatom, R. & Shapir, E. (2006). Sudoku and Graph Theory. Dr. Dobb’s Journal. URL: http://ddj.com/windows/184406436

Back to Home << Publications

Visitors since 2004.12.08: