Searching

Let's say we were going to play a guessing game. I tell you I'm thinking of a number between 1 and 100. I say I don't want to make things too easy on you, so I'm not going to give you any clues or hints, other than to tell you when you've guessed correctly. What guessing strategy would you use? Given that all I will tell you is whether your guess is correct, there's nothing better for you to than to guess each number between 1 and 100 until you happen to get it right. You start by guessing 1, then you guess 2, then you guess 3, and so on.

To make this more general, instead of limiting it to 100, let's say I pick a number at random between 1 and \(n\). Sometimes you might get it right away, but other times you'll have to go through all \(n\) numbers to find it. So on average you'll need to guess \(\frac{n}{2}\) numbers before you find the one I chose. Thus, the big-O complexity of your guessing strategy will be \(O(n)\). We'll call this strategy linear search.

That's all well and good, but you point out that just guessing every number isn't a very fun game. I admit that's true, so now I'll give you a hint each time you make a wrong guess. Specifically, I'll tell you if the number I'm thinking of is higher or lower than what you guessed. How would this change your guessing strategy? A good way to take advantage of these new rules would be to guess right in the middle of the range of possible numbers (i.e., \(\frac{n}{2}\)). That way, if I say the number is higher, you can rule out the lower half of the range. If I say the number is lower, you can rule out the higher half of the range. You can continue this guessing in the middle strategy, each time ruling out half of the remaining numbers.

This seems like it will be a lot faster than when you had to guess every single number. But how much faster? The number of steps involved will depend on how many times you have to cut the set of possible answers in half. If you start with \(n\) possible numbers, eventually you will get down to just one. The number of steps, then, can be computed as:

n / 2 / 2 / 2 ... / 2 = 1
              n / 2^? = 1
                    n = 2^?
                    ? = log(n)

So your guessing stategy with these hints is \(O(\log_2 n)\). Because this strategy involves dividing by 2, it's called binary search.

These guessing game strategies also apply when it comes to searching for a value in a list. When we don't anything about the list we're searching, our only option is to check every value to see if it's the one we're looking for:

// perform a linear search over nums to check if target is present
public boolean contains(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == target) {
            return true;
        }
    }
    return false;
}

Under what circumstances could we use the binary search strategy on a list? We don't have another person to say higher or lower, so it will need to be some property of the list. In particular, when we check a number in the list, we need that to divide the list into two portions: one where all the numbers are larger and one where all the numbers are smaller. The key property here is that the list needs to be sorted. That way, when we check the number in the middle against the number we're looking for, we can narrow our search to just half the list. That is, if target is greater than the number in the middle of a sorted list, we know we only need to search the upper half of the list. Similarly, if target is less than the number in the middle of a sorted list, we know we only need to search the lower half.

// perform a binary search over nums to check if target is present
public boolean sortedContains(int[] nums, int target) {
    int lo = 0;                // first index of the portion of the list we're searching
    int hi = nums.length - 1;  // last index of the portion of the list we're search
    while (lo <= hi) {  // while there are indexes between lo and hi to check
        int mid = (lo + hi) / 2;  // index in the middle
        if (target == nums[mid]) {
            return true;  // we found it!
        } else if (target > nums[mid]) {
            lo = mid + 1;  // narrow our search to the upper half
        } else { // target < nums[mid]
            hi = mid - 1;  // narrow our search to the lower half
        }
    }
    return false;
}

We can also write this method using recursion instead of a loop:

private boolean recursiveContainsHelper(int[] nums, int lo, int hi, int target) {
    if (lo > hi) {
        return false;
    }
    int mid = (lo + hi) / 2;
    if (target == nums[mid]) {
        return true;
    } else if (target > nums[mid]) {
        return recursiveContainsHelper(nums, mid + 1, hi, target);
    } else { // target < nums[mid]
        return recursiveContainsHelper(nums, lo, mid - 1, target);
    }
}

public boolean recursiveContains(int[] nums, int target) {
    return recursiveContainsHelper(nums, 0, nums.length - 1, target);
}

Because the recursion needs to keep track of lo and hi, our recursive method needs to have them as parameters. Thus, we make a recursive helper method that has the parameters we need and call that from the original method.

For example, suppose you want to generate list all of the 3-digit numbers that are composed of the digits 1, 2, and 3:

123
111
333
321
...

We might write code to do this using a triply-nested for loop:

for (int d1 = 1; d1 <= 3; d1++) {
    for (int d2 = 1; d2 <= 3; d2++) {
        for (int d3 = 1; d3 <= 3; d3++) {
            System.out.println("" + d1 + d2 + d3);
        }
    }
}

This is a decent way of thinking about what is involved with exhaustive search: we are exploring a set of choices to be made (1st digit, 2nd digit, 3rd digit). We often want to see a diagram of the different choices and where they lead. Here is the diagram for the triply nested for loop above:

In backtracking, there is an additional idea that we don't tend to apply in exhaustive search. Instead of exploring every possible choice, we stop exploring when we hit a dead end. A dead end is a state where you know that there is no hope of finding a solution beyond a certain choice. For example, suppose that you are dealing with the Cartesian plane and you want to think about all possible paths from the origin (0, 0) to a particular point. Suppose, for example, that you want to get to the point (1, 2):

                y
                ^
                |
                |  * (1, 2)
                |
<---------------+---------------> x
                |
                |
                |
                V

Suppose that you are limited to just three kind of moves:

• North: moving up one in the y-direction
• East: moving up one in the x-direction
• Northeast: moving up one in both directions

Looking at it for a few minutes, you could figure out that there are five solutions to this:

N, N, E
N, E, N
E, N, N
NE, N
N, NE

How would you write a program to find all such answers? This is a problem where backtracking works nicely. The idea is that there is some set of possible answers that you want to explore. We try to view the problem as a sequence of choices, which allows us to think of the exploration process as a decision tree. This kind of diagram visualizes many possible sequences of choices. Here's an example from the web comic xkcd:

In general for decision trees, at the top of the tree we have the first choice with all of the possibilities underneath:

                           choice #1
                                |
       +----------------+-------+--------+----------------+ ...
       |                |                |                |
1st possibility  2nd possibility  3rd possibility  4th possibility

Each choice we might make at the top of the tree leaves us in a different group of possible solutions. From there, we consider all possible second choices we might make. Below is a complete decision tree for two possible moves:

What happens in backtracking is that we explore specific choices until we reach a dead end. Once we find that some path is not going to work out, we back up to where we last made a choice and make a different choice. That's where the idea of "backtracking" comes from (backing up to the last place we made a choice and moving on to the next choice).

Below is a diagram in which we explore all possible choices trying to move from the origin to the point (1, 2). We stop exploring when we get to an x-coordinate or y-coordinate that is beyond the value we are searching for because that is a dead-end:

To demonstrate the power of backtracking, let's solve a classic problem known as 8 queens. The challenge is to place eight queens on a chessboard so that no two queens threaten each other. Queens can move horizontally, vertically or diagonally, so it is a real challenge to find a way to put 8 different queens on the board so that no two of them are in the same row, column or diagonal.

Let's begin by considering the simpler problem of placing 4 queens on a 4-by-4 board. If we start off by putting a queen in the upper-left corner, try and see if you can get 4 queens onto the board that doesn't threaten each other.

Q  -  -  -
-  -  -  -
-  -  -  -
-  -  -  -

You may have been able to get 3 queens on this board with no two threatening each other, but not four. That's because I purposely led us down a bad path. There is no solution with a queen in the corner. Here's one that actually works:

-  -  Q  -
Q  -  -  -
-  -  -  Q
-  Q  -  -

It turns out that people are really smart about solving problems like these. Computers are not. So the computer will solve this by exploring all sorts of possibilities. The simplest way to think of this in terms of a decision tree is to imagine all the places you might put a first queen. For 8 queens, there are 64 of them because the chess board is an 8 by 8 board. So at the top of the tree, there are 64 different choices you could make for placing the first queen. Then once you've placed one queen, there are 63 squares left to choose from for the second queen, then 62 squares for the third queen and so on.

The backtracking technique we are going to use involves an exhaustive search of all possibilities. Obviously this can take a long time to execute, because there are lots of possibilities to explore. So we need to be as smart as we can about the choices we explore. In the case of 8 queens, we can do better than to consider 64 choices followed by 63 choices followed by 62 choices and so on. We know that a whole bunch of these aren't worth exploring.

One approach is to observe that if there is any solution at all to this problem, then the solution will have exactly one queen in each row and exactly one queen in each column. That's because you can't have two in the same row or two in the same column and there are 8 of them on an 8 by 8 board. So we can search more efficiently if we go row by row or column by column. It doesn't matter which choice we make, so let's explore column by column.

In this new way of looking at the search space, the first choice is for column 1. We have 8 different rows where we could put a queen in column 1. At the next level we consider all of the places to put a queen in column 2. And so on. So at the top of our decision tree we have:

                  choice for column 1?
                           |
                           |
  +------+------+------+---+--+------+------+------+
  |      |      |      |      |      |      |      |
row 1  row 2  row 3  row 4  row 5  row 6  row 7  row 8

So there are 8 different branches. Under each of these branches, we have 8 branches for each of the possible rows where we might place a queen in column 2. For example, if we think just about the possibility of row 5 for the queen in column 1, we'll end up exploring:

                  choice for column 1?
                           |
                           |
  +------+------+------+---+--+------+------+------+
  |      |      |      |      |      |      |      |
row 1  row 2  row 3  row 4  row 5  row 6  row 7  row 8
                              |
                     choice for column 2?
                              |
     +------+------+------+---+--+------+------+------+
     |      |      |      |      |      |      |      |
   row 1  row 2  row 3  row 4  row 5  row 6  row 7  row 8

Again, the pictures I can draw in these notes aren't very good because the tree is so big. There are 8 branches at the top. From each of these 8 branches there are 8 branches. And from each of those branches there are 8 branches. And so on, eight levels deep (one level for each column of the board). For example, we might choose to explore placing a queen in row 1 for column 1. So we go down that branch. We will explore all of the possibilities in that branch. If they all lead to dead ends, then we'll come back to the top level and move on to the possibility of having a queen in row 2 of column 1. We explore all of those possibilities. And if they all fail, we try row three for column 1. And so on. As long as we have more choices to explore, we keep trying the next possibility. If they all fail, we conclude that this is a dead end.

It's clear that the 8 choices could be coded fairly nicely in a for loop, something along the lines of:

for (int row = 1; row <= 8; row++)

But what we need for backtracking is something more like a deeply nested for loop:

for (int row = 1; row <= 8; row++)  // to explore column 1
    for (int row = 1; row <= 8; row++)   // to explore column 2
        for (int row = 1; row <= 8; row++)  // to explore column 3
            for (int row = 1; row <= 8; row++)  // to explore column 4
                ....

That's not a bad way to think of what backtracking does, but we're going to use recursion to write this in a more elegant way. Before we looked at the recursive solution to the problem, let's make our lives easier. These recursive backtracking problems are much easier to write and to understand if you separate off the low-level details of the problem. For the 8 queens problem let's assume we have supporting code for a board object to keep track of a lot of the details of the chess board. Here are the methods we'll assume such a Board object will have:

// Board constructor that takes an integer n so we could solve
// the more general "n queens" problem with an n-by-n board.
public Board(int size)

// tests whether it's safe to place a queen at a particular location
public boolean safe(int row, int col)

// a way to place a queen on the board
public void place(int row, int col)

// a way to remove a queen because the backtracking involves trying
//  different possibilities.
public void remove(int row, int col)

// a method that prints out the entire board, including placed queens
public void print()

// ask the board what size it is
public int size()

We could implement the Board class here but that's not the code we're interested in. So we'll assume we already have the Board class, which will make writing our backtracking code a lot more straighforward. So our program will prompt the user for a board size and construct a board of that size. Then it call a method called solve, passing it the Board object:

public void solve(Board board) {
    ...
}

One of the issues that comes up with recursive programming is that we are often asked to write a method like this and we discover that we want to have the recursion work in a different way. For example, we might want more parameters or we might want to have a different return type. So it's common with recursive programming to introduce a helper method that does the actual recursion. That's what we'll do here. So how is the recursion going to work? I pointed out that there are different ways to approach a backtracking problem. You can decide that you want to find all solutions or you might decide that one is enough. In this case, we are going to print all of them.

A good name for our recursive method would be explore. It is a helper method for the public method, so we want to make it private. So what we know so far is that it looks like this:

private void explore(...) {
   ...
}

What parameters will it need? It certainly needs the Board object. Anything else? One important observation is that each level of the decision tree will be handled by a different invocation of the method. So one method invocation will handle column 1. A second invocation will handle column 2 and so on. So what will the method need to know besides where the Board is? It needs to know what column to work on! So that leaves us with this signature:

private void explore(Board board, int col) {
    ...
}

When writing a backtracking algorithm, we don't want to waste our time exploring dead ends. So we want to think in terms of what kind of precondition we'd want for this method. For example, suppose that I've placed queens in columns 1, 2 and 3 and I'm thinking of calling the method to explore column 4. Would that make sense if the first three queens have not been placed safely? The answer is no. If the first three queens already threaten each other, then why bother placing any more? Once something becomes a dead end, we should stop exploring it. So the method should have the following precondition:

// pre: queens have been safely placed in previous columns

This precondition will turn out to be very helpful to us as we think through the different cases. We're using recursion to solve this, so we have to think about base cases and recursive cases. We might ask, "What would be a nice column to get to?" You might say "8" and I's say it would be nice to get to column 8 because it would mean that 7 of the 8 queens have been placed properly. But it would be even better to get to column 9 because the precondition tells us that if we ever reach column 9, then queens have been safely placed in each of the first eight columns. This turns out to be our base case. What do we do if we get to column 9? If we get there, we'd know that we've found an answer, so we can just print it:

if (col > board.size()) {
    board.print();
} else {
    ...
}

What about the recursive case? For example, maybe 4 queens have already been placed and we've been called up to place a queen in column 5. We have 8 possibilities to explore (the 8 rows of this column where we might place a queen). A for loop works nicely to go through the different row numbers. What do we do with each one? First we'd want to make sure it's safe to place a queen in that row of our column. If not, then it's a dead end that's not worth exploring. So our code will look like this:

for (int row = 1; row <= board.size(); row++) {
    if (board.safe(row, col)) {
        ...
    }
}

And how do we explore a particular row and column? First we place a queen there. And then we'd explore the other choices. In this case, the other choices involve other columns that come after our column. That's where the recursion comes in:

for (int row = 1; row <= board.size(); row++) {
    if (board.safe(row, col)) {
        board.place(row, col);
        explore(b, col + 1);
        ...
    }
}

But what if it doesn't work? What if it turns out to be a dead end? Then we want to move on to the next possibility and explore it. That means just coming around the for loop to try the next row. But it's not quite that simple, because we have placed a queen in the current row. We have to undo the current choice before we move on to the next choice:

for (int row = 1; row <= board.size(); row++) {
    if (board.safe(row, col)) {
        board.place(row, col);
        explore(board, col + 1);
        board.remove(row, col);
    }
}

This pattern of making a choice (placing a queen), then making a recursive call to explore later choices, and then undoing the choice (removing the queen) is common in recursive backtracking. It is almost a backtracking mantra: choose, explore, unchoose. If we get all the way through this for loop without finding a solution, then we simply return and allow the backtracking to proceed if there are any other choices to be explored.

It turns out this is the entire recursive backtracking code. Putting it all together we get:

private void explore(Board board, int col) {
    if (col > board.size()) {
       board.print();
    } else {
        for (int row = 1; row <= board.size(); row++) {
            if (board.safe(row, col)) {
                board.place(row, col);
                explore(b, col + 1);
                board.remove(row, col);
            }
        }
    }
}

We need some code in the solve method that starts the recursion in column 1 and then we're done:

public void solve(Board solution) {
    explore(solution, 1);
}

The project contained in queens.zip shows this code in action. Run Queens.java for an entirely text-based version and Queens2.java for a graphical demonstration.