sudokusolver.java

package com.hafthor;

public class Main {
    public static void main(final String[] args) {
        final String input = "" +
                "89. .5. ..." +
                "2.. 7.9 ..." +
                "..4 ..3 ..." +
                "..9 6.2 ..3" +
                "... ..1 897" +
                ".15 97. ..." +
                ".5. 2.. 7.." +
                "... 3.. 4.1" +
                ".42 .9. 5..";
        final byte[] grid = parseGridString(input);
        for (; ; ) {
            printGrid(grid);
            if (solve(grid) == 0) break;
            System.out.println();
        }
        if (!solved(grid)) System.out.println("*** Couldn't solve ***");
        else System.out.println();
    }

    static boolean solved(final byte[] grid) {
        for (final int g : grid) if (g == 0) return false;
        return true;
    }

    static byte[] parseGridString(final String s) {
        final byte[] grid = new byte[9 * 9];
        int i = 0;
        for (final char k : s.toCharArray())
            if (k >= '1' && k <= '9')
                grid[i++] = (byte) Integer.parseInt("" + k);
            else if (k == '.')
                grid[i++] = 0;
        if (i != 9 * 9) throw new IllegalArgumentException();
        return grid;
    }

    static int solve(final byte[] grid) {
        int s = 0;
        for (int r = 0; r < 9; r++)
            for (int c = 0; c < 9; c++)
                s += solve(grid, r, c);
        for (int r = 0; r < 3; r++)
            for (int c = 0; c < 3; c++)
                s += solveSubGrid(grid, r, c);
        return s;
    }

    static int gridAt(final int r, final int c) {
        return (r / 3) * 3 + (c / 3);
    }

    static int subGrid(final int g, final int i) {
        final int r = g / 3, c = g % 3;
        final int rr = i / 3, rc = i % 3;
        return (r * 3 + rr) * 9 + c * 3 + rc;
    }

    static int solveSubGrid(final byte[] grid, final int r, final int c) {
        int s = 0;
        for (byte b = 1; b <= 9; b++) {
            if (!subGridContains(grid, r, c, b)) {
                s += solveSubGrid(grid, r, c, b);
            }
        }
        return s;
    }

    static boolean subGridContains(final byte[] grid, final int r, final int c, final byte b) {
        for (int rr = 0; rr < 3; rr++)
            for (int cc = 0; cc < 3; cc++)
                if (grid[(r * 3 + rr) * 9 + c * 3 + cc] == b) return true;
        return false;
    }

    static int solveSubGrid(final byte[] grid, final int gr, final int gc, final byte b) {
        int match = -1;
        for (int rr = 0; rr < 3; rr++)
            for (int cc = 0; cc < 3; cc++) {
                int r = gr * 3 + rr, c = gc * 3 + cc;
                if (!rowContains(grid, r, b) && !colContains(grid, c, b)) {
                    if (match >= 0) return 0;
                    match = r * 9 + c;
                }
            }
        if (match < 0) return 0;
        grid[match] = b;
        return 1;
    }

    static boolean rowContains(final byte[] grid, final int r, final byte b) {
        for (int i = 0; i < 9; i++) if (grid[r * 9 + i] == b) return true;
        return false;
    }

    static boolean colContains(final byte[] grid, final int c, final byte b) {
        for (int i = 0; i < 9; i++) if (grid[c + i * 9] == b) return true;
        return false;
    }

    static int solve(final byte[] grid, final int r, final int c) {
        if (grid[r * 9 + c] != 0) return 0;
        String canbe = "123456789";
        final int rc = r * 9 + c;
        final int g = gridAt(r, c);
        for (int i = 0; i < 9; i++) {
            final int gr = r * 9 + i, gc = i * 9 + c, gg = subGrid(g, i);
            if (rc != gr && grid[gr] != 0)
                canbe = canbe.replace("" + grid[gr], "");
            if (rc != gc && grid[gc] != 0)
                canbe = canbe.replace("" + grid[gc], "");
            if (rc != gg && grid[gg] != 0)
                canbe = canbe.replace("" + grid[gg], "");
        }
        if (canbe.length() == 0) throw new IllegalArgumentException();
        if (canbe.length() > 1) return 0;
        grid[r * 9 + c] = (byte) Integer.parseInt(canbe);
        return 1;
    }

    static void printGrid(final byte[] grid) {
        for (int i = 0, r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                final byte b = grid[i++];
                System.out.print(b > 0 ? (char) ('0' + b) : '.');
            }
            System.out.println();
        }
    }
}