# 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, 2]
[1, 2, 3]
[1, 3]

[2, 3]
``````

BackTracking_FindAllSubsets.java

``````package com.hellokoding.algorithm;

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

public class BackTracking_FindAllSubsets {

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

void enumerate(int[] a, int startIndex, LinkedList<Integer> currentSubset) {

for (int i = startIndex; i < a.length; 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.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) {
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;
if (!nQueens.enumerate(board, 0)) {
}

nQueens.printBoard(board);
}
}
``````

`int[][] board = new int` 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