gistfile1.java

public class Main {
    private static boolean trySet(String input, int i, char[] data, boolean[] v, boolean[] h, boolean[] c, int value) {
        int vv = i % 9 * 9, hh = i / 9 * 9, cc = (i / 27 * 3 + i % 9 / 3) * 9;

        if (v[vv + value] || h[hh + value] || c[cc + value]) return false;

        data[i] = (char) (value + '1');

        v[vv + value] = h[hh + value] = c[cc + value] = true;
        if (solveInternal(input, i + 1, data, v, h, c))
            return true;
        v[vv + value] = h[hh + value] = c[cc + value] = false;
        return false;
    }

    public static boolean solveInternal(String input, int i, char[] data, boolean[] v, boolean[] h, boolean[] c) {
        if (i == 81)
            return true;

        if (Character.isDigit(input.charAt(i))) {
            return trySet(input, i, data, v, h, c, input.charAt(i) - '1');
        } else {
            for (int value = 0; value < 9; value++)
                if (trySet(input, i, data, v, h, c, value))
                    return true;
            return false;
        }
    }

    public static String solve(String input) {
        char[] data = new char[81];
        boolean[] h = new boolean[81], v = new boolean[81], c = new boolean[81];
        if (!solveInternal(input, 0, data, v, h, c))
            return null;
        return new String(data);
    }

    public static void main(String... args) {
        String input = "8156....4" +
                "6...75.8." +
                "....9...." +
                "9...417.." +
                ".4.....2." +
                "..623...8" +
                "....5...." +
                ".5.91...6" +
                "1....7895";
        System.out.println(solve(input));
    }
}