/*
    Copyright (C) 2005 Aymeric Augustin

    This program is free software; you can redistribute it and/or
    modify it under the terms of the GNU General Public License
    as published by the Free Software Foundation; either version 2
    of the License, or (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 */


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

class Case {

    int valeur;
    boolean[] possibles;
    int numPossibles;

    Case() {
        valeur = 0;
        possibles = new boolean[9];
        for (int i = 0; i < 9; i++)
            possibles[i] = true;
        numPossibles = 9;
    }

}

class Coordonnees {

    int l, c;

    Coordonnees(int ll, int cc) {
        l = ll; c = cc;
    }

}

class File {

    private Coordonnees[] coord;
    private int debut;
    private int fin;

    File() {
        coord = new Coordonnees[82];
        debut = 0;
        fin = 81;
    }

    public Coordonnees pop() {
        Coordonnees c = coord[debut];
        debut = (debut + 1) % 82;
        return c;
    }

    public void push(Coordonnees c) {
        fin = (fin + 1) % 82;
        coord[fin] = c;
    }

    public boolean estVide() {
        return longueur() == 0;
    }

    public int longueur() {
        return (fin + 83 - debut) % 82;
    }

}

class SuDoKu {

    Case[][] grille;
    File def;
    int restants;
    boolean contradiction;

    SuDoKu() {
        initSuDoKu(inputGrille());
    }

    SuDoKu(String fileName) {
        initSuDoKu(readGrille(fileName));
    }

    SuDoKu(SuDoKu s) {
        int[][] g = new int[9][9];
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                g[i][j] = s.grille[i][j].valeur;
        initSuDoKu(g);
    }

    SuDoKu(int[][] g) {
        initSuDoKu(g);
    }

    void initSuDoKu(int[][] g) {
        grille = new Case[9][9];
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                grille[i][j] = new Case();
        def = new File();
        restants = 81;
        contradiction = false;
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (g[i][j] != 0)
                    marquer(i, j, g[i][j]);
    }


    static int[][] inputGrille() {
        System.out.println("Entrez la grille ligne par ligne.");
        System.out.println("Mettez un espace pour chaque case vide.");
        byte[] input = new byte[9];
        int[][] g = new int[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++)
                input[j] = '0';
            System.out.print("Ligne numéro " + (i + 1) + " : ");
            try {
                System.in.read(input, 0, 9);
                System.in.skip(10000);
            } catch (IOException e) {
            }
            for (int j = 0; j < 9; j++) {
                if (input[j] > '0' && input[j] <= '9')
                    g[i][j] = input[j] - '0';
                else
                    g[i][j] = 0;
            }
        }
        return g;
    }

    static int[][] readGrille(String fileName) {
        int[][] g = new int[9][9];
        System.out.println("Lecture du fichier " + fileName + ".");
        try {
            FileReader fr = new FileReader(fileName);
            BufferedReader br = new BufferedReader(fr);
            String input = "         \n";
            for (int i = 0; i < 9; i++) {
                input = br.readLine();
                for (int j = 0; j < 9; j++)
                    if (input.charAt(j) > '0' && input.charAt(j) <= '9')
                        g[i][j] = input.charAt(j) - '0';
                    else
                        g[i][j] = 0;
            }
        } catch (IOException e) {
        }
        System.out.println("OK.");
        return g;
    }

    void testMarquer(int i, int j, int n) {
        if (grille[i][j].numPossibles != -1 && grille[i][j].possibles[n - 1]) {
            grille[i][j].possibles[n - 1] = false;
            grille[i][j].numPossibles--;
            if (grille[i][j].numPossibles == 0)
                contradiction = true;
            else if (grille[i][j].numPossibles == 1)
                def.push(new Coordonnees(i, j));
        }
    }

    void marquer(int i, int j, int n) {
        grille[i][j].valeur = n;
        grille[i][j].numPossibles = -1;
        restants--;
        for (int k = 0; k < 9; k++) {
            testMarquer(i, k, n);
            testMarquer(k, j, n);
        }
        int iBase = i - i % 3;
        int jBase = j - j % 3;
        for (int ii = iBase; ii < iBase + 3; ii++)
            for (int jj = jBase; jj < jBase + 3; jj++)
                testMarquer(ii, jj, n);
        if (restants == 0 && !contradiction) {
            System.out.println("");
            System.out.println("Grille complétée :");
            printGrille(System.out);
        }
    }

    void marquer(int i, int j) { // suppose la vérification que numPossible == 1
        int n = 0;
        while (n < 9 && !grille[i][j].possibles[n])
            n++;
        marquer(i, j, n + 1);
    }

    Coordonnees chercheMin() {
        int min = 10;
        Coordonnees co = null;
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
                if (grille[i][j].numPossibles > 0 && grille[i][j].numPossibles < min) {
                    min = grille[i][j].numPossibles;
                    co = new Coordonnees(i, j);
                }
        return co;
    }

    void resoudre() {
        while (!def.estVide() && !contradiction) {
            Coordonnees co = def.pop();
            if (grille[co.l][co.c].numPossibles == 1)
                marquer(co.l, co.c);
        }
        if (restants > 0 && !contradiction) {
            Coordonnees co = chercheMin();
            int m = grille[co.l][co.c].numPossibles;
            SuDoKu s1;
            for (int k = 0; k < 9; k++)
                if (grille[co.l][co.c].possibles[k]) {
                    s1 = new SuDoKu(this);
                    s1.marquer(co.l, co.c, k + 1);
                    s1.resoudre();
                }
        }
    }

    void printGrille(PrintStream ps) {
        for (int i = 0; i < 9; i++) {
            System.out.println(" --- --- --- --- --- --- --- --- --- ");
            for (int j = 0; j < 9; j++)
                if (grille[i][j].valeur != 0)
                    System.out.print("| " + grille[i][j].valeur + " ");
                else
                    System.out.print("|   ");
            System.out.println("|");
        }
        System.out.println(" --- --- --- --- --- --- --- --- --- ");
    }

    public static void main(String[] args) {
        SuDoKu s;
        if (args.length == 1)
            s = new SuDoKu(args[0]);
        else
            s = new SuDoKu();
        System.out.println("");
        System.out.println("Grille de départ :");
        s.printGrille(System.out);
        System.out.println("");
        System.out.println("Résolution en cours...");
        s.resoudre();
    }

}