Introduction to Artificial Intelligence

CSP Programming Assignment: Comparing Brute-Force Searching with the MRV Heuristic in a Constraint Satisfaction Problem, Using Sudoku Puzzles
 
Summary In this assignment, students compare the performances of a brute-force search and a search employing the Minimum Remaining Values (MRV) heuristic, in solving Sudoku puzzles.
Topics Uninformed Searching, Informed Searching, Intelligent Agents, Recursive Backtracking Search, MRV Heuristic.
Audience Introduction to AI.
Difficulty Moderate to challenging. Students must build their programs with no provided framework, so they must make decisions about how to model a Sudoku puzzle internally. Both the brute-force search and the MRV search are rooted in the basic recursive backtracking search, th only real difference being in the method of selecting the next variable to assign. Most students should probably be able to build both agents in about 15-25 hours.
Strengths

This assignment is specifically designed to illustrate the value of using the MRV heuristic over a brute force search for a constraint satisfaction problem. By measuring the efficiencies of the two algorithms in terms of variable assignments attempted instead of elapsed time, students can get a better feel for how much additional work a brute force search actually does.

Students are given flexibility in the choice of programming language, so the assignment can be adapted to curriculums regardless of what programming language is used for the curriculum's core coursework.
Weaknesses Sudoku is becoming a popular test bed for AI courses, so some modifications may need to be made at some point to discourage students from searching for solutions on the internet. The strength of flexibility in programming language used nevertheless imposes a restriction in that students must use a language that will enable them to count variable assignments.
Dependencies Uninformed and informed searching; competency in chosen programming language
Variants

Sudoku puzzles of different sizes (e.g., 4 x 4) and difficulties (number of initial assignments) can be used in addition to the standard 3 x 3 puzzles.

The order in which the legal domain values are attempted can be modified to see how that affects the search.

Since it is possible for there to be more than one variable with the same MRV value, rather than greedily using the first such variable found, some thought can be put into discriminating between them.

The MRV heuristic can be augmented by the Least Constraining Value (LCV) heuristic, which attempts to choose the optimal order in which to try the values available after the MRV heuristic has been applied.

Arc consistency can be added to provide forward checking capability.

The assignment can also be viewed as a graph coloring problem. With this approach, the constraint would be that no two adjacent cells may have the same value.

Link to assignment

Selected test puzzles

Source Code for Instructors