One Pager Cheat Sheet

• Backtracking is a powerful algorithm used to explore all potential solutions to a problem and identify those that satisfy a constraint, making it a useful tool for Combinatorial, Path Finding, and Sudoku Solving.
• The algorithm of backtracking creates a search tree and explores it in a depth first manner to find candidate solutions that can be pruned to become more efficient.
• Finding all possible combinations of items from a set of size N is an example of a combinatorics problem that can be solved with a pseudo code solution.
• The algorithmic solution builds an implicit search tree starting with an empty set, and explores certain paths while abandoning others in order to find all possible combinations in an efficient manner.
• We can modify our combosN code to find all N combinations whose sum < S, with an even more efficient version when the array is sorted.
• We can use backtracking to enumerate all possible paths from a start location to a target location in a square grid by making alternating "up" and "right" moves.
• By backtracking through all possible paths of an m * n grid, this code provides a simple C++ implementation to list out all paths from a given cell, and prints them if they reach the goal/target cell.
• Find a path through a maze by abandoning earlier on in the search any paths leading to cells forbidden to the robot.
• The C++ code implements an algorithm which backtracks from pits or previous cells to enumerate all paths through a binary 2D array, which serves as a representation of the maze.
• Solving Sudoku involves using backtracking to fill out an N * N grid with numbers from 1 .. N so that no row or column contains a repeated number.
• We can solve Sudoku using a simple backtracking routine and an accompanying C++ implementation.
• Backtracking is an important technique for enumerating all possible solutions satisfying a given constraint and software engineers should beware of its complexity and carefully plan how to optimize their code before using it.
• Step b of Combos should be changed to unconditionally display the set and no additional checks should be made to determine the size, so that all possible combinations of any size can be printed.
• There are 70 distinct paths between (0,0) and (4,4) in a 5x5 grid, which can be calculated using the factorial formula to calculate the number of ways to arrange the 24 distinct paths that must be traveled.