Programming Assignment #2 Solution

For this assignment, you will implement a hill-climbing search algorithm as discussed in the course notes and Section 4.1 of the textbook. We will be using this program to solve simple 4-sudoku problems such as those described in Homework 2. A 4-sudoku grid is a smaller version of the more typical 9-sudoku grid, where the cells may have values only between 1 and 4. As with the larger 9-sudoku problem, the goal for a 4-sudoku problem is to fill all of the grid elements such that no row, column, or "box" has duplicate entries. A sample 4-sudoku grid (taken from Homework 2) is shown below:









2
4


_
_






















_
3


_
_


















































_
_


4
_






















_
_


3
1














































Your job is to write a hill-climbing program to solve arbitrary 4-sudoku problems. Your program will need to read a 4-sudoku problem from a file, set up an initial state based on the file, and then find a solution to the problem via hill climbing. Note that since hill-climbing is never guaranteed to find a solution your program should make use of the random restart technique to start the search over if it reaches a local minimum and cannot find a better successor state to evaluate.




Your code should take a filename on the command line and read in a "blank" sudoku board using a format where the first line of the file will be the number 4. Each line after the first line will hold one row of the sudoku board, where the blanks in the board are indicated by '*' characters. For example, the input file for the board above would be:







4




24**




*3**




**4*




**31




Hill-climbing requires that the state be represented as a vector, and the sudoku problem requires that any values that are "fixed" at start time remain fixed. So these are two problems for your state representation. My suggested method of handling this would be to make your state vector a vector of the blank spots on the board and maintain some kind of mapping between the positions in the vector and positions on the sudoku board. For example, the above sudoku board might have a mapping like this:







State vector: [ a, b, c, d, e, f, g, h, i, j ]






Programming Assignment 2







24ab




c3de




fg4h




ij31




Meaning that the value in position 'a' of the vector belongs in position 'a' of the sudoku board and so on. You might also want to consider "flattening" the sudoku board out to a long 1d vector, rather than dealing with a 2d mapping (or not, depending on your tastes). A 1d version of the board would look like this:













24abc3defg4hij31




And the mapping could then be contained in a vector that maps index 0 of the vector to position 2 on the 1d board above, index 1 to position 3, index 2 to position 4, index 3 to position 6, and so on. This representation is only a suggestion, and you are not required to use it. If you can think of something better please use it - this is just a suggestion for a simple representation.




I suggest following the pseudocode either from the textbook or from the course notes. You should write a function named hillClimber() that takes an initial state as a parameter. Remember that the initial state should contain no blank elements. You should choose a random initial state with all elements filled in and no blanks. You will also need to write a successor function to generate possible successors to the current state. You can come up with your own successor function, but the easiest one is to generate all the possible states that you can get by changing any single number on the board to any other possible value. (If you can come up with a more clever successor function, note it in your readme file and explain why you think it's so clever).




You will need to write an evaluation function that "scores" your state vector based on how well it fits the sudoku board. I would recommend an evaluation function that counts the total number of conflicts in a board. For example, in the board above a '4' in position 'a' would give two conflicts - one with the '4' in the same row, and one with the '4' in the same column. Remember to include a check for a conflict in the same "box" of 4 elements (so each blank can potentionally have up to 3 conflicts). It's safe to double-count conflicts, so long as you are consistent about it, so don't worry about keeping track of whether or not you've already counted a particular conflict or not and just iterate over every position on the board counting the conflicts. If you take this approach, your hill climbing algorithm will be attempting to minimize this evaluation function and you will know that you have a solution when your evaluation function returns 0 conflicts for a state. If you do this, note that where the notes and the textbook say "ChooseHighest" you will actually want to choose the lowest since you will be minimizing your evaluation function instead of maximizing it. (Again, if you come up with an evaluation function that you think is more clever than this one, note it in your readme file and explain why you think it's so clever.)




At every step, your hillClimber() function should output to the screen each state that it chooses, as well as the result of your evaluation function for that state, and a count of the number of iterations it has taken so far. You don't need to put the full sudoku board out to the screen, just the state vector. You should also include a "TestHarness" program that reads the sudoku problem from the file, sets up the initial state, and calls the hillClimber() function. When the hillClimber() function is finished, it should pass back the solution state that it has found and the TesthHarness should display it to the screen.


Programming Assignment 2




MAKE SURE YOU TEST YOUR CODE WITH OTHER PROBLEMS! We will pick a few 4-sudoku problems to test your code with other than the one provided. We will only use problems that are guaranteed to have solutions, and no conflicts in the base setup (so you don't need to test for valid input boards).




Make sure that your code runs our our stdlinux environment and INCLUDE A TEXT FILE with your submission with instructions on how to run each part on our stdlinux environment. Create a ZIP archive that includes ALL of the files needed to run your code (including elements from the code repository or the sample code provided above) as well as your instructions and upload that ZIP file to the dropbox on carmen. Make sure your code is fully documented and includes your name in an obvious position at the top of each file you have written. MAKE SURE YOUR CODE RUNS ON THE stdlinux ENVIRONMENT! We will only be testing your code in this environment. DO NOT TRY TO MAKE US FIGURE OUT HOW TO COMPILE AND RUN YOUR CODE. If you do not provide instructions on how your code is to be compiled and executed on stdlinux WE WILL NOT EVEN LOOK AT YOUR CODE AND YOU WILL RECEIVE A ZERO FOR THE ASSIGNMENT.