Construct a program that uses an agent to solve a Sudoku puzzle as a Constraint Satisfaction Problem, with the following guidelines:

Since 3 x 3 puzzles are too trivial for a computer, your program should use 4 x 4 puzzles (also known as Super Sudoku puzzles; see Figure 2 for an example).

The program should read a Sudoku puzzle from a text file. The user should be able to browse the file system to select this file. See Figure 2 for the format the text file should obey. Please be sure you follow this format, as I will test your program by loading my own test puzzles. How you represent the puzzle within your program is entirely up to you.

You do not need to generalize your program to cover other sizes of Sudoku puzzles, so you can assume all puzzles tested will be of the 4 x 4 variety.

Any set of 16 unique symbols can be used for a 4 x 4 Sudoku puzzle. The standard set consists of the same characters used in hexadecimal arithmetic (numerals 0-9 plus letters A-F). This is the symbol set I will use in my tests. You may use any symbols you wish, but make sure your program can handle any set of 16 unique characters that can be represented in a text file. In keeping with the standard CSP terminology, I will refer to the cells in the puzzle as the variables, and the chosen domain of valid characters as the values.

Build 2 separate agents for solving the puzzles:

An uninformed agent that attempts to solve the puzzle by starting with the first empty cell and progressing from left to right, top to bottom. This is considered the default variable selector.

A CSP agent that uses the MRV heuristic to reduce the size of the search space. The order in which cells should be assigned using this heuristic is in order of increasing number of possible values. The number of possible values for a given cell is determined by looking at the row, column, and box that have that cell in common, and subtracting from 16 the number of unique values that are already present. The range can be anywhere from 1 to 16 for an empty cell.

You may find it useful to implement the backtracking search algorithm, the pseudocode for which is shown on page 215 of the text. This is not a strict requirement, but this algorithm is a good, general purpose backtracking search that is suitable for CSPs.

To measure the relative efficiencies of the two agents, incorporate the ability to maintain counts of the total numbers of cell assignments attempted using each method of selecting variables to assign. Feel free to measure the actual running time if you wish, but counting the total number of attempted variable assignments will give the best, implementation-independent estimate of relative efficiency.

You may use any programming language you wish, provided I am able to install and compile your code on Windows 7. One exception to this is that I cannot accept programs written in any Visual Studio version prior to .NET, since programs written in earlier versions like VB6 do not convert easily. Currently the only version of Visual Studio I am running is Visual Studio 2010.

You are not required to build an extensive framework for this assignment, so do not feel obligated to conform to the framework described by the authors in the text.

Test both agents on a variety of 4 x 4 Sudoku puzzles

Use at least 5 different puzzles in your tests. Try to ensure the puzzles have different levels of difficulty.

Compare the results of your two agents on each puzzle you test.

Write a brief discussion of your observations.