Sudoku Solver

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

public class Solver {
    FastScanner in;
    PrintWriter out;

    int n = 9;
    char[][] a = new char[n][n];
    boolean[] was = new boolean[n + 1];

    boolean isOk() {
        for (int i = 0; i < n; i++) {
            Arrays.fill(was, false);
            for (int j = 0; j < n; j++) {
                int x = a[i][j] == '.' ? -1 : a[i][j] - '0';
                if (x == -1)
                    continue;
                if (was[x])
                    return false;
                was[x] = true;
            }
        }
        for (int i = 0; i < n; i++) {
            Arrays.fill(was, false);
            for (int j = 0; j < n; j++) {
                int x = a[j][i] == '.' ? -1 : a[j][i] - '0';
                if (x == -1)
                    continue;
                if (was[x])
                    return false;
                was[x] = true;
            }
        }
        for (int stX = 0; stX < n; stX += n / 3)
            for (int stY = 0; stY < n; stY += n / 3) {
                Arrays.fill(was, false);
                for (int j = 0; j < n; j++) {
                    int dx = j % (n / 3);
                    int dy = j / (n / 3);
                    int x = a[stX + dx][stY + dy] == '.' ? -1 : a[stX + dx][stY
                            + dy] - '0';
                    if (x == -1)
                        continue;
                    if (was[x])
                        return false;
                    was[x] = true;
                }
            }
        return true;
    }

    boolean go(int fromX, int fromY) {
        while (fromX < n) {
            if (fromY >= n) {
                fromY = 0;
                fromX++;
            }
            if (fromX == n)
                break;
            if (a[fromX][fromY] != '.') {
                fromY++;
            } else {
                break;
            }
        }
        if (fromX == n)
            return true;
        for (int x = 1; x <= n; x++) {
            char c = (char) ('0' + x);
            a[fromX][fromY] = c;
            if (isOk()) {
                if (go(fromX, fromY + 1)) {
                    return true;
                } else {
                    a[fromX][fromY] = '.';
                }
            } else {
                a[fromX][fromY] = '.';
            }
        }
        return false;
    }

    void solve() {
        long time = System.currentTimeMillis();
        for (int i = 0; i < n; i++) {
            String s = in.next();
            for (int j = 0; j < n; j++)
                a[i][j] = s.charAt(j);
        }
        if (isOk())
            go(0, 0);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                out.print(a[i][j]);
            }
            out.println();
        }
        System.err.println(System.currentTimeMillis() - time);
    }

    void run() {
        try {
            in = new FastScanner(new File("sudoku.in"));
            out = new PrintWriter(new File("sudoku.out"));

            solve();

            out.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    void runIO() {

        in = new FastScanner(System.in);
        out = new PrintWriter(System.out);

        solve();

        out.close();
    }

    class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner(File f) {
            try {
                br = new BufferedReader(new FileReader(f));
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            }
        }

        public FastScanner(InputStream f) {
            br = new BufferedReader(new InputStreamReader(f));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    public static void main(String[] args) {
        new Solver().run();
    }
}