avatarAndre Ye

Summary

The article provides an in-depth explanation of backtracking as a technique for solving programming interview questions, illustrated through examples such as the N-Queens problem, flight itinerary reconstruction, and Sudoku.

Abstract

Backtracking is an algorithmic technique that is particularly useful for solving search problems encountered in programming interviews. The method involves exploring possible solutions recursively and abandoning paths as soon as they are determined to be invalid, thus reducing the search space. The article breaks down the backtracking process into three components: a recursive function, a mechanism to test partial solutions, and a check for solution completeness and validity. It demonstrates the application of backtracking through three examples: the N-Queens problem, where the challenge is to place N queens on a chessboard such that no two queens threaten each other; the flight itinerary problem, which involves reconstructing an itinerary from a list of flights; and Sudoku, a popular number-placement puzzle. By visually explaining these examples, the article aims to enhance readers' understanding of backtracking and its practical application in solving complex problems.

Opinions

  • Backtracking is presented as an efficient method for problem-solving in interviews due to its ability to systematically explore and eliminate invalid solution paths.
  • The author emphasizes that backtracking is most effective when partial solutions can be constructed and validated, and when there is a clear criterion for solution completeness.
  • The article suggests that backtracking is not only applicable to traditional algorithmic problems but also to real-world scenarios like reconstructing a flight itinerary.
  • While acknowledging that there may be more efficient algorithms for specific problems, the author advocates for backtracking as a versatile and reliable approach that can be applied broadly.
  • The author appreciates the "beauty" and "cleanness" of backtracking algorithms, particularly in their ability to automatically build a search tree and find optimal solutions.

Backtracking: How to Approach Search Programming Interview Questions

Explained visually in three examples: N queens, flight itinerary, and Sudoku

Image source: author

Backtracking is an effective method for solving commonly asked programming interview algorithmic problems. Backtracking depth-searches for solutions and then backtracks to the most recent valid path as soon as an end node is reached (i.e., we can proceed no further). This method reduces the search space since any paths we know are invalid are eliminated from the solution space.

However, using backtracking requires the ability to test partial solutions — the method can’t find global optimum if there’s no progress indicator that the solution path we’re currently on leads to a solution or not. However, something like Sudoku can be solved with backtracking — it is clear immediately if the current solution path is invalid if, say, there are two of the same number in a row, column, or square.

Backtracking consists of three parts: a recursive function, which takes in a solution set (which may be incomplete n), a mutation or addition to n that adds on to set n, and a completion and validity check, which checks a solution set mutation’s completion (is the solution complete?) and validity (does it meet the requirements for validity? With the currently filled-in values, is this an acceptable solution?).

Image source: author

Backtracking automatically creates a clean and computationally efficient search tree based on very simple elements.

In this article, I’ll demonstrate, along with visuals, how backtracking can be used to solve three classic programming interview-style search questions.

N-Queens Problem

The N-queens problem is a classic backtracking problem: given a chessboard of N by N size, how many ways can you arrange N queen pieces such that they do not threaten each other (one is not in the line of one queen’s column, row, or diagonals)?

As an example, this grid is an invalid move, because at least two of the eight queens is in another’s row, column, or diagonal, marked by a red square.

The brute-force solution to the problem is to try every single combination of N queens in each of the N by N spots — N² choose N possibilities.

Graphing it out, where x represents N and y represents the number of possibilities to search through, it skyrockets.

Image source: author

Just for a standard 8-by-8 grid, there are 4,426,165,368 combinations, which is painfully slow. This can be partially improved by not putting two queens ever in the same row or column, but we still need to iterate over each row and each cell in each row — a runtime of O(N²), not fast enough.

Now, let’s go through a checklist of questions to determine if backtracking can help.

Can partial solutions be constructed?

Yes, partial solutions can be constructed. By placing a certain number of queens on the board, we can partially construct a solution.

Can those partial solutions be verified as valid or invalid?

Yes, we can verify whether a partial solution is valid or invalid by checking if any two queens threaten each other. This can be sped up by acknowledging that the original queens do not threaten each other, and only checking if a newly added queen threatens any of the other queens.

Can the solution be verified as complete?

Yes, the solution is complete when all N queens have been placed on the board. What’s great about backtracking is that when the solution is complete, it is also correct, because all incorrect solution paths have been ruled out beforehand.

Let’s construct a backtracking approach to solve the N-queens problem in faster time.

Function n_queens:

  1. Intake N and board, a list of numbers.
  2. Initialize board as an empty list if it is not specified, and count to 0.
  3. For each column X in N,
  4. >> Add column X’s index to board.
  5. >> If board is valid, add the output of n_queens with inputs N and board to count (this will initialize another loop of the function, and is the tunneling or tree-building process of backtracking. Since the partial solution is considered valid in this case, it initiates another instance of function n_queens).
  6. >> Otherwise, remove the column X.
  7. Return count.
Telescoping tree-building

The function to evaluate if a board is valid or not is as follows:

  1. Intake board, a list of numbers where each number corresponds to one column.
  2. The most recently added queen’s row is the current length of the board, minus one (because indexes start from 0), and the current queen’s column is the last element of the board.
  3. For each row R and column C in the board (which consists only of placed queens),
  4. >> Find the difference between the newly added queen’s column and the current column C. If it equals 0 (the two columns are the same), return False and break from the function.
  5. >> Find the difference between the newly added queen’s row and the current row R. If it equals 0 (the two rows are the same), return False and break from the function.
  6. Otherwise, return True.

By recursively iterating new instances of a building function within a building function, backtracking is able to build a smart tree that doesn’t continue where the situation is hopeless: it is process-based instead of outcome-based.

The results, where the index indicates the value of N:

1, 1, 0, 0, 2, 10, 4, 40, 92, 352

The Flight Itinerary Problem

Given an unordered list of someone’s flights, each represented with an (origin, destination) pair and a starting airport, compute the person’s itinerary. If none exists, return na — all flights must be used in the itinerary.

Let us take, as an example, these flights:

  • HNL ➔ AKL
  • YUL ➔ ORD
  • SFO ➔ HNL
  • ORD ➔ SFO

The brute force solution to the problem is to try every permutation of flights and verify if it is a valid itinerary, making it O(n!) time.

Let’s ask our three-question checklist again for using backtracking.

Can partial solutions be constructed?

Yes, partial solutions can be constructed by listing out an incomplete itinerary, such as SFO ➔ HNL ➔ ORD ➔ ?.

Can those partial solutions be verified as valid or invalid?

The solution can be verified invalid if there are no flights leaving from the last destination in the itinerary and there are still flights remaining that can be taken. Since all flights must be used, we’ve reached an end node.

Can the solution be verified as complete?

Yes, the solution is complete when the itinerary uses all the flights.

Constructing the logic of the solution:

A function get_itinerary:

  1. Intake an unordered list flights with elements in the form (origin, destination), and current_itinerary, a list of the itinerary (where the first element is the starting airport and the second is the destination of the first flight and the origin of the second flight, and so on).
  2. If the flights have been all used up, return current_itinerary.
  3. The last_stop will be equal to the last element of current_itinerary.
  4. For each (origin, destination) pair in flights,
  5. >> Add the destination to the current_itinerary.
  6. >> If the origin is equal to last_stop (this is the check, and makes sure that the flight is a valid connection),
  7. >> >> Return another run of get_itinerary with all the flights except the current (origin, destination) pair, and break from the function.
  8. >> Otherwise, remove the most recent destination.
  9. Return None if none of the previous tree searches were able to return any solution.
A reduced version of what a backtrack-built tree might look like

You can probably observe that a large part of implementing backtracking has to do with using a function many times and building an automated, recursive search tree.

Note that for this particular problem, there is a much more efficient way to solve it. We just used backtracking as an example. In reality, a faster way would be just to take the starting airport (e.g., SFO), find the linking airport in the flights (SFO to HNL), and add whatever the destination is to the itinerary, recursively carrying on.

Sudoku

Can we use backtracking to solve a standard Sudoku puzzle?

Can partial solutions be constructed?

Yes, we can partially fill in positions on the Sudoku board.

Can those partial solutions be verified as valid or invalid?

Yes, if the partial solution has any numbers that have the same number in a row, column, or square, the solution is invalid. Otherwise, it is valid.

Can the solution be verified as complete?

Yes, the solution is complete when the entire Sudoku board is filled.

Let’s try filling each empty cell one by one, and backtrack once we hit an invalid state. That’ll look something like this:

Function sudoku:

  1. Intake the variable board, which is an array, each value representing a cell on the Sudoku board.
  2. If the board is complete, return the board and break from the function.
  3. Let r and c represent the row and column of the first empty value on the board.
  4. For each value i in [1, 2, 3, 4, 5, 6, 7, 8, 9],
  5. >> Set the rth row and cth column cell to i.
  6. >> If the board is valid so far,
  7. >> >> Run another instance of sudoku given board.
How a 4x4 version of Sudoku might work with backtracking

The simplicity and cleanness of using backtracking to solve something as complex as a difficult Sudoku board are beautiful. Just outline a recursive function, a partial solution check, and a function to evaluate if a solution is complete, and the program will automatically build a tree for you and find the best solution, if any.

Conclusion

I hope this article was able to give you an understanding of how outlining three simple components of backtracking can outline rules for the program to sort itself out and find the best solution.

Programming
Coding
Data Science
Interview
Strategy
Recommended from ReadMedium