L'union fait la force

package unionfaitlaforce;

import java.util.Arrays;

/**
 *
 * @author alain
 */
public class UnionFaitLaForce {

    static final int FREE = 0, SELECTED = 1, FORBIDDEN = 2;
    int[][] input = new int[][]{
        {0, 2, 7, 7, 7, 8, 4, 3, 0, 9},
        {0, 3, 1, 9, 6, 2, 0, 9, 4, 0},
        {0, 5, 9, 2, 5, 7, 8, 1, 3, 6},
        {0, 8, 0, 3, 3, 2, 3, 6, 5, 7},
        {0, 8, 3, 1, 8, 4, 2, 6, 2, 8},
        {1, 0, 5, 4, 9, 3, 7, 5, 3, 9},
        {1, 1, 8, 2, 8, 2, 4, 0, 9, 3},
        {1, 2, 5, 1, 2, 7, 6, 7, 8, 5},
        {1, 4, 2, 1, 5, 3, 1, 7, 0, 4},
        {2, 0, 8, 3, 4, 8, 5, 1, 5, 5},
        {2, 3, 2, 7, 1, 3, 2, 1, 8, 3},
        {2, 6, 5, 2, 7, 5, 3, 9, 2, 4},
        {2, 9, 4, 4, 1, 1, 4, 7, 7, 6},
        {3, 0, 7, 2, 2, 1, 9, 8, 6, 1},
        {4, 1, 2, 8, 7, 4, 6, 5, 1, 6},
        {4, 5, 0, 6, 6, 8, 2, 8, 5, 5},
        {5, 6, 2, 9, 8, 7, 7, 3, 7, 8},
        {7, 1, 0, 7, 1, 7, 1, 5, 2, 0},
        {7, 8, 2, 9, 2, 3, 4, 1, 2, 7},
        {8, 1, 9, 1, 7, 0, 7, 8, 8, 7},
        {8, 3, 1, 4, 5, 1, 6, 3, 2, 3},
        {8, 5, 1, 1, 1, 3, 6, 3, 9, 4},
        {9, 7, 1, 0, 0, 5, 4, 6, 3, 2}
    };
    /*int[][] input = new int[][]{
        { 0, 7, 3, 4, 4},
        { 1, 4, 0, 9, 8},
        { 2, 7, 3, 5, 6},
        { 3, 6, 4, 2, 9},
        { 4, 5, 3, 7, 4},
        { 5, 2, 2, 0, 7},
        { 6, 3, 8, 2, 2},
        { 7, 0, 5, 5, 8},
        { 8, 5, 2, 3, 7},
        { 9, 7, 6, 6, 5}
    };*/
    int[][] occurrences, status;
    int[] max;

    public static void main(String[] args) {
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < 1000; i++) {
            UnionFaitLaForce union = new UnionFaitLaForce();
            union.init();
            union.iterate();
        }
        System.out.println(System.currentTimeMillis() - startTime);
    }

    private void init() {
        status = new int[10][input[0].length];
        computeOcurrences();
    }

    private void print(int[][] input) {
        for (int row = 0; row < input.length; row++) {
            for (int col = 0; col < input[0].length; col++) {
                System.out.print(input[row][col] + " ");
            }
            System.out.println("");
        }
    }

    private void computeOcurrences() {
        occurrences = new int[10][input[0].length];
        for (int row = 0; row < input.length; row++) {
            for (int col = 0; col < input[0].length; col++) {
                occurrences[input[row][col]][col]++;
            }
        }
    }

    private void iterate() {
        while (sumMaxes() >= input.length) {
            int d = 0, c = 0, max = -1;
            for (int digit = 0; digit < occurrences.length; digit++) {
                for (int col = 0; col < occurrences[0].length; col++) {
                    if (occurrences[digit][col] > max && status[digit][col] == FREE) {
                        max = occurrences[digit][col];
                        d = digit;
                        c = col;
                    }
                }
            }
            if (max >= 0) {
                int[][] statusCopy = deepCopy(status);
                select(d, c);
                iterate();
                status = deepCopy(statusCopy);
                status[d][c] = FORBIDDEN;
            } else {
                System.out.println("Found");
                for (int col = 0; col < status[0].length; col++) {
                    for (int digit = 0; digit < status.length; digit++) {
                        if (status[digit][col] == SELECTED) {
                            System.out.print(digit + " ");
                        }
                    }
                }
                System.out.println();
                break;
            }
        }
    }

    private int sumMaxes() {
        max = new int[input[0].length];
        int sum = 0;
        for (int col = 0; col < occurrences[0].length; col++) {
            for (int digit = 0; digit < occurrences.length; digit++) {
                if (status[digit][col] != FORBIDDEN) {
                    max[col] = occurrences[digit][col] < max[col] ? max[col] : occurrences[digit][col];
                }
            }
            sum += max[col];
        }
        return sum;
    }

    private void select(int d, int c) {
        status[d][c] = SELECTED;
        for (int digit = 0; digit < occurrences.length; digit++) {
            if (d != digit) {
                status[digit][c] = FORBIDDEN;
            }
        }
        for (int row = 0; row < input.length; row++) {
            if (input[row][c] == d) {
                for (int col = 0; col < input[0].length; col++) {
                    if (col != c) {
                        status[input[row][col]][col] = FORBIDDEN;
                    }
                }
            }
        }
    }

    private int[][] deepCopy(int[][] original) {
        final int[][] result = new int[original.length][];
        for (int i = 0; i < original.length; i++) {
            result[i] = Arrays.copyOf(original[i], original[i].length);
        }
        return result;
    }
}