Problem Set 5 FAQ

If you don’t see your question here, post it on Piazza or come to office hours! See the links in the navigation bar for both of those options.

Problem 5

1. I’m having trouble with the Sudoku problem. Can you give us any hints on how to get started?

   The basic idea behind recursive backtracking is that you have a number of variables that can each take on a number of possible values, and you are trying to assign values to the variables subject to a set of constraints.

   In the Sudoku problem, what are the variables? What are the possible values for each variable? What are the constraints – i.e., the requirements that the values of the variables need to fulfill?

   A given invocation of the recursive-backtracking method uses a loop to consider all possible values for one of the variables. Once a value is successfully assigned to that variable, the method calls itself recursively, this time to consider all of the possible values for the next variable in the list (given the values of the variables that have already been set). If you have successfully found values for all of the variables that fit the constraints, your terminating condition is met, and you can display the solution and return.

   If a particular value for a variable violates a constraint, you should skip that value and keep trying other values. If you run out of values for a variable, you should backtrack to the previous level of the recursion and go back to trying values for the previous variable.

2. I am struggling to apply the backtracking template from the lecture notes and the n-Queens solver solution to the Sudoku problem. I’m confused about what n and val in the template should mean in the context of this problem.

   As we said in the answer to the previous problem, recursive backtracking is a method for assigning values to a set of variables in light of a set of constraints. In the template, n tells you the variable that you’re currently trying to assign a value to, and val iterates over the set of possible values for that variable. (Note that n is not the variable itself - it is simply a parameter that allows you to determine the variable. For example, in the n-Queens problem, n was the number of row in which we were trying to place a queen, but we stored the actual values – i.e., the locations of the queens – in other data structures.)

   Our template mentions that you might sometimes want to have additional parameters for the recursive-backtracking method. For this problem, you will need to decide how many parameters you want to use in your solveRB() method, and what they will mean. There is more than one correct choice for the number and meaning of the parameters. All that matters is that your parameter or parameters allow you to specify which variable the current method call is responsible for.

   Another detail of the template that can vary is the way that the parameters to the method are modified in the recursive call. In the template, n is incremented by 1 to indicate that the recursive call will focus on the next variable. However, depending on the parameter(s) that you decide to use for your method, you may need to modify it/them in some other way when you make the recursive call. The important thing is that the new parameter value(s) should reflect the subproblem that you’re trying to solve by making the recursive call, and the parameter(s) should eventually reach a base case of the recursion.

3. Based on some temporary debugging statements that I have added to my code, my solveRB() method seems to be working more or less as expected. However, I end up either caught in an infinite loop, or getting back a final return value of false instead of true. Do you have any suggestions?

   One thing worth checking is how you are handling the cells that have fixed values. You should be checking for a fixed-value cell before you begin the for loop, because you do not want to try to assign any values to these cells.

   Instead of entering the for loop for these cells, you should instead do two things:

   • make a recursive call to move onto the next cell

   • return whatever value is returned by that recursive call.

   Taking this approach will allow you to pass back to the invocation for the previous cell the result of processing the subsequent cells.

4. I’m not sure if my constraint-checking method is working correctly. Is there an easy way to check it?

   One thing you could do is to add to your Sudoku class a non-static helper method called test() that looks like this:

   public void test() {
       System.out.println(this.isValid(...));
       System.out.println(this.isValid(...));
       // add other similar lines here
   }
   

   Replace each ... with parameters for a single call to your constraint-checking method (which we’re assuming you have called isValid, but you can adjust the name here if you called it something else).

   Choose the parameters of the calls based on one of the puzzles that we have given you. For example, you could base your calls on puzzle1.txt:

   -------------------------------------
   |   | 4 |   |   |   | 3 | 7 |   |   |
   -------------------------------------
   |   | 8 | 9 | 7 |   |   | 1 |   |   |
   -------------------------------------
   |   |   |   |   |   | 4 | 2 |   |   |
   -------------------------------------
   |   |   |   |   |   |   |   |   | 1 |
   -------------------------------------
   | 6 |   |   | 5 | 1 | 8 |   |   | 9 |
   -------------------------------------
   | 2 |   |   |   |   |   |   |   |   |
   -------------------------------------
   |   |   | 5 | 3 |   |   |   |   |   |
   -------------------------------------
   |   |   | 6 |   |   | 1 | 9 | 4 |   |
   -------------------------------------
   |   |   | 1 | 2 |   |   |   | 6 |   |
   -------------------------------------
   

   Given this puzzle, possible tests could include:

   • testing if it is valid to put a 4 in the upper-left hand corner; your method should say that it isn’t, because there is already a 4 in that row

   • testing if it is valid to put a 9 in the upper-left hand corner; your method should say that it isn’t, because there is already a 9 in that 3x3 subgrid

   • testing if it is valid to put a 5 in the upper-left hand corner; your method should say that it is, because there isn’t a 5 in that row, column, or 3x3 subgrid.

   Once you have created this test() method, add a temporary call to it in the main() method – calling it after the puzzle is read in but before the solve method is called:

   ...
   puzzle.test();    // temporary call to new test method
   
   if (puzzle.solve()) {
       ...
   

   Then, run the program and specify puzzle1.txt as the desired puzzle, and see whether you get the expected return values from your test calls.

5. I don’t understand why the three dimensional array subgridHasVal is being created as a 9x9x10 three dimensional array in the Sudoku no-arg constructor.

   public Sudoku() {
       ...
   
       this.subgridHasVal = new boolean[9][9][10];
   }
   

   The reason it is 3-dimensional array is because each 3x3 sub-grid can contain one appearance of 10 possible values 0-9. The third dimension is created as an array of 10 so that you can index each possible value 1 - 9 directly without having to adjust for the offset.

   As our Sudoku grid is fixed to 9x9 we really only on need to consider a 3x3 sub-grid. Do not worry that it is being created larger than it needs to be. You will only need to use the top left qudrant, as though it was created as [3][3][10]. You could also create it as [3][3][9] but then would have to know that [1][1][0] is the check to see if the number 1 has been placed in the middle sub-grid, etc.