Teaching Artificial Intelligence across the Computer Science Curriculum Using Sudoku as a Problem Domain.

Artificial Intelligence (AI) is a field of both great breadth and depth. Thus, determining undergraduate material for an AI course can be problematic. Fortunately, AI is continually searching for new perspectives on problem solving that eventually propagate into the Computer Science mainstream. An approach is proposed for undergraduate AI education that utilizes these aspects of exploration and propagation. The approach introduces important individual techniques early in the computer science curriculum to form a foundation for the upper-level AI course focusing on research methods. This approach is explored using two Sudoku projects at different levels in the Computer Science curriculum, with constraint satisfaction used as the individual technique. Sudoku is a logic puzzle that has a great deal of appeal and is easily encoded as a constraint satisfaction problem domain. In the introductory-level CS 2 course, the Sudoku-based project uses a provided BackTrack class that can be employed to find a path through a maze, place eight queens, or schedule a knight’s tour. This illustrates the power of recursion in general and backtracking in particular (a central aspect of constraint satisfaction techniques.) In the upper-level AI course, Sudoku is used as a problem domain for developing a puzzle solver using the full breadth of constraint satisfaction techniques and producing an optimal puzzle generator using a technique of the student’s own selection. Students are required to write a research quality publication based on the results of their projects. The goal of the paper is to provide a research experience where not only a solution is derived but the reasoning process is directly explored. Due to the frequency that the AI course is taught, two separate student populations are discussed. The results from the dual population still allow for a viable exploration of this cross-curriculum approach. Finally, the paper illustrates that Sudoku is an excellent problem domain choice for teaching AI approaches in both introductoryand upper-level computer science courses. Copyright c © 2007, American Association for Artificial Intelligence (www.aaai.org). All rights reserved. Introduction Artificial Intelligence (AI) has directly influenced many areas of computer science and produced a plethora of techniques. Thus, determining the important topics for a single semester undergraduate AI course is a nontrivial task. This issue is illustrated by the ACM Computing Curricula 2001 (CC2001) document, which details ten modules for Intelligent Systems study. Three of the ten modules are considered “core” and consist of 10 contact hours, with the topics being: Fundamental Issues, Search and Constraint Satisfaction, and Knowledge Representation and Reasoning. For the remaining “elective” contact hours, the material includes: Advance Search, Advanced Knowledge Representation, Agents, Natural Language Processing, Machine Learning and Neural Networks, Planning Systems, and Robotics. No single-semester course could cover this range of material in a rigorous fashion, leaving the question of what to cover. Generally the choice is left up to the faculty member’s preference, which can be guided by a variety of factors. We propose an approach that leverages the fact that AI is both an exploratory field that has also contributed directly to many areas of mainstream Computer Science. The proposal is to front-load core AI techniques in earlier low-level courses, where appropriate, with a brief discussion of how this technique is used in the higher-level AI course. This technique is reinforced with a project that ties the technique to the currently covered material. The “front-loading” of material serves to provide students with an intuition about AI techniques before they reach the actual course. Once reaching the AI course, the focus can switch from using techniques to developing techniques, or to teach students the process of exploration. To reinforce an exploratory approach students are required to develop a research quality paper that explores and extends a particular technique. To explore this approach constraint satisfaction techniques and the Sudoku problem domain were focused on. Constraint satisfaction was chosen because of its applicability to recursive solutions and thus is a good target for inclusion in a CS 2 course, in addition to being one of the core AI modules. Sudoku is used for a variety of reasons: its symbolic