Backtracking in Java

Backtracking is a powerful algorithm used to solve problems that involve searching for a solution among multiple possibilities. It is used in data structures and algorithms with Java to find a path from the start to the goal in a tree or graph. Backtracking is a type of recursive algorithm that can be used to solve problems such as the N-Queens problem, Hamiltonian Cycle problem, and the Knapsack problem. This article will cover the basics of backtracking, how it is used in data structures and algorithms with Java, and provide coding exercises to test the reader’s understanding.

What is Backtracking?

Backtracking is an algorithmic technique used to find a solution to a problem by trying each possibility in turn until a solution is found. It is a type of recursive algorithm, meaning that it can be used to solve problems by breaking them down into smaller subproblems and recursively solving those subproblems. Backtracking is often used in data structures and algorithms with Java to solve problems such as the N-Queens problem, Hamiltonian Cycle problem, and the Knapsack problem.

The Backtracking Algorithm

The backtracking algorithm is relatively simple. It follows a depth-first search approach and works by making an initial guess and then exploring it until it reaches a solution or a dead end. If the guess is wrong, the algorithm backtracks, or “unwinds”, the previous guess and makes a new one. This process is repeated until a solution is found.

The algorithm can be summarized as follows:

1. Make an initial guess
2. Check if the guess is valid
3. If the guess is valid, explore it further
4. If the guess is not valid, backtrack
5. Repeat until a solution is found

How Backtracking is Used in Data Structures and Algorithms with Java

Backtracking is a powerful technique used in data structures and algorithms with Java. It can be used to solve problems such as the N-Queens problem, Hamiltonian Cycle problem, and the Knapsack problem.

The N-Queens Problem

The N-Queens problem is a classic problem in computer science. The goal of the problem is to place N queens on an NxN chessboard such that no two queens can attack each other. This problem can be solved using backtracking.

The algorithm starts by placing the first queen in the first row, then the second queen in the second row, and so on. After each queen is placed, a check is done to make sure that no two queens can attack each other. If two queens can attack each other, then the algorithm backtracks and tries a different position for the last placed queen. This process is repeated until a solution is found.

The following Java code illustrates the backtracking algorithm used to solve the N-Queens problem:

public class NQueens { 
    private static final int N = 8; 
    private static int[][] chessboard = new int[N][N]; 
 
    // Function to check if a queen can be placed 
    private static boolean isValid(int row, int col) { 
        // Check if any queen is placed in the same row 
        for (int i = 0; i < col; i++) { 
            if (chessboard[row][i] == 1) { 
                return false; 
            } 
        } 
 
        // Check if any queen is placed in the same diagonal 
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) { 
            if (chessboard[i][j] == 1) { 
                return false; 
            } 
        } 
 
        // Check if any queen is placed in the same diagonal 
        for (int i = row, j = col; i < N && j >= 0; i++, j--) { 
            if (chessboard[i][j] == 1) { 
                return false; 
            } 
        } 
 
        return true; 
    } 
 
    // Function to solve N-Queens problem using backtracking 
    private static boolean solveNQueensUtil(int col) { 
        // Base case: If all queens are placed 
        if (col >= N) { 
            return true; 
        } 
 
        // Consider this column and try placing this queen in all rows one by one 
        for (int i = 0; i < N; i++) { 
            // Check if queen can be placed on board[i][col] 
            if (isValid(i, col)) { 
                // Place this queen in board[i][col] 
                chessboard[i][col] = 1; 
 
                // Recur to place rest of the queens 
                if (solveNQueensUtil(col + 1)) { 
                    return true; 
                } 
 
                // If placing queen in board[i][col] doesn't lead to a solution, then backtrack 
                chessboard[i][col] = 0; // BACKTRACK 
            } 
        } 
 
        return false; 
    } 
 
    // Function to solve N-Queens problem 
    public static void solveNQueens() { 
        if (solveNQueensUtil(0)) { 
            for (int i = 0; i < N; i++) { 
                for (int j = 0; j < N; j++) { 
                    System.out.print(chessboard[i][j] + " "); 
                } 
                System.out.println(); 
            } 
        } else { 
            System.out.println("No solution exists"); 
        } 
    } 
 
    // Driver code 
    public static void main(String args[]) { 
        solveNQueens(); 
    } 
}

The Hamiltonian Cycle Problem

The Hamiltonian Cycle problem is another classic problem in computer science. The goal of the problem is to find a Hamiltonian cycle in a graph, which is a cycle that visits each vertex exactly once. This problem can also be solved using backtracking.

The algorithm starts by choosing an initial vertex and then exploring the edges from that vertex. After each step, a check is done to make sure that the current path does not contain a cycle. If the path does contain a cycle, then the algorithm backtracks and tries a different path. This process is repeated until a solution is found.

The following Java code illustrates the backtracking algorithm used to solve the Hamiltonian Cycle problem:

public class HamiltonianCycle { 
    private static final int V = 5; 
    private int[] path = new int[V]; 
 
    // A utility function to check if the current path has a solution or not 
    private boolean isSafe(int v, int graph[][], int path[], int pos) { 
        // Check if the current node is already present in the path 
        if (graph[path[pos - 1]][v] == 0) { 
            return false; 
        } 
 
        // Check if the current node is already present in the path 
        for (int i = 0; i < pos; i++) { 
            if (path[i] == v) { 
                return false; 
            } 
        } 
 
        return true; 
    } 
 
    // A recursive function to find a Hamiltonian Cycle in the given graph 
    private boolean hamCycleUtil(int graph[][], int path[], int pos) { 
        // Base case: If all vertices are included in the path 
        if (pos == V) { 
            // Check if the last node is connected to the first node 
            if (graph[path[pos - 1]][path[0]] == 1) { 
                return true; 
            } else { 
                return false; 
            } 
        } 
 
        // Try different vertices as a next candidate in Hamiltonian Cycle. 
        // We don't try for 0 as we included 0 as starting point in in hamCycle() 
        for (int v = 1; v < V; v++) { 
            // Check if this vertex can be added to the Hamiltonian Cycle 
            if (isSafe(v, graph, path, pos)) { 
                path[pos] = v; 
 
                // Recur to construct rest of the path 
                if (hamCycleUtil(graph, path, pos + 1)) { 
                    return true; 
                } 
 
                // If adding vertex v doesn't lead to a solution, then backtrack 
                path[pos] = -1; // BACKTRACK 
            } 
        } 
 
        // If no vertex can be added to the Hamiltonian Cycle constructed so far, then return false 
        return false; 
    } 
 
    // This function solves the Hamiltonian Cycle problem using Backtracking. 
    public boolean hamCycle(int[][] graph) { 
        // Initialize the path so that all vertices are not included in the path 
        for (int i = 0; i < V; i++) { 
            path[i] = -1; 
        } 
 
        // Start the path from the first vertex 
        path[0] = 0; 
        if (hamCycleUtil(graph, path, 1) == false) { 
            System.out.println("Solution does not exist"); 
            return false; 
        } 
 
        // Print the solution 
        printSolution(); 
        return true; 
    } 
 
    // Function to print the solution 
    public void printSolution() { 
        System.out.println("Hamiltonian Cycle: "); 
        for (int i = 0; i < V; i++) { 
            System.out.print(path[i] + " "); 
        } 
 
        // Print the first node to complete the cycle 
        System.out.println(path[0]); 
    } 
 
    // Driver code 
    public static void main(String[] args) { 
        HamiltonianCycle hamCycle = new HamiltonianCycle(); 
        int[][] graph1 = { { 0, 1, 0, 1, 0 }, 
                            { 1, 0, 1, 1, 1 }, 
                            { 0, 1, 0, 0, 1 }, 
                            { 1, 1, 0, 0, 1 }, 
                            { 0, 1, 1, 1, 0 } }; 
 
        hamCycle.hamCycle(graph1); 
    } 
}

The Knapsack Problem

The Knapsack problem is yet another classic problem in computer science. The goal of the problem is to find the subset of items that will maximize the value of a knapsack given a certain weight limit. This problem can also be solved using backtracking.

The algorithm starts by considering the first item and then exploring the possibilities of including or excluding that item. After each step, a check is done to make sure that the current subset of items is not exceeding the weight limit. If the current subset is exceeding the weight limit, then the algorithm backtracks and tries a different subset. This process is repeated until a solution is found.

The following Java code illustrates the backtracking algorithm used to solve the Knapsack problem:

public class Knapsack { 
    private static int maxValue(int[] values, int[] weights, int capacity) { 
        int[][] dp = new int[values.length + 1][capacity + 1]; 
 
        for (int i = 1; i <= values.length; i++) { 
            for (int j = 1; j <= capacity; j++) { 
                if (weights[i - 1] <= j) { 
                    dp[i][j] = Math.max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]); 
                } else { 
                    dp[i][j] = dp[i - 1][j]; 
                } 
            } 
        } 
 
        return dp[values.length][capacity]; 
    } 
 
    // Driver code 
    public static void main(String args[]) { 
        int[] values = { 60, 100, 120 }; 
        int[] weights = { 10, 20, 30 }; 
        int capacity = 50; 
  
        System.out.println(maxValue(values, weights, capacity)); 
    } 
}

Conclusion

In conclusion, backtracking is a powerful technique used in data structures and algorithms with Java to solve problems such as the N-Queens problem, Hamiltonian Cycle problem, and the Knapsack problem. Backtracking works by making an initial guess and then exploring it until it reaches a solution or a dead end. If the guess is wrong, the algorithm backtracks, or “unwinds”, the previous guess and makes a new one. The backtracking algorithm is relatively simple and can be thought of as a depth-first search approach.

Exercises

public class NQueens { 
	public static boolean solveNQueens(int n, int row, int[] board) { 
		if (row == n) { 
			return true; 
		}
		for (int col = 0; col < n; col++) { 
			if (isSafe(row, col, board)) { 
				board[row] = col; 
				if (solveNQueens(n, row + 1, board)) 
					return true; 
				board[row] = -1; 
			} 
		} 
		return false; 
	} 
	
	public static boolean isSafe(int row, int col, int[] board) { 
		for (int i = 0; i < row; i++) { 
			if (board[i] == col || (i - row) == (board[i] - col) || (i - row) == (col - board[i])) { 
				return false; 
			} 
		} 
		return true; 
	} 
	
	public static void main(String args[]) { 
		int N = 8; 
		int[] board = new int[N]; 
		Arrays.fill(board, -1); 
		if (solveNQueens(N, 0, board)) { 
			for (int i = 0; i < N; i++) { 
				for (int j = 0; j < N; j++) { 
					if (board[i] == j) { 
						System.out.print("Q "); 
					} else { 
						System.out.print("_ "); 
					} 
				} 
				System.out.println(); 
			} 
		} else { 
			System.out.println("Solution does not exist"); 
		} 
	} 
}

public class KnightsTour { 
	public static boolean isSafe(int x, int y, int sol[][]) { 
		return (x >= 0 && x < 8 && y >= 0 && 
				y < 8 && sol[x][y] == -1); 
	} 
	public static void printSolution(int sol[][]) { 
		for (int x = 0; x < 8; x++) { 
			for (int y = 0; y < 8; y++) 
				System.out.print(sol[x][y] + " "); 
			System.out.println(); 
		} 
	} 
	public static boolean solveKTUtil(int x, int y, int movei, 
									int sol[][], int xMove[], 
									int yMove[]) { 
		int k, next_x, next_y; 
		if (movei == 64) 
			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;// backtracking 
			} 
		} 
		return false; 
	} 
	public static void solveKT() { 
		int sol[][] = new int[8][8]; 
		for (int x = 0; x < 8; x++) 
			for (int y = 0; y < 8; 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; 
		} else
			printSolution(sol); 
	} 
	public static void main(String args[]) { 
		solveKT(); 
	} 
} 

public class HamiltonianCycle { 
	static 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) { 
			if (graph[path[pos - 1]][path[0]] == 1) 
				return true; 
			else
				return false; 
		} 
		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] + " "); 
	} 

	public static void main(String args[]) { 
		/* Let us create the following graph 
			(0)--(1)--(2) 
			| / \ | 
			(3)-------(4)	 */
		HamiltonianCycle hamiltonian = new HamiltonianCycle(); 
		int graph1[][] = {{0, 1, 0, 1, 0}, 
						{1, 0, 1, 1, 1}, 
						{0, 1, 0, 0, 1}, 
						{1, 1, 0, 0, 1}, 
						{0, 1, 1, 1, 0}, 
						}; 
		hamiltonian.hamCycle(graph1); 
	} 
} 

public class SubsetSum { 
	static boolean isSubsetSum(int set[], 
							int n, int sum) 
	{ 
		// Base Cases 
		if (sum == 0) 
			return true; 
		if (n == 0 && sum != 0) 
			return false; 

		// If last element is greater than 
		// sum, then ignore it 
		if (set[n - 1] > sum) 
			return isSubsetSum(set, n - 1, sum); 

		/* else, check if sum can be obtained 
		by any of the following 
			(a) including the last element 
			(b) excluding the last element */
		return isSubsetSum(set, n - 1, sum) 
			|| isSubsetSum(set, n - 1, sum - set[n - 1]); 
	} 
	public static void main(String args[]) 
	{ 
		int set[] = { 3, 34, 4, 12, 5, 2 }; 
		int sum = 9; 
		int n = set.length; 
		if (isSubsetSum(set, n, sum) == true) 
			System.out.println("Found a subset"
								+ " with given sum"); 
		else
			System.out.println("No subset with"
								+ " given sum"); 
	} 
}

public class RatInAMaze { 
	final int N = 4; 

	/* A utility function to print solution matrix sol[N][N] */
	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(); 
		} 
	} 

	/* A utility function to check if x, y is valid 
		index for N*N maze */
	boolean isSafe(int maze[][], int x, int y) { 
		// if (x, y outside maze) return false 
		return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1); 
	} 

	/* This function solves the Maze problem using 
	Backtracking. It mainly uses solveMazeUtil() 
	to solve the problem. It returns false if no 
	path is possible, otherwise return true and 
	prints the path in the form of 1s. Please note 
	that there may be more than one solutions, this 
	function prints one of the feasible solutions.*/
	boolean solveMaze(int maze[][]) { 
		int sol[][] = new int[N][N]; 

		if (solveMazeUtil(maze, 0, 0, sol) == false) { 
			System.out.print("Solution doesn't exist"); 
			return false; 
		} 

		printSolution(sol); 
		return true; 
	} 

	/* A recursive utility function to solve Maze 
	problem */
	boolean solveMazeUtil(int maze[][], int x, int y, 
							int sol[][]) { 
		// if (x, y is goal) return true 
		if (x == N - 1 && y == N - 1) { 
			sol[x][y] = 1; 
			return true; 
		} 

		// Check if maze[x][y] is valid 
		if (isSafe(maze, x, y) == true) { 
			// mark x, y as part of solution path 
			sol[x][y] = 1; 

			/* Move forward in x direction */
			if (solveMazeUtil(maze, x + 1, y, sol)) 
				return true; 

			/* If moving in x direction doesn't give 
			solution then Move down in y direction */
			if (solveMazeUtil(maze, x, y + 1, sol)) 
				return true; 

			/* If none of the above movements work then 
			BACKTRACK: unmark x, y as part of solution 
			path */
			sol[x][y] = 0; 
			return false; 
		} 

		return false; 
	} 

	public static void main(String args[]) { 
		RatInAMaze rat = new RatInAMaze(); 
		int maze[][] = { { 1, 0, 0, 0 }, 
						{ 1, 1, 0, 1 }, 
						{ 0, 1, 0, 0 }, 
						{ 1, 1, 1, 1 } }; 
		rat.solveMaze(maze); 
	} 
}