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:
- Make an initial guess
- Check if the guess is valid
- If the guess is valid, explore it further
- If the guess is not valid, backtrack
- 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
N-Queens Problem
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");
}
}
}
Knight’s Tour Problem
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();
}
}
Hamiltonian Cycle Problem
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);
}
}
Subset Sum Problem
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");
}
}
Rat in a Maze Problem
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);
}
}