When I run one of the recursive methods that I’ve written for
problem 6, I get a NullPointerException. Do you have
any idea of why that might be happening?
A NullPointerException occurs when you try to call a method using
a reference variable with a value of null. For example, if you
have a variable named str with a value of null and you call
str.length(), you will get this exception because there is no
object on which the length() method can be invoked. You may need
to check first if the value of a reference variable is null before
attempting to use it to call a method.
In one of my recursive methods for problem 6, I’m getting a
StringIndexOutOfBoundsException. What am I doing wrong?
Don’t forget that the characters in a string have index values that go from 0 to length - 1. The exception means that your code is using an index from outside that range.
In one of my recursive methods for problem 6, I’m using the
substring method to create a substring that has everything but the
first character from the original string. I’m using the expression
str.substring(1, str.length() - 1), but I seem to be losing
characters at the end of the string as well.
Don’t forget that the second parameter to the substring method is
non-inclusive. So if you want the last character to be included in
the substring, your should use the expression
str.substring(1, str.length()) – without the “- 1”.
Alternatively, you could use the version of substring that only
takes a start index: str.substring(1).
I’m having trouble figuring out how to structure the recursive case of one of the recursive methods for problem 6. Do you have any hints on how to do this?
One thing that can help is to consider what should happen for one or more concrete cases – as we did in the example problem that we covered in lecture.
For example, let’s say that you needed to write a recursive
removeVowels method. As
with many recursive methods that operate on strings, this method
should make recursive calls on ever smaller substrings. For example,
let’s say that we wanted to do removeVowels("movies")
This would lead to the following sequence of method calls:
removeVowels("movies") removeVowels("ovies") removeVowels("vies") removeVowels("ies") removeVowels("es") removeVowels("s") removeVowels("")
(The last call might not be needed. It depends on which base cases you choose to include.)
Then, once you have the sequence of method calls, you should think
about what each of these separate method calls should return,
treating them as if they were independent of each other. For
example, what should removeVowels("ies") return – i.e., what
string will result if the vowels in "ies" were removed? Based on
these return values, you should be able to figure out how a given
invocation of the method should use the return value from the
recursive call to form its own return value.
One of my recursive methods for problem 6 is not working correctly. Do you have any suggestions?
Try tracing through some concrete examples of cases in which the your method is not returning the correct value. You might want to try adding some temporary printlns to see if that helps you to diagnose the problem. In particular, you could print what the method will return before it actually returns it. That will allow you to see when the wrong value is being returned.
In addition, if your method returns a value, make sure that you aren’t throwing away the return value of the recursive call. For example, consider this incorrect version of a recursive method that determines if a string is a palindrome – i.e., if it is a word like “radar” that reads the same in either direction:
public static boolean isPalindrome(String str) { if (str == null || str.equals("")) { return true; } // recursive call -- the return value is thrown away isPalindrome(str.substring(1, str.length() - 1)); char first = str.charAt(0); char last = str.charAt(str.length() - 1); if (first != last) { return false; } else { return true; } }
This version of the method makes the correct recursive call – looking at the substring consisting of everything except the first and last characters – but it throws away the value that is returned.
To avoid losing the return value of the recursive call, we can do one of two things:
I’m having trouble with the recursive trim method. Do you have any
suggestions.
First, it’s worth noting that you will likely need an additional base case beyond our usual one for string inputs.
Given the description of what the method is supposed to do, for what cases besides the empty string would it be possible to return the correct solution without needing to make a recursive call?
Second, consider including more than one possible recursive call. The following concrete cases can help in coming up with the different possible calls:
If the current call is
trim(" hello")
what should the recursive call be – i.e., what smaller subproblem would bring me closer to one of my base cases, and would do so in such a way that I could use the solution to the subproblem to determine the solution to the current problem?
If the current call is
trim("hello ")
what should the recursive call be?
If the current call is
trim(" hello ")
what should the recursive call be?
Use these and other concrete cases to construct different possible
recursive calls, and then include conditional code that makes the
appropriate recursive call based on the current value of the input
str.
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. In the Sudoku problem, there is a variable for each cell in the puzzle, and you are trying to determine the integer value from 1-9 that should be assigned to each variable, subject to the constraints of the puzzle. (What are the constraints in this problem? What requirement do 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 they have already 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.
I am struggling to apply the backtracking template from the
lecture notes 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.
In Sudoku, the parameter n is the number of the cell that a given
invocation of the recursive-backtracking method is responsible
for. See the comments that come before the template for the
solveRB() method in Puzzle.java for a recommendation of how to
number the cells.
I’m finding it hard to come up with a way to efficiently check whether a number I’m considering placing in a cell satisfies the Sudoku constraints. Can you give us any hints?
When you’re considering placing the number i in cell n, you need data structures to quickly tell you whether the number i has already been placed in the row, column, and 3x3 subgrid that cell n belongs to. Recall that in the n-queens example we used arrays of booleans to keep track of whether a given column or down/up diagonal was occupied.
We have already given you a field that should help you to keep track
of whether a number is already present in a given 3x3 subgrid, and
our placeVal and removeVal methods update those arrays as
needed.
As mentioned in the assignment, you must add whatever additional fields are needed to efficiently determine whether a given value can be placed in a given cell without scanning over the rows or columns of the Sudoku board. The new fields that you add will be similar to the field that we have given you for the subgrids, but they should be a bit simpler!
We also encourage you to review the fields used for
constraint-checking in the n-Queens solver: colEmpty, upDiagEmpty, and
downDiagEmpty. How are they used to avoid the need to scan
through the board when checking if a given value satisified the
constraints of that problem? You should do something similar here.
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.
Based on some temporary debugging statements that I’ve 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.
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 Puzzle 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 of Sudoku.java – 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.
Last updated on January 27, 2026.