sudokusolver

public class SudokuGroup {
    SudokuCell[] cells;
    int cellCount = 0;
    final int SUDOKUSIZE;

    public SudokuGroup(int size, SudokuCell... cells) {
        this.SUDOKUSIZE = size;
        this.cells = new SudokuCell[size];
        //if (cells != null) {
            for (SudokuCell cell : cells) {
                addCell(cell);
            }
        //}
    }

    public void addCell(SudokuCell cell) {
        cell.addParentGroup(this);
        cells[cellCount++] = cell;
    }

    void disallow(int number) {
        for (SudokuCell cell : cells) {
            cell.disallow(number);
        }
    }

    Boolean tryDetailSolve() {
        for ( int i = 0; i < SUDOKUSIZE; i++ ) {
            SudokuCell onlyCell = null;
            for (SudokuCell cell : cells) {
                if ( cell.isNumberAllowed(i) ) {
                    if (onlyCell == null) {
                        onlyCell = cell;
                    } else {
                        // second possible placement found, forget it
                        onlyCell = null;
                        break;
                    }
                }
            }
            if (onlyCell != null && onlyCell.getSolution() == -1 ) {
                onlyCell.setValue(i);
                return true;
            }
        }
        return false;
    }



}






public class SudokuCell {
    private Boolean[] numberAllowed;
    private Vector<SudokuGroup> parentGroups = new Vector<SudokuGroup>();
    private int allowedNumberCount;
    private int solution = -1;


    public SudokuCell(int maxval) {
        numberAllowed = new Boolean[maxval];
        for (int i = 0; i < numberAllowed.length; i++) {
            numberAllowed[i] = true;
        }
        allowedNumberCount = maxval;
    }

    void disallow(int number) {
        if ( allowedNumberCount <= 1 || !numberAllowed[number]) {
            return;
        }
        numberAllowed[number] = false;
        allowedNumberCount--;

        if ( allowedNumberCount == 1) { // solved
            for (int i = 0; i < numberAllowed.length; i++) {
                if ( numberAllowed[i] ) {
                    reportSolve(i);
                    return;
                }
            }
        }
    }

    void setValue(int number) {
        for (int i = 0; i < numberAllowed.length; i++) {
            numberAllowed[i] = false;
        }
        numberAllowed[number] = true;
        allowedNumberCount = 1;
        reportSolve(number);
    }

    void reportSolve(int solution) {
        this.solution = solution;
        for ( SudokuGroup group : parentGroups ) {
            group.disallow(solution);
        }
    }

    Boolean isNumberAllowed(int number) {
        return numberAllowed[number];
    }

    void addParentGroup(SudokuGroup group) {
        parentGroups.add(group);
    }

    public int getSolution() {
        return solution;
    }


}








public class Sudokusolver {
    private static final int SUDOKUSIZE = 9;
    private static final int BLOCKSIZE = (int)Math.sqrt(SUDOKUSIZE);
    /**
     * @param args
     */
    public static void main(String[] args) {
        Sudokusolver solver = new Sudokusolver();

/* sample input:
 4      1
67
3   2 4 7
   3 6
   2 4 93
8 579 2 4
42    9
 57 68
    7   8
*/

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        for ( int row = 1; row <= SUDOKUSIZE; row++) {
            try {
                String line = input.readLine();
                for ( int col = 1; col <= SUDOKUSIZE; col++) {
                    char c = line.charAt(col-1);
                    if (Character.isDigit(c)) {
                        solver.setValue(row, col, new Integer(Character.toString(c)));
                    }
                }
            } catch (IOException e) {
                e.printStackTrace();
            }
        }

        while (solver.tryDetailSolve()) {
            /*
            System.out.println("=======================================");
            solver.outputAllowed();
            */
        }

        solver.outputSolved();

    }



    private SudokuCell[][] cells;
    private SudokuGroup[] groups;

    public Sudokusolver() {
        cells = new SudokuCell[SUDOKUSIZE][SUDOKUSIZE];
        for (int x = 0; x < SUDOKUSIZE; x++) {
            for (int y = 0; y < SUDOKUSIZE; y++) {
                cells[x][y] = new SudokuCell(SUDOKUSIZE);
            }
        }

        // 0-8: Columns
        // 9-17: Rows
        // 18-26: Blocks
        groups = new SudokuGroup[SUDOKUSIZE*3];

        // Columns
        for (int i = 0; i < SUDOKUSIZE; i++) {
            groups[i] = new SudokuGroup(SUDOKUSIZE, cells[i]);
        }

        // Rows
        for (int y = 0; y < SUDOKUSIZE; y++) {
            groups[y+9] = new SudokuGroup(SUDOKUSIZE);
            for (int x = 0; x < SUDOKUSIZE; x++) {
                groups[y+9].addCell(cells[x][y]);
            }
        }

        // Blocks
        for (int i = 0; i < SUDOKUSIZE; i++) {
            groups[i+18] = new SudokuGroup(SUDOKUSIZE);
            int blockx = i % BLOCKSIZE;
            int blocky = i / BLOCKSIZE;
            int blockstartx = blockx * BLOCKSIZE;
            int blockstarty = blocky * BLOCKSIZE;
            for (int x = 0; x < BLOCKSIZE; x++) {
                for (int y = 0; y < BLOCKSIZE; y++) {
                    groups[i+18].addCell(cells[blockstartx+x][blockstarty+y]);
                }
            }
        }
    }

    public void setValue(int row, int column, int value) {
        cells[column-1][row-1].setValue(value-1);
    }

    public Boolean tryDetailSolve() {
        for ( SudokuGroup group : groups ) {
            if (group.tryDetailSolve()) {
                return true;
            }
        }
        return false;
    }

    public void outputAllowed() {
        for (int y = 0; y < SUDOKUSIZE; y++) {
            if ( (y % BLOCKSIZE) == 0) {
                System.out.println("---------------------------------------------------------------------------------------------");
            }
            for (int x = 0; x < SUDOKUSIZE; x++) {
                if ( (x % BLOCKSIZE) == 0) {
                    System.out.print("|");
                }
                for (int number = 0; number < SUDOKUSIZE; number++) {
                    System.out.print(cells[x][y].isNumberAllowed(number)? number+1 : " ");
                }
                System.out.print("|");
            }
            System.out.println();
        }
    }


    public void outputSolved() {
        for (int y = 0; y < SUDOKUSIZE; y++) {
            if ( (y % BLOCKSIZE) == 0) {
                //System.out.println();
            }
            for (int x = 0; x < SUDOKUSIZE; x++) {
                if ( (x % BLOCKSIZE) == 0 && (x > 0)) {
                    //System.out.print(" ");
                }
                System.out.print(cells[x][y].getSolution() == -1? "?" : cells[x][y].getSolution()+1);
            }
            System.out.println();
        }
    }

}