/* 
 * DominoChain.java
 * 
 * Computer Science E-22
 */

import java.util.Arrays;

/**
 * A domino chain solver
 * 
 * This class uses backtracking to find domino chain(s) of a desired length.
 */
public class DominoChain {

    /** The dominoes to choose from when making chains */
    private Domino[] dominoes;

    /** The desired length of the domino chain */
    private int targetLength;

    /** An array that keeps track of the current domino chain */
    private Domino[] chain;

    /** An array that keeps track of which dominoes are used */
    private boolean[] alreadyUsed;

    public DominoChain(Domino[] dominoes, int targetLength) {
        if (dominoes.length == 0) {
            throw new IllegalArgumentException("must be at least one domino");
        }
        if (targetLength <= 0) {
            throw new IllegalArgumentException("chain length must be > 0");
        }
        if (targetLength > dominoes.length) {
            throw new IllegalArgumentException(
                "cannot find chains longer than the number of dominoes"
            );
        }

        this.dominoes = dominoes;
        this.alreadyUsed = new boolean[dominoes.length];

        this.targetLength = targetLength;
        this.chain = new Domino[targetLength];
    }

    public boolean findSolution() {
        // Start building chain at index 0
        return this.findSolution(0);
    }

    /**
     * Use recursive backtracking to find a chain. When a chain is found,
     * the recursion is stopped and the solution may be obtained using the
     * printSolution() instance method.
     */
    private boolean findSolution(int chainIndex) {
        if (chainIndex == this.targetLength) {
            return true;
        }

        for (int i = 0; i < this.dominoes.length; i++) {
            if (this.isValid(chainIndex, this.dominoes[i], i)) {
                this.applyValue(chainIndex, this.dominoes[i], i);
                if (this.findSolution(chainIndex + 1)) {
                    return true;
                }
                this.removeValue(chainIndex, i);
            }

            if (!this.dominoes[i].isDouble()) {
                Domino flipped = this.dominoes[i].flipped();
                if (this.isValid(chainIndex, flipped, i)) {
                    this.applyValue(chainIndex, flipped, i);
                    if (this.findSolution(chainIndex + 1)) {
                        return true;
                    }
                    this.removeValue(chainIndex, i);
                }
            }
        }

        // No chain possible with the available dominoes
        return false;
    }

    /**
     * Checks if a domino can be placed at the given chain index.
     */
    private boolean isValid(
        int chainIndex, Domino candidate, int candidateIndex
    ) {
        if (chainIndex == 0) {
            // Any domino is allowed to start the chain
            return true;
        }

        if (this.alreadyUsed[candidateIndex]) {
            // Cannot use the same domino more than once
            return false;
        }

        // The previous domino in the chain must match the next domino
        Domino previous = this.chain[chainIndex - 1];
        return previous.getRight() == candidate.getLeft();
    }

    private void applyValue(
        int chainIndex, Domino candidate, int candidateIndex
    ) {
        this.alreadyUsed[candidateIndex] = true;
        this.chain[chainIndex] = candidate;
    }

    private void removeValue(int chainIndex, int candidateIndex) {
        this.alreadyUsed[candidateIndex] = false;
        this.chain[chainIndex] = null;
    }

    /**
     * Use the recursive backtracking technique to find all possible chains.
     * When a chain is found, it is printed, and recursion continues to find
     * all other solutions.
     */
    public void findAllSolutions() {
        // Start building chains at index 0
        this.findAllSolutions(0);
    }

    private void findAllSolutions(int chainIndex) {
        if (chainIndex == this.targetLength) {
            this.printSolution();
            return;
        }

        for (int i = 0; i < this.dominoes.length; i++) {
            if (this.isValid(chainIndex, this.dominoes[i], i)) {
                this.applyValue(chainIndex, this.dominoes[i], i);
                this.findAllSolutions(chainIndex + 1);
                this.removeValue(chainIndex, i);
            }

            if (!this.dominoes[i].isDouble()) {
                Domino flipped = this.dominoes[i].flipped();
                if (this.isValid(chainIndex, flipped, i)) {
                    this.applyValue(chainIndex, flipped, i);
                    this.findAllSolutions(chainIndex + 1);
                    this.removeValue(chainIndex, i);
                }
            }
        }
    }

    public void printSolution() {
        System.out.println(Arrays.toString(this.chain));
    }

    public static void main(String[] args) {
        Domino[] input = {
            new Domino(4, 2),
            new Domino(1, 0),
            new Domino(1, 4),
            new Domino(2, 0),
            new Domino(3, 2),
            new Domino(1, 3)
        };
        System.out.println("input: " + Arrays.toString(input));

        int targetLength = 5;
        DominoChain solver = new DominoChain(input, targetLength);

        if (solver.findSolution()) {
            System.out.println("Found one possible chain:");
            solver.printSolution();
        } else {
            System.out.println("No chain is possible.");
        }

        // Create a fresh solver object
        DominoChain solver2 = new DominoChain(input, targetLength);
        System.out.println("Find all possible chains:");
        solver2.findAllSolutions();
    }
}