import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

/*  
 * Oct 1, 2007
 *
 * Copyright (c) LandAmerica Tax and Flood
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of La
+ndAmerica
 * Tax and Flood ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with LandAmerica Tax and Flood.
 */

public class SudoKu
{
    public static int loadedTable[][] = new int[9][9];
    public static int initialTable[][] = new int[9][9];

    public static int tmpTable[][] = new int[9][9];
    
    public static int completeTable[][] = new int[9][9];

    public static boolean rowpossible[][] = new boolean[9][9];
    public static boolean rowpossibleInitial[][] = new boolean[9][9];

    public static boolean columnpossible[][] = new boolean[9][9];

    public static boolean blockpossible[][] = new boolean[9][9];
    public static boolean blockpossibleInitial[][] = new boolean[9][9]
+;
    
    public static int blockCount[] = {0,0,0};
    
    static int rowoffset = 0;
    static int recursions = 0;

    /**
     * @param args
     * @throws IOException
     */
    public static void main(String[] args) throws IOException
    {
        long time = System.nanoTime();
        StringBuilder sb = new StringBuilder();

        initializePossibilities();
        //sb.append("initializePossibilities:");
        //sb.append(((double)(System.nanoTime() - time))/1000000000);
        //sb.append("\n");
        initializeFromFile(args[0]);
        sb.append("initializeFromFile:");
        sb.append(((double)(System.nanoTime() - time))/1000000000);
        sb.append("\n");
        sb.append(printTable(loadedTable));
        /*sb.append("printTable:");
        sb.append(((double)(System.nanoTime() - time))/1000000000);
        sb.append("\n");
        sb.append(printTable(initialTable));
        sb.append("printTable:");
        sb.append(((double)(System.nanoTime() - time))/1000000000);
        sb.append("\n");*/
        if (!doSudoku(0, 0))
            sb.append("AAAHHH, it failed....");
        sb.append("\n");
        sb.append("doSudoku:");
        sb.append("\n");
        changeBack();
        /*sb.append(((double)(System.nanoTime() - time))/1000000000);
        sb.append("\n");
        sb.append(printTable(tmpTable));
        sb.append("printTable:");
        sb.append(((double)(System.nanoTime() - time))/1000000000);
        sb.append("\n");*/
        sb.append(printTable(completeTable));
        sb.append("total time:");
        sb.append(((double)(System.nanoTime() - time))/1000000000);
        sb.append("\n");
    sb.append("recursions: " + recursions);
        System.out.println(sb.toString());
    }

    private static boolean doSudoku(int row, int column)
    {
        recursions ++;
        if (column > 8)
        {
            column = 0;
            row++;
            if (row > 8)
                return true;// we got to the end, woot....
        }
        
        if (initialTable[row][column] > 0)
        {
            return doSudoku(row, column + 1);
        }
        int block = (row/3)*3 + column/3;//gotta love integer math....
+This will return 0-8 representing the 9 3x3 grids
        for (int num = 1; num < 10; num++)
        {
            if (rowpossible[row][num] 
                 && columnpossible[column][num] 
                 && blockpossible[block][num])
            {
                tmpTable[row][column] = num;
                rowpossible[row][num] = false;
                columnpossible[column][num] = false;
                blockpossible[block][num] = false;
                if (doSudoku(row, column + 1))
                {
                    return true;
                } 
                tmpTable[row][column] = 0;
                rowpossible[row][num] = true;
                columnpossible[column][num] = true;
                blockpossible[block][num] = true;
            }
        }
        return false;
    }

    private static String printTable(int[][] initialTable2)
    {
        StringBuilder sb = new StringBuilder();
        for (int rows = 0; rows < 9; rows++)
        {
            for (int columns = 0; columns < 9; columns++)
            {
                sb.append(initialTable2[rows][columns]);
                if (columns < 8) sb.append(",");
            }
            sb.append("\n");
        }
        return sb.toString();
    }

    private static void initializeFromFile(String inputFile) throws IO
+Exception
    {
        BufferedReader inp = new BufferedReader(new FileReader(inputFi
+le));
        int i = inp.read();
        int rowcount = 0;
        int columncount = 0;
        int tmp;
        while (i >= 0)
        {
            char c = (char) i;
            if (c == '-')
            {
                initialTable[rowcount][columncount] = 0;
                tmpTable[rowcount][columncount] = 0;
            } else if (c == ',')
            {
                columncount++;
            } else if (c == '\n' || c == '\r')
            {
                i = inp.read();
                if (i == '\n' || i == '\r')
                {
                    i = inp.read();
                }
                rowcount++;
                columncount = 0;
                continue;
            } else
            {
                tmp = Integer.parseInt(Character.toString(c));
                loadedTable[rowcount][columncount] = tmp;
                blockCount[(rowcount/3)]++;
                
                initialTable[rowcount][columncount] = tmp;
                tmpTable[rowcount][columncount] = tmp;
                rowpossible[rowcount][tmp] = false;
                rowpossibleInitial[rowcount][tmp] = false;
                columnpossible[columncount][tmp] = false;
                blockpossible[(rowcount/3)*3 + columncount/3][tmp] = f
+alse;
                blockpossibleInitial[(rowcount/3)*3 + columncount/3][t
+mp] = false;
            }
            i = inp.read();
        }
        
        // shift blocks if needed....
        int biggestBlockRow = 0;
        int maxValue = 0;
        for (int loop = 0; loop < 3; loop++)
        {
            if (blockCount[loop] > maxValue)
            {
                biggestBlockRow = loop;
                maxValue = blockCount[loop];
            }
        }
        System.out.println(biggestBlockRow);
        if (biggestBlockRow == 0) return;
        rowoffset = 9 - 3 * (biggestBlockRow);
        int modOffset;
        for (int loop = 0; loop < 9; loop++)
        {
            modOffset = (loop+rowoffset) < 9?loop + rowoffset:(loop + 
+rowoffset) - 9;
            initialTable[modOffset] = loadedTable[loop].clone();
            tmpTable[modOffset] = loadedTable[loop].clone();
            rowpossible[modOffset] = rowpossibleInitial[loop].clone();
            blockpossible[modOffset] = blockpossibleInitial[loop].clon
+e();
        }
    }

    static void changeBack()
    {
        int modOffset;
        for (int loop = 0; loop < 9; loop++)
        {
            modOffset = (loop+rowoffset) < 9?loop + rowoffset:(loop + 
+rowoffset) - 9;
            completeTable[loop] = tmpTable[modOffset].clone();
        }
    }
    private static void initializePossibilities()
    {
        boolean tmp[] = new boolean[]
                                    { false, true, true, true, true, t
+rue, true, true, true, true };
        for (int loop = 0; loop < 9; loop++)
        {
            rowpossible[loop] = tmp.clone();
            rowpossibleInitial[loop] = tmp.clone();
            columnpossible[loop] = tmp.clone();
            blockpossible[loop] = tmp.clone();
            blockpossibleInitial[loop] = tmp.clone();
        }
                                           
    }

}
[download]