WikiGalaxy
WikiGalaxy💙Blue💛🌹
Personalize
Backtracking Problem Solving Approach
Introduction:
Backtracking is a systematic method for exploring all possible configurations of a search space. It is used to solve problems incrementally, building candidates for solutions and abandoning candidates as soon as it becomes clear that they cannot be extended to a complete solution.
Method 1: N-Queens Problem
Concept:
The N-Queens problem involves placing N queens on an N×N chessboard so that no two queens threaten each other. The solution involves backtracking to explore possible placements and backtracking when a conflict arises.
Step 1: Place Queen in the first column.
Step 2: Move to the next column and place Queen in a safe row.
Step 3: If no safe row is found, backtrack to the previous column.
Step 4: Continue until all Queens are placed or no solution is possible.
class NQueens {
final int N = 4;
void solveNQueens() {
int board[][] = new int[N][N];
if (solveNQUtil(board, 0) == false) {
System.out.print("Solution does not exist");
return;
}
printSolution(board);
}
boolean solveNQUtil(int board[][], int col) {
if (col >= N) return true;
for (int i = 0; i < N; i++) {
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1)) return true;
board[i][col] = 0;
}
}
return false;
}
boolean isSafe(int board[][], int row, int col) {
for (int i = 0; i < col; i++)
if (board[row][i] == 1) return false;
for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1) return false;
for (int i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1) return false;
return true;
}
void printSolution(int board[][]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + board[i][j] + " ");
System.out.println();
}
}
}
Method 2: Sudoku Solver
Concept:
Sudoku solving using backtracking involves filling in the empty cells one by one, ensuring that the number is valid according to Sudoku rules. If a cell cannot be filled, the algorithm backtracks to the previous cell.
Step 1: Find an empty cell.
Step 2: Try placing numbers 1 to 9 in the cell.
Step 3: Check if the number is valid.
Step 4: If valid, move to the next empty cell.
Step 5: If not valid, backtrack to the previous cell.
class SudokuSolver {
final int N = 9;
boolean solveSudoku(int grid[][]) {
int row = -1, col = -1;
boolean isEmpty = true;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 0) {
row = i;
col = j;
isEmpty = false;
break;
}
}
if (!isEmpty) break;
}
if (isEmpty) return true;
for (int num = 1; num <= N; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
if (solveSudoku(grid)) return true;
grid[row][col] = 0;
}
}
return false;
}
boolean isSafe(int grid[][], int row, int col, int num) {
for (int x = 0; x < N; x++)
if (grid[row][x] == num || grid[x][col] == num) return false;
int startRow = row - row % 3, startCol = col - col % 3;
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (grid[i+startRow][j+startCol] == num) return false;
return true;
}
}
Method 3: Subset Sum Problem
Concept:
The Subset Sum problem involves determining if there is a subset of a given set of numbers that adds up to a specific target sum. Backtracking is used to explore subsets and abandon paths that exceed the target.
Step 1: Start with an empty subset.
Step 2: Add the next element to the subset.
Step 3: Check if the subset sum equals the target.
Step 4: If not, backtrack and try the next element.
Step 5: Continue until a solution is found or all elements are tried.
class SubsetSum {
boolean isSubsetSum(int set[], int n, int sum) {
if (sum == 0) return true;
if (n == 0) return false;
if (set[n-1] > sum) return isSubsetSum(set, n-1, sum);
return isSubsetSum(set, n-1, sum) || isSubsetSum(set, n-1, sum-set[n-1]);
}
}
Method 4: Hamiltonian Cycle
Concept:
A Hamiltonian cycle in a graph is a cycle that visits each vertex exactly once. The backtracking approach tries to build the cycle incrementally and abandons paths that revisit vertices.
Step 1: Start at a vertex and add it to the path.
Step 2: Try adding the next vertex to the path.
Step 3: Check if the vertex creates a cycle.
Step 4: If not, backtrack and try the next vertex.
Step 5: Continue until a cycle is found or all vertices are tried.
class HamiltonianCycle {
final int V = 5;
int path[];
boolean isSafe(int v, int graph[][], int path[], int pos) {
if (graph[path[pos - 1]][v] == 0) return false;
for (int i = 0; i < pos; i++)
if (path[i] == v) return false;
return true;
}
boolean hamCycleUtil(int graph[][], int path[], int pos) {
if (pos == V) return graph[path[pos - 1]][path[0]] == 1;
for (int v = 1; v < V; v++) {
if (isSafe(v, graph, path, pos)) {
path[pos] = v;
if (hamCycleUtil(graph, path, pos + 1)) return true;
path[pos] = -1;
}
}
return false;
}
int hamCycle(int graph[][]) {
path = new int[V];
for (int i = 0; i < V; i++) path[i] = -1;
path[0] = 0;
if (!hamCycleUtil(graph, path, 1)) {
System.out.println("Solution does not exist");
return 0;
}
printSolution(path);
return 1;
}
void printSolution(int path[]) {
System.out.println("Solution Exists: Following is one Hamiltonian Cycle");
for (int i = 0; i < V; i++) System.out.print(" " + path[i] + " ");
System.out.println(" " + path[0] + " ");
}
}
Method 5: Knight's Tour
Concept:
The Knight's Tour problem involves moving a knight on a chessboard such that it visits every square exactly once. Backtracking is used to explore possible moves and backtrack when a move leads to a dead end.
Step 1: Place the knight on the first square.
Step 2: Try all possible moves from the current square.
Step 3: Check if the move is valid.
Step 4: If valid, move the knight and continue.
Step 5: If not valid, backtrack to the previous square.
class KnightsTour {
static int N = 8;
boolean isSafe(int x, int y, int sol[][]) {
return (x >= 0 && x < N && y >= 0 && y < N && sol[x][y] == -1);
}
boolean solveKT() {
int sol[][] = new int[8][8];
for (int x = 0; x < N; x++)
for (int y = 0; y < N; y++)
sol[x][y] = -1;
int xMove[] = {2, 1, -1, -2, -2, -1, 1, 2};
int yMove[] = {1, 2, 2, 1, -1, -2, -2, -1};
sol[0][0] = 0;
if (!solveKTUtil(0, 0, 1, sol, xMove, yMove)) {
System.out.println("Solution does not exist");
return false;
} else printSolution(sol);
return true;
}
boolean solveKTUtil(int x, int y, int movei, int sol[][], int xMove[], int yMove[]) {
int k, next_x, next_y;
if (movei == N * N) return true;
for (k = 0; k < 8; k++) {
next_x = x + xMove[k];
next_y = y + yMove[k];
if (isSafe(next_x, next_y, sol)) {
sol[next_x][next_y] = movei;
if (solveKTUtil(next_x, next_y, movei + 1, sol, xMove, yMove)) return true;
else sol[next_x][next_y] = -1;
}
}
return false;
}
void printSolution(int sol[][]) {
for (int x = 0; x < N; x++) {
for (int y = 0; y < N; y++)
System.out.print(sol[x][y] + " ");
System.out.println();
}
}
}
Method 6: Permutations of a String
Concept:
Generating permutations of a string involves rearranging its characters in all possible ways. Backtracking involves swapping characters and exploring further permutations recursively.
Step 1: Fix the first character and swap it with each character.
Step 2: Recursively generate permutations of the remaining characters.
Step 3: Swap back to restore the original string.
Step 4: Repeat for each character.
class Permutations {
void permute(String str, int l, int r) {
if (l == r) System.out.println(str);
else {
for (int i = l; i <= r; i++) {
str = swap(str, l, i);
permute(str, l + 1, r);
str = swap(str, l, i);
}
}
}
String swap(String a, int i, int j) {
char temp;
char[] charArray = a.toCharArray();
temp = charArray[i];
charArray[i] = charArray[j];
charArray[j] = temp;
return String.valueOf(charArray);
}
}
Method 7: Rat in a Maze
Concept:
The Rat in a Maze problem involves finding a path for the rat from the start to the end of the maze. Backtracking is used to explore paths and backtrack when a dead end is reached.
Step 1: Start at the entrance of the maze.
Step 2: Move in one direction until a dead end or exit is reached.
Step 3: If a dead end is reached, backtrack to the last junction.
Step 4: Try a different direction.
Step 5: Continue until the exit is found or all paths are tried.
class RatMaze {
final int N = 4;
boolean isSafe(int maze[][], int x, int y) {
return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}
boolean solveMaze(int maze[][]) {
int sol[][] = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}};
if (!solveMazeUtil(maze, 0, 0, sol)) {
System.out.println("Solution doesn't exist");
return false;
}
printSolution(sol);
return true;
}
boolean solveMazeUtil(int maze[][], int x, int y, int sol[][]) {
if (x == N - 1 && y == N - 1) {
sol[x][y] = 1;
return true;
}
if (isSafe(maze, x, y)) {
sol[x][y] = 1;
if (solveMazeUtil(maze, x + 1, y, sol)) return true;
if (solveMazeUtil(maze, x, y + 1, sol)) return true;
sol[x][y] = 0;
return false;
}
return false;
}
void printSolution(int sol[][]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + sol[i][j] + " ");
System.out.println();
}
}
}
Method 8: Word Search
Concept:
The Word Search problem involves finding a word in a 2D grid of letters. Backtracking is used to explore paths from each letter, checking if the word can be formed by adjacent letters.
Step 1: Start from each letter in the grid.
Step 2: Check if the word can start with the current letter.
Step 3: Move to adjacent letters and continue checking.
Step 4: If the word is not found, backtrack to the previous letter.
Step 5: Continue until the word is found or all letters are tried.
class WordSearch {
boolean exist(char[][] board, String word) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
if (board[i][j] == word.charAt(0) && search(board, word, i, j, 0)) {
return true;
}
}
}
return false;
}
boolean search(char[][] board, String word, int i, int j, int index) {
if (index == word.length()) return true;
if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
return false;
}
char temp = board[i][j];
board[i][j] = ' ';
boolean found = search(board, word, i + 1, j, index + 1) ||
search(board, word, i - 1, j, index + 1) ||
search(board, word, i, j + 1, index + 1) ||
search(board, word, i, j - 1, index + 1);
board[i][j] = temp;
return found;
}
}
Method 9: Combination Sum
Concept:
The Combination Sum problem involves finding all combinations of numbers that add up to a target sum. Backtracking is used to explore combinations and backtrack when a combination exceeds the target.
Step 1: Start with an empty combination.
Step 2: Add the next number to the combination.
Step 3: Check if the combination sum equals the target.
Step 4: If not, backtrack and try the next number.
Step 5: Continue until all combinations are tried.
class CombinationSum {
List> combinationSum(int[] candidates, int target) {
List> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), candidates, target, 0);
return result;
}
void backtrack(List> result, List tempList, int[] nums, int remain, int start) {
if (remain < 0) return;
else if (remain == 0) result.add(new ArrayList<>(tempList));
else {
for (int i = start; i < nums.length; i++) {
tempList.add(nums[i]);
backtrack(result, tempList, nums, remain - nums[i], i);
tempList.remove(tempList.size() - 1);
}
}
}
}
Method 10: Palindrome Partitioning
Concept:
Palindrome Partitioning involves partitioning a string such that every substring is a palindrome. Backtracking is used to explore partitions and check if each substring is a palindrome.
Step 1: Start with an empty partition.
Step 2: Add the next substring to the partition.
Step 3: Check if the substring is a palindrome.
Step 4: If not, backtrack and try the next substring.
Step 5: Continue until all partitions are tried.
class PalindromePartitioning {
List> partition(String s) {
List> result = new ArrayList<>();
backtrack(result, new ArrayList<>(), s, 0);
return result;
}
void backtrack(List> result, List tempList, String s, int start) {
if (start == s.length()) result.add(new ArrayList<>(tempList));
else {
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i)) {
tempList.add(s.substring(start, i + 1));
backtrack(result, tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
}
boolean isPalindrome(String s, int low, int high) {
while (low < high)
if (s.charAt(low++) != s.charAt(high--)) return false;
return true;
}
}
