WikiGalaxy
Introduction to Backtracking
What is Backtracking?
Backtracking is a general algorithmic technique that involves solving problems incrementally, one piece at a time, and removing solutions that fail to satisfy the problem constraints. It is often used for constraint satisfaction problems such as puzzles, crosswords, and more.
Example 1: N-Queens Problem
Problem Statement:
Place N queens on an N×N chessboard so that no two queens threaten each other.
Step 1: Place a queen in the leftmost column
Step 2: If all queens are placed, return true
Step 3: Try placing the queen in all rows in the current column
Step 4: If placing the queen leads to a solution, return true
Step 5: If none of the rows work, backtrack and remove the queen
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; // BACKTRACK
}
}
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 N-Queens problem is solved using backtracking by placing queens one by one in different columns, starting from the leftmost column. When a queen can't be placed in any row in a column, it backtracks to the previous column and moves the previously placed queen to the next row.
Console Output:
0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0
Example 2: Sudoku Solver
Problem Statement:
Fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids contain all of the digits from 1 to 9.
Step 1: Find an empty cell
Step 2: Try all numbers from 1 to 9
Step 3: If a number is valid, place it and move to the next cell
Step 4: If placing the number doesn't lead to a solution, remove it
Step 5: Repeat until the entire grid is filled
public class Sudoku {
private static final int GRID_SIZE = 9;
public static void main(String[] args) {
int[][] board = {
{7, 0, 2, 0, 5, 0, 6, 0, 0},
{0, 0, 0, 0, 0, 3, 0, 0, 0},
{1, 0, 0, 0, 0, 9, 5, 0, 0},
{8, 0, 0, 0, 0, 0, 0, 9, 0},
{0, 4, 3, 0, 0, 0, 7, 5, 0},
{0, 9, 0, 0, 0, 0, 0, 0, 8},
{0, 0, 9, 7, 0, 0, 0, 0, 5},
{0, 0, 0, 2, 0, 0, 0, 0, 0},
{0, 0, 7, 0, 4, 0, 2, 0, 3}
};
if (solveBoard(board)) {
printBoard(board);
} else {
System.out.println("No solution exists");
}
}
private static boolean isNumberInRow(int[][] board, int number, int row) {
for (int i = 0; i < GRID_SIZE; i++) {
if (board[row][i] == number) {
return true;
}
}
return false;
}
private static boolean isNumberInColumn(int[][] board, int number, int column) {
for (int i = 0; i < GRID_SIZE; i++) {
if (board[i][column] == number) {
return true;
}
}
return false;
}
private static boolean isNumberInBox(int[][] board, int number, int row, int column) {
int localBoxRow = row - row % 3;
int localBoxColumn = column - column % 3;
for (int i = localBoxRow; i < localBoxRow + 3; i++) {
for (int j = localBoxColumn; j < localBoxColumn + 3; j++) {
if (board[i][j] == number) {
return true;
}
}
}
return false;
}
private static boolean isValidPlacement(int[][] board, int number, int row, int column) {
return !isNumberInRow(board, number, row) &&
!isNumberInColumn(board, number, column) &&
!isNumberInBox(board, number, row, column);
}
private static boolean solveBoard(int[][] board) {
for (int row = 0; row < GRID_SIZE; row++) {
for (int column = 0; column < GRID_SIZE; column++) {
if (board[row][column] == 0) {
for (int numberToTry = 1; numberToTry <= GRID_SIZE; numberToTry++) {
if (isValidPlacement(board, numberToTry, row, column)) {
board[row][column] = numberToTry;
if (solveBoard(board)) {
return true;
} else {
board[row][column] = 0;
}
}
}
return false;
}
}
}
return true;
}
private static void printBoard(int[][] board) {
for (int row = 0; row < GRID_SIZE; row++) {
if (row % 3 == 0 && row != 0) {
System.out.println("-----------");
}
for (int column = 0; column < GRID_SIZE; column++) {
if (column % 3 == 0 && column != 0) {
System.out.print("|");
}
System.out.print(board[row][column]);
}
System.out.println();
}
}
}
Explanation:
The Sudoku solver fills the grid by trying numbers 1 through 9 in empty cells while ensuring the rules of Sudoku are not violated. If a conflict is found, it backtracks and tries the next number.
Console Output:
579682413 624913758 138457926 857134692 943268175 216795384 392571864 781649532 465328917
