backtracking

README

Backtracking

Backtracking is a commonly used recursive technique in which the solution is built incrementally while simultaneously checking for problem conditions at each step. If the conditions are unmet, the algorithm backtracks to the previous step and tries an alternative approach. The algorithm terminates with success if the final goal is reached while satisfying the problem conditions at each step. On the other hand, if all alternatives have been exhausted and the algorithm has backtracked to the starting point, it terminates with failure.

Backtracking can be compared to how a person solves a maze or searches for an exit in an unfamiliar mall. This technique guarantees a solution if one exists since it involves trying out every possibility until success or failure is achieved.

Implementation

Backtracking algorithms are typically implemented in these steps:

1. Prune invalid approaches when possible.
2. Generate a partial solution by iterating through available alternatives.
3. Check the validity of the selected alternative according to the problem conditions and rules.
4. Check for solution completion when required.

Complexity

The time complexity of backtracking algorithms may vary depending on the problem at hand. However, they generally require iterating through possible alternatives and checking for validity at each step. Although backtracking may be the only feasible approach to certain problems, it does not always guarantee an optimal solution. Pruning, which involves eliminating known invalid options before iterating through the alternatives, is an effective technique to improve the time complexity of backtracking algorithms.

Application

Backtracking is widely used to solve board games and computers use it to select their next moves. Furthermore, the backtracking technique is also applied to graphs and trees through the use of Depth First Search. It also has applications in object detection and image processing.

Rehearsal

Permutations

• Permutations, Solution
• Generate Parentheses, Solution
• Phone Letter Combinations, Solution
• Maze, Solution
• Sudoku, Solution
• N Queens, Solution

Documentation

Index

• func GenerateParentheses(n int) []string
• func Maze(m, n int, walls [][2]int, start, finish [2]int) string
• func Permutations(input []int) [][]int
• func PhoneLetterCombinations(digits string) []string
• func Sudoku(board [][]int) bool
• type Chessboard
  • func NQueens(n int) []Chessboard

Functions

func GenerateParentheses

func GenerateParentheses(n int) []string

GenerateParentheses solves the problem in O(2^n) time and O(n) space.

func Maze

func Maze(m, n int, walls [][2]int, start, finish [2]int) string

Maze solves the problem in O(mn) time and O(mn) space complexity.

func Permutations

func Permutations(input []int) [][]int

Permutations solves the problem in O(n!) time and O(n) space.

func PhoneLetterCombinations

func PhoneLetterCombinations(digits string) []string

PhoneLetterCombinations solves the problem in O(3^n) time and O(3^n) space.

func Sudoku

func Sudoku(board [][]int) bool

Sudoku solves the problem in O(9^(n*n)) time and O(n*n) space.

Types

type Chessboard

type Chessboard [][]int

Chessboard represents a chessboard.

func NQueens

func NQueens(n int) []Chessboard

NQueens solves the problem in O(n!) time and O(n) space.