Question

The logic puzzle known as Sudoku has become very popular recently. Although Sudoku puzzles can come in a variety of sizes, the most common size is a 3 x 3 grid of boxes, each of which contains a 3 x 3 grid of cells. The object is to place the digits 0-9 in the squares such that the following constraints are obeyed: 1. Each row must contain one and only one of each digit. 2. Each column must contain one and only one of each digit. 3. Each of the larger 3 x 3 boxes must contain one and only one of each digit. In the puzzle's initial state some of the digits are already present, but most of the cells are blank. The goal is to use logic to figure out which number should be placed into each cell such that the above constraints are not violated. Figure 1 shows an example of a Sudoku puzzle in both its initial and solved states. 5 98 4 7 8 6 6 7354 2 8 4 6 3 5 9 4 2 8 7 1 472 51 839 18 9 6 7 3 5 4 8 6 7 3 9 1 2 5 2 1 3 4 8 5 6 9 5 4 2 6 7 1 3 5 4 8 1 3 9 6 2 9122648 2 1 3 85 6 8 5 813 6 7 9 2 00 3 5 2 9 1 7 2 6 8 5 4 9 1 3 Figure 1. Example of a Sudoku puzzle. The diagram on the left represents the puzzle in its initial, unsolved state. Pre-assigned values are shown. The diagram on the right is the puzzle after it has been solved. The nine boxes in the puzzle are shown using alternating blue and white backgrounds for the individual squares that make up the boxes.

Programming Language: JAVA

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

1. 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).

2. 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.

3. 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.

4. 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.

5. Build 2 separate agents for solving the puzzles: a. 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. b. 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.

6. You may find it useful to implement the backtracking search algorithm. This is not a strict requirement, but this algorithm is a good, general purpose backtracking search that is suitable for CSPs.

7. 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.

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

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

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