CrossNum.java

package crossnum;

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

/**
 * Solve TarfHead's puzzle.
 *
 * Represents the problem as a set of simultaneous equations represented by Tuples,
 * and uses a backtracking / constraint propagation algorithm to solve it.
 *
 * http://www.askaboutmoney.com/showthread.php?t=188279
 *
 *
 * @author dub_nerd
 *
 */
public class CrossNum {

    /**
     * Main entry point
     * @param args not used
     */
    public static void main(String[] args) {
        (new CrossNum()).solve();
    }

    /**
     * A string representation of the board. This is just an easy way to type it
     * in -- we'll immediately convert to an easier-to-use representation for
     * solving using the Board class.
     */
    String strBoard =
            "23 45 291 " +
            "3 87  2 38" +
            " 654 74  9" +
            "2 578 64 1" +
            " 29  6 891" +
            "743 21 55 " +
            " 9811 28  " +
            "62 7 52 28" +
            "9   841313" +
            "2 3987  44" ;

    /**
     * The row totals.
     */
    int rowTotals[] = {
        47,41,51,45,51,35,55,43,47,52
    };

    /**
     * The column totals
     */
    int colTotals[] = {
        44,40,54,51,52,46,36,56,34,54
    };

    /**
     * Diagonal top left to bottom right.
     */
    int leadingDiagTotal = 32;

    /**
     * Diagonal top right to bottom left.
     */
    int minorDiagTotal = 43;

    /**
     * Guts of the algorithm.
     */
    void solve() {

        /*
         * Convert initial board to a more wieldy representation.
         */
        Board board = new Board(strBoard);

        /*
         * Set up the unknowns in the rows, columns, diagonals (i.e. tuples)
         * as a set of simultaneous equations in an augmented matrix containing
         * unknowns and required sums.
         */
        List<Tuple> augmentedMatrix = getAugmentedMatrix(board);

        /*
         * Cache all numbers of combinations of up to 4 digits that sum to anything
         * up to 30. For instance, combos.getNumberCombos(3, 14) would return the
         * number of combinations of 3 digit numbers that sum to 14 (excluding all
         * combinations that contain any zeros).
         */
        Combos combos = new Combos(4, 30);

        // Try column 4 ... to try all tuples restore the commented out values

        for (int i = /* 0 */ 13; i < /*augmentedMatrix.size()*/ 14; i++) {
            totalCombosDone = 0;
            boolean b =constrain(combos, augmentedMatrix, i);
            System.out.printf("Start at %s, solved=%s, combos tried=%s\n", getTupleName(i), b, totalCombosDone);
            // Print the unknown values (now known!)
            for (int row = 0; row < board.getSide(); row++) {
                Tuple tuple = augmentedMatrix.get(row);
                boolean first = true;
                for (Variable v : tuple.variables()) {
                    System.out.printf("%s", first? "  " : ", ");
                    System.out.printf("B%s = %s", v.getOrdinal(), v.getValue());
                    first = false;
                }
                System.out.println();
            }
        }


    }

    /**
     * Set up the augmented matrix
     * @param board
     * @return the augmented matrix as a list of tuples
     */
    private List<Tuple> getAugmentedMatrix(Board board) {

        List<Tuple> augmentedMatrix = new ArrayList<Tuple>();

        // Board's side length
        int side = board.getSide();

        // We label our unknowns with an ordinal value starting at 1.
        int ordinal = 1;

        /*
         * Do rows and columns -- "isRow" indicates whether we are doing rows or
         * columns. For each row and column we set up a tuple consisting of the
         * unknown (i.e. = zero) values. We also set the tuple's required total
         * by subtracting the known values from the totals given in the puzzle.
         *
         * We set an ordinal (label) for each unknown in ascending sequence.
         * This is only done on the rows since we also encounter the same
         * unknowns on the columns and diagonals. On each tuple we sort the
         * unknown in ascending order of ordinal -- this is just a convenience
         * so that when printing them out we see a consistent order.
         */
        for (boolean isRow : new boolean[] { true, false }) {

            for (int i = 0; i < side; i++) {

                Tuple amRow = new Tuple();
                augmentedMatrix.add(amRow);
                int tupleActualTotal = 0;
                int tupleTotals[] = isRow? rowTotals : colTotals;

                for (int j = 0; j < side; j++) {

                    int row = isRow? i : j;
                    int col = isRow? j : i;
                    Variable v = board.get(row, col);
                    tupleActualTotal += v.getValue();
                    if (v.getValue() == 0) {
                        amRow.variables().add(v);
                        if (isRow) {
                            v.setOrdinal(ordinal++);
                        }
                    }

                }

                amRow.setRequiredSum(tupleTotals[i] - tupleActualTotal);
                Collections.sort(amRow.variables(), Variable.sortByOrdinal);

            }

        }


        // Do both diagonals in a similar way -- isLead indicates which one
        for (boolean isLead : new boolean[]{true, false}) {

            Tuple amRow = new Tuple();
            augmentedMatrix.add(amRow);
            int tupleActualTotal = 0;
            int tupleTotal = isLead? leadingDiagTotal : minorDiagTotal;

            for (int i = 0; i < side; i++) {

                int row = i;
                int col = isLead? row : side - row - 1;
                Variable v = board.get(row, col);
                tupleActualTotal += v.getValue();
                if (v.getValue() == 0) {
                    amRow.variables().add(v);
                }

            }

            amRow.setRequiredSum(tupleTotal - tupleActualTotal);
            Collections.sort(amRow.variables(), Variable.sortByOrdinal);

        }

        return augmentedMatrix;

    }



    /**
     * A handy tot on how many tuple attempts has to be made to come up with solution.
     */
    int totalCombosDone = 0;

    /**
     * "Constrain" a tuple of unknowns. That is, try out the possible values for
     * the unknowns, given that some of them may already have been constrained
     * by other tuples, and then recursively constrain more tuples until there
     * are none left and the puzzle is solved.
     *
     * Whenever we try out a combination of values for this tuple, we "lock" the
     * values we have tried, so that no other recursive attempt on a tuple can
     * touch those values. Whenever we are exiting this recursive iteration, we
     * unlock our values so that they are free to be altered again.
     *
     * @param combos
     *            a convenience cache of combinations and sums, used to optimise
     *            the selection of the next tuple to be constrained, based on
     *            minimum combinations.
     * @param augmentedMatrix
     *            the full list of tuples
     * @param n
     *            the index into the augmented matrix of the tuple to be
     *            constrained this time
     * @return a boolean indicating if the puzzle is now solved
     */
    private boolean constrain(Combos combos, List<Tuple> augmentedMatrix, int n) {

        Tuple currTuple = augmentedMatrix.get(n); // current tuple

        // Get the remaining total that our unlocked unknowns must sum to
        int remainingSum = currTuple.getRemainderSum();

        // Count the remaining unknown digits, and lock them
        int remainingDigits = currTuple.lock();

        // Find out how many combinations of our remaining digits can sum to the
        // required total
        int numCombos = combos.getNumberCombos(remainingDigits, remainingSum);

        // Now try all those possible combinations:
        int combosDone = 0;
        DigitCombo d = new Base9(remainingDigits);
        while (combosDone < numCombos) {
            if (d.summedDigits() != remainingSum) {
                // keep counting until we get the necessary total
                d.increment();
                continue;
            }
            // if we get here then we have a match -- try it
            combosDone++;
            totalCombosDone++;
            int i = 0;
            System.out.printf("Try %s: ", getTupleName(n)); // convenience print
                                                            // - comment out for
                                                            // performance
            // We have a set of digits to try. Set our "owned" variables with them
            for (Variable v : currTuple.variables()) {
                if (v.getLock() == currTuple) { // i.e. owned by us
                    int val = d.digits()[i++];
                    v.setValue(val);
                    // Convenience print to show value tried -- comment out for performance
                    System.out.printf("B%s = %s; ", v.getOrdinal(), v.getValue()); //
                }
            }
            System.out.println(); // Comment out for performance

            // Now that we're trying a value that sums to the right number,
            // select the next tuple to be constrained, based on minimum
            // possible combinations.
            int nextTuple = selectNextConstrainee(combos, augmentedMatrix);
            if (nextTuple == -1) {
                // -1 indicates there are no tuples left to constrain, so we
                // are finished!
                currTuple.unlock();
                return true;
            } else if (nextTuple >= -0) {
                // we found a tuple to constrain, so recursively constrain it.
                // If *it* returns true, we are finished.
                if (constrain(combos, augmentedMatrix, nextTuple)) {
                    currTuple.unlock();
                    return true;
                }
            }
            // If we get here, our combination was no use because we couldn't
            // recursively constrain the remaining tuples. So try the next combination.
            d.increment();
        }

        // We have now tried all our combinations and if we get here it means that
        // we couldn't satisfy our required total. We have to backtrack and let the
        // previous tuple try another combination.
        System.out.println("Stuck -- go back to previous"); // convenience print
        currTuple.unlock();
        return false;
    }

    /**
     * Select the next tuple from the augmented matrix which is not yet
     * satisfied. Instead of just taking the next one in sequence, we poll them
     * all to see how many possible combinations they might have to try, and we
     * take the one with the minimum. This is intended as an optimisation
     * (although it's not guaranteed to find the best route).
     *
     * @param combos
     *            a convenience cache of numbers of combinations.
     * @param augmentedMatrix
     *            the augmented matrix
     * @return the index into the augmented matrix of the next tuple to be
     *         constrained. Negative values have special meaning: -1 means there
     *         are no more tuples to constrain and the problem is solved; -2
     *         means the problem is solved but there is no valid way forward so
     *         we must backtrack.
     */
    int selectNextConstrainee(Combos combos, List<Tuple> augmentedMatrix) {

        // Track which tuple has minimum combos. Start with a crazy high number.
        int minCombos = 1000000;

        // The selected tuple index, initially -1 which indicates no tuple
        // is left unsatisfied.
        int selectedTuple = -1;

        // An indicator value meaning "there is no possible solution from here"
        final int kNoSolution = -2;

        // Test all tuples
        for (int i = 0; i < augmentedMatrix.size(); i++) {

            Tuple tuple = augmentedMatrix.get(i);

            // Get the required remaining sum, discounting any variables already locked
            int remainingSum = tuple.getRemainderSum();
            int remainingDigits = tuple.getNumUnlocked();

            if (remainingDigits == 0) {
                // no digits left unlocked
                if (remainingSum == 0) {
                    // this tuple is satisfied -- next
                    continue;
                } else {
                    // no digits left to set but wrong total -- no solution
                    return kNoSolution;
                }
            }

            if (remainingSum < 1) {
                // there are remaining digits but they must sum to less than 1 -- no solution
                return kNoSolution;
            }

            // How many combinations of the remaining digits sum to required sum?
            int numCombos = combos.getNumberCombos(remainingDigits, remainingSum);

            if (numCombos == 0) {
                // no combos = no solution
                return kNoSolution;
            }

            // There are possible combos -- select the minimum number
            if (numCombos < minCombos) {
                minCombos = numCombos;
                selectedTuple = i;
            }
        }

        return selectedTuple;
    }


    /**
     * A convenience routine for getting a printable tuple name from
     * its position in the augmented matrix.
     *
     * @param tupleNum position in matrix
     * @return a convenience name for printing
     */
    String getTupleName(int tupleNum) {
        int n = tupleNum;
        // First 10 tuples are rows, next 10 are columns, then two diagonals
        return n < 10 ? "row " + (n + 1) : n < 20 ? "column "
                + (n - 9) : "diagonal " + (n - 19);

    }

}