DominoChain.java

Download 
1/* 2 * DominoChain.java3 * 4 * Computer Science S-225 */6 7import java.util.Arrays;8 9/**10 * A domino chain solver11 * 12 * This class uses backtracking to find domino chain(s) of a desired length.13 */14public class DominoChain {15 16    /** The dominoes to choose from when making chains */17    private Domino[] dominoes;18 19    /** The desired length of the domino chain */20    private int targetLength;21 22    /** An array that keeps track of the current domino chain */23    private Domino[] chain;24 25    /** An array that keeps track of which dominoes are used */26    private boolean[] alreadyUsed;27 28    public DominoChain(Domino[] dominoes, int targetLength) {29        if (dominoes.length == 0) {30            throw new IllegalArgumentException("must be at least one domino");31        }32        if (targetLength <= 0) {33            throw new IllegalArgumentException("chain length must be > 0");34        }35        if (targetLength > dominoes.length) {36            throw new IllegalArgumentException(37                "cannot find chains longer than the number of dominoes"38            );39        }40 41        this.dominoes = dominoes;42        this.alreadyUsed = new boolean[dominoes.length];43 44        this.targetLength = targetLength;45        this.chain = new Domino[targetLength];46    }47 48    public boolean findSolution() {49        // Start building chain at index 050        return this.findSolution(0);51    }52 53    /**54     * Use recursive backtracking to find a chain. When a chain is found,55     * the recursion is stopped and the solution may be obtained using the56     * printSolution() instance method.57     */58    private boolean findSolution(int chainIndex) {59        if (chainIndex == this.targetLength) {60            return true;61        }62 63        for (int i = 0; i < this.dominoes.length; i++) {64            if (this.isValid(chainIndex, this.dominoes[i], i)) {65                this.applyValue(chainIndex, this.dominoes[i], i);66                if (this.findSolution(chainIndex + 1)) {67                    return true;68                }69                this.removeValue(chainIndex, i);70            }71 72            if (!this.dominoes[i].isDouble()) {73                Domino flipped = this.dominoes[i].flipped();74                if (this.isValid(chainIndex, flipped, i)) {75                    this.applyValue(chainIndex, flipped, i);76                    if (this.findSolution(chainIndex + 1)) {77                        return true;78                    }79                    this.removeValue(chainIndex, i);80                }81            }82        }83 84        // No chain possible with the available dominoes85        return false;86    }87 88    /**89     * Checks if a domino can be placed at the given chain index.90     */91    private boolean isValid(92        int chainIndex, Domino candidate, int candidateIndex93    ) {94        if (chainIndex == 0) {95            // Any domino is allowed to start the chain96            return true;97        }98 99        if (this.alreadyUsed[candidateIndex]) {100            // Cannot use the same domino more than once101            return false;102        }103 104        // The previous domino in the chain must match the next domino105        Domino previous = this.chain[chainIndex - 1];106        return previous.getRight() == candidate.getLeft();107    }108 109    private void applyValue(110        int chainIndex, Domino candidate, int candidateIndex111    ) {112        this.alreadyUsed[candidateIndex] = true;113        this.chain[chainIndex] = candidate;114    }115 116    private void removeValue(int chainIndex, int candidateIndex) {117        this.alreadyUsed[candidateIndex] = false;118        this.chain[chainIndex] = null;119    }120 121    /**122     * Use the recursive backtracking technique to find all possible chains.123     * When a chain is found, it is printed, and recursion continues to find124     * all other solutions.125     */126    public void findAllSolutions() {127        // Start building chains at index 0128        this.findAllSolutions(0);129    }130 131    private void findAllSolutions(int chainIndex) {132        if (chainIndex == this.targetLength) {133            this.printSolution();134            return;135        }136 137        for (int i = 0; i < this.dominoes.length; i++) {138            if (this.isValid(chainIndex, this.dominoes[i], i)) {139                this.applyValue(chainIndex, this.dominoes[i], i);140                this.findAllSolutions(chainIndex + 1);141                this.removeValue(chainIndex, i);142            }143 144            if (!this.dominoes[i].isDouble()) {145                Domino flipped = this.dominoes[i].flipped();146                if (this.isValid(chainIndex, flipped, i)) {147                    this.applyValue(chainIndex, flipped, i);148                    this.findAllSolutions(chainIndex + 1);149                    this.removeValue(chainIndex, i);150                }151            }152        }153    }154 155    public void printSolution() {156        System.out.println(Arrays.toString(this.chain));157    }158 159    public static void main(String[] args) {160        Domino[] input = {161            new Domino(4, 2),162            new Domino(1, 0),163            new Domino(1, 4),164            new Domino(2, 0),165            new Domino(3, 2),166            new Domino(1, 3)167        };168        System.out.println("input: " + Arrays.toString(input));169 170        int targetLength = 5;171        DominoChain solver = new DominoChain(input, targetLength);172 173        if (solver.findSolution()) {174            System.out.println("Found one possible chain:");175            solver.printSolution();176        } else {177            System.out.println("No chain is possible.");178        }179 180        // Create a fresh solver object181        DominoChain solver2 = new DominoChain(input, targetLength);182        System.out.println("Find all possible chains:");183        solver2.findAllSolutions();184    }185}