WikiGalaxy
Backtracking Technique: N-Queens Problem
Understanding the Problem:
The N-Queens problem involves placing N queens on an N×N chessboard so that no two queens threaten each other. This means no two queens share the same row, column, or diagonal.
Approach:
We use backtracking to explore all possible placements of queens on the board, backtracking whenever a conflict is detected.
public class NQueens {
final int N = 4;
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();
}
}
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;
}
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 solveNQ() {
int board[][] = {{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0},
{0, 0, 0, 0}};
if (!solveNQUtil(board, 0)) {
System.out.print("Solution does not exist");
return false;
}
printSolution(board);
return true;
}
public static void main(String args[]) {
NQueens Queen = new NQueens();
Queen.solveNQ();
}
}
Explanation:
The algorithm places queens one by one in different columns, starting from the leftmost column. When a queen is placed in a column, we check for clashes with already placed queens. If a clash occurs, we backtrack and try a different row. This process continues until all queens are placed safely.
Backtracking Technique: Sudoku Solver
Understanding the Problem:
Sudoku is a 9x9 grid puzzle where the objective is to fill the grid with numbers 1 to 9, such that each number appears exactly once in each row, column, and 3x3 subgrid.
Approach:
Backtracking is used to fill the grid one cell at a time, ensuring no conflicts with the Sudoku rules. If a conflict arises, we backtrack to the previous cell and try a different number.
public class SudokuSolver {
final int N = 9;
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;
}
boolean solveSudoku(int grid[][], int row, int col) {
if (row == N - 1 && col == N)
return true;
if (col == N) {
row++;
col = 0;
}
if (grid[row][col] != 0)
return solveSudoku(grid, row, col + 1);
for (int num = 1; num <= N; num++) {
if (isSafe(grid, row, col, num)) {
grid[row][col] = num;
if (solveSudoku(grid, row, col + 1))
return true;
grid[row][col] = 0;
}
}
return false;
}
public static void main(String args[]) {
SudokuSolver sudoku = new SudokuSolver();
int grid[][] = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
if (sudoku.solveSudoku(grid, 0, 0))
sudoku.print(grid);
else
System.out.println("No solution exists");
}
void print(int grid[][]) {
for (int r = 0; r < N; r++) {
for (int d = 0; d < N; d++)
System.out.print(grid[r][d]);
System.out.print("\n");
}
}
}
Explanation:
The algorithm attempts to fill each cell with a valid number. If a number placement leads to a conflict, it backtracks and tries a different number. This continues until the entire grid is filled correctly.
Backtracking Technique: Subset Sum Problem
Understanding the Problem:
Given a set of integers, the task is to find a subset whose sum is equal to a given target.
Approach:
Backtracking explores all subsets of the given set, checking if the sum of the current subset equals the target. If not, it backtracks and tries a different combination.
public class SubsetSum {
static 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]);
}
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");
}
}
Explanation:
The algorithm checks each subset of the set recursively. If a subset's sum matches the target, it returns true. Otherwise, it backtracks and tries other combinations until all possibilities are exhausted.
Backtracking Technique: Rat in a Maze
Understanding the Problem:
The Rat in a Maze problem involves finding a path from the top-left corner to the bottom-right corner of a grid, moving only right or down, avoiding obstacles.
Approach:
Backtracking is used to explore all possible paths from the start to the destination. If a path is blocked, the algorithm backtracks and tries a different path.
public 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.print("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();
}
}
public static void main(String args[]) {
RatMaze rat = new RatMaze();
int maze[][] = {{1, 0, 0, 0},
{1, 1, 0, 1},
{0, 1, 0, 0},
{1, 1, 1, 1}};
rat.solveMaze(maze);
}
}
Explanation:
The algorithm explores all paths from the start to the destination. It marks the path as part of the solution if it leads to the destination. If a dead-end is reached, it backtracks and tries a different path.
Backtracking Technique: Hamiltonian Cycle
Understanding the Problem:
The Hamiltonian Cycle problem is to find a cycle in a graph that visits every vertex exactly once and returns to the starting vertex.
Approach:
Backtracking is used to build the cycle one vertex at a time, checking for cycles at each step. If a cycle is not possible, it backtracks to try a different path.
public 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) {
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) == true)
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) == false) {
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[]) {
HamiltonianCycle hamiltonian = new HamiltonianCycle();
int graph[][] = {
{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(graph);
}
}
Explanation:
The algorithm attempts to construct a cycle by adding vertices one by one. If a vertex cannot be added, the algorithm backtracks and tries another vertex until a cycle is found or all possibilities are exhausted.
