Introduction to Artificial Intelligence

CSP Programming Assignment: Comparing Brute-Force Searching with the MRV Heuristic in a Constraint Satisfaction Problem, Using Sudoku Puzzles

Source Code for Instructors

 

I have left this assignment open-ended in terms of programming language since in my experience teaching our Intro to AI course, I have encountered many students with diverse programming backgrounds. Our CS I-III sequence is done in Java, so I initially required students to write their programs in Java, but this caused problems for transfer students who had completed their CS I-III sequence using a different programming language. However, open-ended assignments can also cause significant problems, so I have included a zip file containing a prototype project, written in Java, that fulfills the requirements of this assignment. Although this code contains a solution to the assignment, it is relatively easy to remove key pieces of code, leaving the remainder as a template for students to use as a foundation. The key pieces of code the students should write (or at least fill in) are:

  1. the backtracking search algorithm (BacktrackingSearch.java)
  2. the brute force variable selector (BruteForceVariableSelector.java)
  3. the MRV-informed variable selector (MRVVariableSelector.java)
  4. the agent (SudokuCSPAgent.java)

This code includes a GUI with capabilities to show both the uninformed and MRV-informed searches in progress, which allows students to visualize how each agent functions. Since long-running recursive code typically causes a GUI to freeze, in order to enable the GUI to show "live" progress I have allowed some unconventional coupling between the search algorithm and the GUI, to allow the search to update the GUI directly as it proceeds. I have tried to keep the GUI relatively simple, but if students are not familiar with Java Swing, or if they find the GUI too difficult to assimilate, the project is also amenable to using the standard output for displaying the results.

Below is a link to the Java source files for the project:

Sudoku_brute_force_vs_MRV_src.zip

I welcome any comments or suggestions for improvement you may have.