Backtracking

Author: Jacob Park

A backtracking algorithm is an algorithm that enumerates a set of partial candidates that could be completed through various extensions to give all the possible solutions to the given problem. The completion is done incrementally, by a sequence of candidate extension steps.

Pseudocode

package backtracking.pseudocode;

import java.util.*;

class Backtracking {
    
    public static class Problem {
        
        public Problem() {
            throw new UnsupportedOperationException();
        }
        
    }
    
    public static class Candidate {
        
        public Candidate() {
            throw new UnsupportedOperationException();
        }
        
    }
    
    public static void backtrack(Problem p) {
        backtrack(p, initialCandidate(p));
    }
    
    private static void backtrack(Problem p, Candidate c) {
        if (rejectCandidate(p, c)) {
            return;
        }
        if (acceptCandidate(p, c)) {
            outputSolution(p, c);
            return;
        }
        
        final Iterable<Candidate> extensions = extendCandidate(p, c);
        
        for (Candidate e : extensions) {
            backtrack(p, e);
        }
    }
    
    private static Candidate initialCandidate(Problem p) {
        throw new UnsupportedOperationException();
    }
    
    private static boolean rejectCandidate(Problem p, Candidate c) {
        throw new UnsupportedOperationException();
    }
    
    private static boolean acceptCandidate(Problem p, Candidate c) {
        throw new UnsupportedOperationException();
    }
    
    private static void outputSolution(Problem p, Candidate c) {
        throw new UnsupportedOperationException();
    }
    
    private static Iterable<Candidate> extendCandidate(Problem p, Candidate c) {
        return new Iterable<Candidate>() {
            @Override
            public Iterator<Candidate> iterator() {
                return new Iterator<Candidate>() {
                    @Override
                    public boolean hasNext() {
                        throw new UnsupportedOperationException();
                    }

                    @Override
                    public Candidate next() {
                        throw new UnsupportedOperationException();
                    }
                };
            }  
        };
    }
    
}

backtracking.pseudocode.Backtracking

Backtracking Example: Eight Queens Puzzle

See Link.

package backtracking.example.eight_queens_puzzle;

import java.lang.Math;
import java.util.*;

class EightQueensPuzzle {
    
    private static class Position {

        private final int row;
        private final int column;

        public Position(int row, int column) {
            this.row = row;
            this.column = column;
        }

        public int getRow() {
            return row;
        }

        public int getColumn() {
            return column;
        }

    }

    public static int countSolutions(int n) {
        return countSolutions(n, initialCandidate(n));
    }

    private static int countSolutions(int n, ArrayList<Position> candidate) {
        if (rejectCandidate(n, candidate)) {
            return 0;
        }
        if (acceptCandidate(n, candidate)) {
            return 1;
        }

        int currentCount = 0;

        final int row = candidate.size() + 1;
        for (int column = 1; column <= n; column++) {
            final ArrayList<Position> extension = new ArrayList<>(candidate);

            extension.add(new Position(row, column));

            currentCount += countSolutions(n, extension);
        }

        return currentCount;
    }

    private static ArrayList<Position> initialCandidate(int n) {
        return new ArrayList<>(n);
    }

    private static boolean rejectCandidate(int n, ArrayList<Position> candidate) {
        if (candidate.size() > n) {
            return true;
        }

        for (int index = 0; index < candidate.size() - 1; index++) {
            final Position lastPosition = candidate.get(candidate.size() - 1);
            final Position currentPosition = candidate.get(index);

            if (currentPosition.getRow() == lastPosition.getRow()) {
                return true;
            }
            if (currentPosition.getColumn() == lastPosition.getColumn()) {
                return true;
            }
            if (Math.abs(currentPosition.getColumn() - lastPosition.getColumn()) ==
                Math.abs(currentPosition.getRow() - lastPosition.getRow())) {
                return true;
            }
        }

        return false;
    }

    private static boolean acceptCandidate(int n, ArrayList<Position> candidate) {
        return n == candidate.size();
    }
    
}

backtracking.example.eight_queens_puzzle.EightQueensPuzzle

package backtracking.example.eight_queens_puzzle;

System.out.println(String.format(
    "Number of Solutions for Eight Queens: %d", EightQueensPuzzle.countSolutions(8)));

Number of Solutions for Eight Queens: 92

null