Solved-Programming Assignment #2- Solution

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.