HelloKoding

Practical coding guides

Backtracking Algorithm Examples in Java

In this article, you will learn about Backtracking algorithm and its approach to solve constraint satisfaction problems such as crosswords and puzzles

Backtracking is an algorithm for solving a constraint satisfaction problem by incrementally building candidates to the solution and abandoning a candidate as soon as it can not satisfy the constraint

Problem 1: All subsets of a set

Write an algorithm to print all subsets of a given array a

For example, the array [1, 2, 3] will have the following subsets

[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

BackTracking_FindAllSubsets.java

package com.hellokoding.algorithm;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BackTracking_FindAllSubsets {
    List<LinkedList<Integer>> result = new ArrayList<>();

    void printSubsets() {
        for (LinkedList<Integer> subset : result) {
            System.out.println(String.valueOf(subset));
        }
    }

    void enumerate(int[] a, int startIndex, LinkedList<Integer> currentSubset) {
        result.add(new LinkedList<>(currentSubset));

        for (int i = startIndex; i < a.length; i++) {
            currentSubset.addLast(a[i]);
            enumerate(a, i + 1, currentSubset);
            currentSubset.removeLast(); // backtracking
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        BackTracking_FindAllSubsets findAllSubsets = new BackTracking_FindAllSubsets();
        findAllSubsets.enumerate(a, 0, new LinkedList<>());
        findAllSubsets.printSubsets();
    }
}

Problem 2: All substrings of a string

Write an algorithm to find all permutations of a given string s

For example, the string "ABC" will have the following permutations: "ABC" "ACB" "BAC" "BCA" "CBA" "CAB"

BackTracking_StringPermutations.java

package com.hellokoding.algorithm;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class BackTracking_StringPermutations {
    List<String> result = new ArrayList<>();

    String swap(String str, int i, int j) {
        char[] arr = str.toCharArray();

        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        return String.valueOf(arr);
    }

    void enumerate(String str, int startIndex) {
        if (startIndex == str.length()-1) {
            result.add(str);
            return;
        }

        for(int i=startIndex; i<str.length(); i++) {
            str = swap(str, startIndex, i);
            enumerate(str, startIndex+1);
            str = swap(str, startIndex, i); // backtracking
        }
    }

    public static void main(String[] args) {
        String str = "ABC";

        BackTracking_StringPermutations permutations = new BackTracking_StringPermutations();
        permutations.enumerate(str, 0);

        System.out.println(permutations.result.stream().collect(Collectors.joining(" ")));
    }
}

Problem 3: N-Queen puzzle

Write an algorithm to place N chess queens on an NxN chessboard so that no two queens threaten each other; thus, a solution requires that no two queens share the same row, column or diagonal

NQueens.java

package com.hellokoding.algorithm;

public class NQueens {
    private void printBoard(int[][] board){
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                System.out.printf(" %d", board[i][j]);
            }

            System.out.println();
        }
    }

    private boolean isValid(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; i < board.length && j >= 0 ; i++, j--) {
            if (board[i][j] == 1) return false;
        }

        return true;
    }

    public boolean enumerate(int[][] board, int col) {
        if (col == board.length) return true;

        for (int i = 0; i < board.length; i++) {
            if (isValid(board, i, col)) {
                board[i][col] = 1;

                if (enumerate(board, col+1)) return true;

                board[i][col] = 0; //backtracking
            }
        }

        return false;
    }

    public static void main(String[] args){
        NQueens nQueens = new NQueens();

        int[][] board = new int[8][8];
        if (!nQueens.enumerate(board, 0)) {
            System.out.println("Solution not found!");
        }

        nQueens.printBoard(board);
    }
}

int[][] board = new int[8][8] all cells default value are 0

isValid(board, row, col) ensures no two queens share the same row, column or diagonal

enumerate(board, col) tries all possible candidates starting from column 0 to 7, backtracks to remove the queen from the board as soon as can not build the solution

col == board.length means all queen are placed on the board

board[i][col] = 1 places a queen on the board at rows i and column col

board[i][col] = 0 removes the queen at rows i and column col from the board

Follow HelloKoding