Background The logic puzzle known as Sudoku has become very popular recently. Although Sudoku puzzles can come in a vari

[answerhappygod]

BackgroundThe logic puzzle known as Sudoku has become very popular recently.Although Sudokupuzzles can come in a variety of sizes, the most common size is a 3x 3 grid of boxes, each ofwhich contains a 3 x 3 grid of cells. The object is to place thedigits 0-9 in the squares suchthat 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 ofeach digit.In the puzzle’s initial state some of the digits are alreadypresent, but most of the cellsare blank. The goal is to use logic to figure out which numbershould be placed into each cellsuch that the above constraints are not violated. Figure 1 shows anexample of a Sudokupuzzle in both its initial and solved states.Figure 1. Example of a Sudoku puzzle. The diagram on the leftrepresents the puzzle inits initial, unsolved state. Pre-assigned values are shown. Thediagram on the right is thepuzzle after it has been solved. The nine boxes in the puzzle areshown using alternatingblue and white backgrounds for the individual squares that make upthe boxes.
Suppose we want to construct an agent to solve any given 3 x 3Sudoku puzzle.Given an empty starting grid there are6,670,903,752,021,072,936,960 (or 6.67 x 1021)unique problems that can be created. As you can see, the 3 x 3Sudoku problem is far toopermutationally complex to try to compare the initial state to allthe possible solutions inorder to find the one that matches the initial configuration ofdigits. A brute-force, uninformedsearch, in which each digit is tried systematically in each cell,will solve the puzzle, but it won’tbe able to do so efficiently. In fact, it could quickly overwhelmavailable memory. Assumingabout 36% of the cells already contain digits in the initial state,as in the example above, thatstill leaves about 52 open cells. Thus, the branching factor at thefirst level in the search treewould be 52. The branching factor of the second level would be 51(for each of the 1st level’s52 nodes); the third level would be 50, and so on. The total numberof combinations wouldbe on the order of 8 x 1067.It should be apparent that the order in which the digits are filledin is irrelevantsince the only item of interest is reaching the goal state.Therefore, a Sudoku puzzle can besolved as a constraint satisfaction problem. Another benefit ofsolving a problem like this asa constraint satisfaction problem is that the constraints arechecked each time a symbol isplaced. If a constraint is violated, the failure is returnedimmediately, which eliminates a lotof pointless searching down paths that cannot return asolution.If you have ever solved Sudoku puzzles before, you most likely didnot begin at thefirst empty cell and systematically work your way left to right,top to bottom. The problemwith this approach is that most cells in a typical Sudoku puzzlecannot be assigned a valuewith certainty until it can be proven that the chosen value doesnot violate any of the puzzle’sconstraints. Most people tend to look first for cells where thenumber of possible values islimited to three or fewer, since it becomes mentally taxing to tryto look ahead much furtherthan that. People who solve Sudoku puzzles this way are utilizingthe Minimum RemainingValues heuristic—probably without realizing what the MRV heuristicis. The MRV heuristic is agood choice for Sudoku puzzles because initiating a search at thecell with the fewest numberof possible values will always prune a significant portion of thesearch space.What you need to doConstruct a program that uses an agent to solve a Sudoku puzzle asaConstraint Satisfaction Problem, with the followingguidelines:1. Since 3 x 3 puzzles are too trivial for a computer, your programshould use 4 x 4puzzles (also known as Super Sudoku puzzles; see Figure 2 for anexample).2. The program should read a Sudoku puzzle from a text file. Theuser should be ableto browse the file system to select this file. See Figure 2 for theformat the text fileshould obey. Please be sure you follow this format, as I will testyour program byloading my own test puzzles. How you represent the puzzle withinyour program isentirely up to you.3. You do not need to generalize your program to cover other sizesof Sudoku puzzles,so you can assume all puzzles tested will be of the 4 x 4variety.4. Any set of 16 unique symbols can be used for a 4 x 4 Sudokupuzzle. Thestandard set consists of the same characters used in hexadecimalarithmetic(numerals 0-9 plus letters A-F). This is the symbol set I will usein my tests.You may use any symbols you wish, but make sure your program canhandleany set of 16 unique characters that can be represented in a textfile. Inkeeping with the standard CSP terminology, I will refer to thecells in the puzzleas the variables, and the chosen domain of valid characters as thevalues.
5. Build 2 separate agents for solving the puzzles:a. An uninformed agent that attempts to solve the puzzle bystarting with the firstempty cell and progressing from left to right, top to bottom. Thisis consideredthe default variable selector.b. A CSP agent that uses the MRV heuristic to reduce the size ofthe search space.The order in which cells should be assigned using this heuristic isin order ofincreasing number of possible values. The number of possible valuesfor a givencell is determined by looking at the row, column, and box that havethat cell incommon, and subtracting from 16 the number of unique values thatare alreadypresent. The range can be anywhere from 1 to 16 for an emptycell.6. You may find it useful to implement the backtracking searchalgorithm, thepseudocode for which is shown on page 215 of the text. This is nota strictrequirement, but this algorithm is a good, general purposebacktracking searchthat is suitable for CSPs.7. To measure the relative efficiencies of the two agents,incorporate the ability tomaintain counts of the total numbers of cell assignments attemptedusing eachmethod of selecting variables to assign. Feel free to measure theactual runningtime if you wish, but counting the total number of attemptedvariable assignmentswill give the best, implementation-independent estimate of relativeefficiency.8. You may use any programming language you wish, provided I amable to installand compile your code on Windows 10. One exception to this involvesMicrosoft’sVisual Studio Environment. If you wish to use Visual Studio, pleaseuse the mostrecent version of the IDE. I am currently running the most recentversion availablethrough UIS. Programs written in earlier versions of VS may or maynot be convertedreliably.9. You are not required to build an extensive framework for thisassignment, so do notfeel obligated to conform to the framework described by the authorsin the text.Test both agents on a variety of 4 x 4 Sudoku puzzles1. Use at least 5 different puzzles in your tests. Try to ensurethe puzzles have differentlevels of difficulty.2. Compare the results of your two agents on each puzzle youtest.3. Write a brief discussion of your observations.