📄️ Backtracking algorithms
The N-Queens Problem is a classic problem where the objective is to place `N` queens on an `N x N` chessboard such that no two queens can attack each other. A queen can attack any other piece in the same row, column, or diagonal, making it challenging to place all `N` queens without conflict.
📄️ M-Coloring Problem
The M-Coloring problem is a backtracking algorithm where the task is to assign colors to vertices of a graph so that no two adjacent vertices share the same color. The goal is to find if it is possible to color the graph using at most M colors.
📄️ N-Queens
Overview and implementation of the N-Queens problem using a backtracking algorithm.
📄️ What is Backtracking?
Backtracking is a systematic algorithmic method for solving problems where you need to explore all possible configurations (solution candidates) and discard those that fail to satisfy the given constraints. It is widely used to solve constraint satisfaction problems such as puzzles, combinatorial optimization problems, and decision problems.
📄️ Hamiltonian Path and Cycle
Hamiltonian Path and Cycle problems are a classic graph theory problem where the task is to find a path or cycle that visits every vertex exactly once. These problems are NP-complete and are widely used in various applications such as route planning, logistics, and genome sequencing.
📄️ Importance of Backtracking
Backtracking is a systematic algorithmic method for solving problems where you need to explore all possible configurations (solution candidates) and discard those that fail to satisfy the given constraints. It is widely used to solve constraint satisfaction problems such as puzzles, combinatorial optimization problems, and decision problems.
📄️ Bron-Kerbosch Algorithm
The Bron-Kerbosch algorithm is a backtracking algorithm used to find all maximal cliques in an undirected graph. Known for its efficiency, especially on sparse graphs, it is widely applied in social network analysis, bioinformatics, and computational chemistry. The algorithm can be optimized with pivoting to reduce recursive calls and improve performance.
📄️ Backtracking
In this blog post, we'll explore the backtracking algorithm, a powerful technique for solving combinatorial problems by building solutions incrementally.
📄️ Tiling Problem
The Tiling Problem involves determining the number of ways to tile a 2×n grid using 1×2 dominoes, solved efficiently using dynamic programming.
📄️ Sudoku Solver
Solve a 9×9 Sudoku puzzle using backtracking with constraint propagation. A classic constraint-satisfaction problem solved by trying digits and backtracking on conflicts.
📄️ Word Search
Solve the Word Search problem using DFS with backtracking on a 2D character grid. Covers both Word Search I (single word) and Word Search II (multiple words with Trie).
📄️ Permutations & Combinations
Generate all permutations and combinations of a set using backtracking state-tree exploration. Covers both with and without duplicates.
📄️ Subset Sum & Combination Sum
Explore all subsets and find combinations that sum to a target using decision-tree backtracking. Covers Subset Sum, Combination Sum I, II, and III.