Teaching Artificial Intelligence Across the Computer Science Curriculum using Sudoku as a Problem Domain

All Papers

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 introductory- and upper-level computer science courses.