import java.io.PrintWriter;
import java.util.*;

public class Konsole {

    public static void main(String[] args) {
        System.out.println("Sudoku solver 1.0\n\tType help for help.");
        Sudoku S = new Sudoku();                                        // the instance of the class Sudoku is the core of the program
        Scanner input = new Scanner(System.in);
        String cmd = new String();                                      // the whole input will be saved here
        String cmdType = new String();                                  // saves the first token of the command
        int x,y,z,i,j;                                                  // some auxiliary variables
        int[][] outArray = new int[9][9];                               // will be needed for the command "show"
        int[] poss = new int[9];                                        // will be needed for the command "list x y"
        boolean test;

        // infinite loop for input
        while(true) {
            for (i=0;i<9;i++)
                poss[i] = 0;                                            // clears the array "poss"

            System.out.println("\nWaiting for input...");

            cmd = input.nextLine();                                     // command input

            StringTokenizer cut = new StringTokenizer(cmd);

            if (cut.hasMoreTokens())
                cmdType = cut.nextToken();                              // is there any command?

            if (cmdType.equals("exit")) {
                break;
            }

            if (cmdType.equals("help")) {
                System.out.println("\nFollowing commands are available:");
                System.out.println("set x y value\tsets field (x,y) to value");
                System.out.println("unset x y\tsets (x,y) to 0");
                System.out.println("get x y\t\tdisplays the value of (x,y)");
                System.out.println("list x y\tlists the possible solutions for (x,y)");
                System.out.println("solve\t\tsolves the sudoku");
                System.out.println("show\t\tdisplays the complete Sudoku");
                System.out.println("help\t\tdisplays this help");
                System.out.println("exit\t\texits the program");
                System.out.println("credits\t\tdisplays some information about the author of\n\t\tthis program");
                continue;
            }

            if (cmdType.equals("set")) {                                // defines values for fields
                x = Integer.valueOf(cut.nextToken());
                y = Integer.valueOf(cut.nextToken());
                z = Integer.valueOf(cut.nextToken());
                S.setField(x,y,z);
                System.out.println("\nField ("+x+","+y+") is set to "+z+".");
                continue;
            }

            if (cmdType.equals("get")) {                                // a relict of an old version, but you never know if you will need it again...
                x = Integer.valueOf(cut.nextToken());
                y = Integer.valueOf(cut.nextToken());
                z = S.getField(x,y);
                System.out.println("\nThe value of field ("+x+","+y+") is "+z+".");
                continue;
            }

            if (cmdType.equals("unset")) {                              // short (?) version of set x y 0
                x = Integer.valueOf(cut.nextToken());
                y = Integer.valueOf(cut.nextToken());
                S.setField(x,y,0);
                System.out.println("\nField ("+x+","+y+") is set to 0.");
                continue;
            }

            if (cmdType.equals("show")) {                               // shows the full grid instead of one field
                outArray = S.writeOutput();
                for (i=0;i<9;i++) {
                    System.out.print("\n-------------------------------------\n| ");
                    for (j=0;j<9;j++) {
                        if (outArray[j][i] != 0) {
                            System.out.print(outArray[j][i]+" | ");
                        } else {
                            System.out.print("  | ");
                        }
                    }
                }
                System.out.println("\n-------------------------------------\n");
                continue;
            }

            if (cmdType.equals("list")) {                               // lists the possible values of a field
                x = Integer.valueOf(cut.nextToken());
                y = Integer.valueOf(cut.nextToken());
                poss = S.listPossibilities(x,y);
                System.out.print("\nPossible Solutions for ("+x+","+y+") are:");
                for (i=0;i<9;i++) {
                    if (poss[i] != 0)
                        System.out.print(" "+poss[i]);
                }
                System.out.print("\n");
                continue;
            }

            if (cmdType.equals("solve")) {                               // solving algorithm
                for (x=1;x<30;x++) {
                    S.compScan();
                    S.fullSolve();
                }
                if (S.backtrack(0,0)) {
                    System.out.println("Solved.");
                } else {
                    System.out.println("Couldn't solve the sudoku.");
                }
                continue;
            }

            if (cmdType.equals("credits")) {                            // some information about me :)
                System.out.println("\t  Sudoku solver has been coded by\n");
                System.out.println("\t\tAlexander M. Fabisch");
                System.out.println("\t      alexander.fabisch@web.de");
                continue;
            }

        System.out.println("Unknown command.");                         // if the input doesn't equal to any command, the command is unknown ;)
        }
    }

}

class Sudoku {

    int[][][] grid = new int[9][9][10];
    int[][] outArray = new int[9][9];

    Sudoku() {
        int i,j,k;
        // initializing grid
        for (i=0;i<9;i++) {
            for (j=0;j<9;j++) {
                for (k=0;k<10;k++) {
                    grid[i][j][k] = k;
                }
            }
        }
    }

    int[][] writeOutput() {
        int i,j;
        for (i=0;i<9;i++) {
            for (j=0;j<9;j++) {
                outArray[i][j] = grid[i][j][0];
            }
        }
        return outArray;
    }

    int[] listPossibilities(int x, int y) {
        int[] poss = new int[9];
        int i,j;
        j = 0;
        for (i=1;i<10;i++) {
            if (grid[x-1][y-1][i] != 0)
                poss[j++] = i;
        }
        return poss;
    }

    void setField(int x, int y, int z) {
        int i;
        grid[x-1][y-1][0] = z;
    }

    int getField(int x, int y) {
        return grid[x-1][y-1][0];
    }

    void scanArray(int xmin, int xmax, int ymin, int ymax) {
        boolean[] values = new boolean[9];
        int i,j,k;
        xmin--;
        xmax--;
        ymin--;
        ymax--;
        for (i=xmin;i<=xmax;i++) {
            for (j=ymin;j<=ymax;j++) {
                if (grid[i][j][0] != 0) {
                    values[grid[i][j][0]-1] = true;
                }
            }
        }

        for (i=xmin;i<=xmax;i++) {
            for (j=ymin;j<=ymax;j++) {
                if (grid[i][j][0] == 0) {
                    for (k=1;k<10;k++) {
                        if ((grid[i][j][k]==k) && (values[k-1]))
                            grid[i][j][k]=0;
                    }
                }
            }
        }
    }

    void compScan() {
        int i,j;
        for (i=1;i<10;i++) {
            // rows
            this.scanArray(1,9,i,i);
            // columns
            this.scanArray(i,i,1,9);
        }
        for (i=1;i<8;i+=3) {
            for (j=1;j<8;j+=3) {
                this.scanArray(i,i+2,j,j+2);
            }
        }
    }

    void nakedSingle(int x, int y) {
        int i,j,k;
        j=0;
        k=0;
        for (i=1;i<10;i++) {
            if (grid[x-1][y-1][i] != 0) {
                j++;
                k = i;
            }
        }

        if (j == 1) {
            grid[x-1][y-1][0] = k;
            grid[x-1][y-1][k] = 0;
        }
    }


    void hiddenSingle(int x, int y) {
        boolean hs;
        int i,j,k,n,m;
        for (i=1;i<10;i++) {
            hs = true;
            if (grid[x-1][y-1][i] != 0) {
                for (j=0;j<9;j++) {
                    if (grid[x-1][j][i] != 0) {
                        hs = false;
                    }
                }
                if (hs)
                    this.setField(x+1,y+1,i);
                hs = true;
                for (j=0;j<9;j++) {
                    if (grid[j][y-1][i] != 0) {
                        hs = false;
                    }
                }
                if (hs)
                    this.setField(x+1,y+1,i);
                hs = true;
                n = x-((x-1)%3)-1;
                m = y-((y-1)%3)-1;
                for (j=n;j<=n+2;j++) {
                    for (k=m;k<=m+2;k++) {
                        if (grid[j][k][i] != 0) {
                            hs = false;
                        }
                    }
                }
                if (hs)
                    this.setField(x+1,y+1,i);
            }
        }
    }

    void fullSolve() {
        int i,j;
        for (i=1;i<10;i++) {
            for (j=1;j<10;j++) {
                this.nakedSingle(i,j);
                this.hiddenSingle(i,j);
            }
        }
    }

    boolean gridSolved() {
        int i,j;
        boolean solved = true;
        for (i=0;i<9;i++) {
            for (j=0;j<9;j++) {
                if (grid[i][j][0] == 0)
                    solved = false;
            }
        }
        return solved;
    }

    boolean contradiction(int x, int y) {

        int i,j;
        boolean ok = true;

        HashSet<Integer> Co = new HashSet<Integer>();
        HashSet<Integer> Ro = new HashSet<Integer>();
        HashSet<Integer> Sq = new HashSet<Integer>();

        for (i=0;i<9;i++) {
            if (grid[x][i][0]!=0) {
                ok = Co.add(grid[x][i][0]);
                if (!ok)
                    return true;
            }
            if (grid[i][y][0]!=0) {
                ok = Ro.add(grid[i][y][0]);
                if (!ok)
                    return true;
            }
        }

        for (i=x-(x%3);i<=x-(x%3)+2;i++) {
            for (j=y-(y%3);j<=y-(y%3)+2;j++) {
                if (grid[i][j][0]!=0) {
                    ok = Sq.add(grid[i][j][0]);
                    if (!ok)
                        return true;
                }
            }
        }

    return false;
    }

    int[] setCoord(int x, int y) {
        int[] Coord = new int[2];
        if (x==8) {
            x=0;
            y++;
        } else {
            x++;
        }
        Coord[0] = x;
        Coord[1] = y;
        return Coord;
    }

    boolean backtrack(int x, int y) {
        int i;
        int[] Coord = new int[2];

        if (this.contradiction(x,y))
            return false;

        if (this.gridSolved())
            return true;

        if (x!=0 || y!=0) {
            Coord = setCoord(x,y);
            x = Coord[0];
            y = Coord[1];
        }

        if (grid[x][y][0] != 0) {
            Coord = setCoord(x,y);
            x = Coord[0];
            y = Coord[1];
            if (this.backtrack(x,y))
                return true;
        }
 
        for (i=1;i<10;i++) {
            if (grid[x][y][i]==i) {
                grid[x][y][0]=i;
                if (this.backtrack(x,y))
                    return true;
            }
        }

        return false;

    }

}