/**
 * Resic Sudoku pomoci backtrackingu. Tato metoda nezjisti, jestli je dane
 * sudoku resitelne clovekem, ale zda-li ma dane zadani vubec reseni, pripadne
 * kolik takovychto reseni umoznuje (zjisti a vypise vsechna reseni).
 * @author Pavel Micka
 */
public class SudokuSolver {
    /**
     * Velikost ulohy == klasicke Sudoku 9*9, 3x vnitrni ctverec 3*3, kazde cislo
     * (1-9) pouze jednou v radku, sloupci i ctverci
     */
    public static final int SUDOKU_SIZE = 9;
    /**
     * Velikost vnitrnich ctvercu (3*3 dle beznych pravidel)
     */
    public static final int SQUARE_SIZE = 3;
    /**
     * Prazdne pole
     */
    public static final int EMPTY = 0;

    /**
     * Vyresi zadane Sudoku pomoci backtrackingu (najde vsechna reseni)
     * @param array pole zadani
     */
    public static void solveSudoku(int[][] array) {
        if(array.length != SUDOKU_SIZE) throw new IllegalArgumentException("Pole ma mit velikost 9x9");

        boolean[][] fixed = new boolean[SUDOKU_SIZE][SUDOKU_SIZE];
        for (int i = 0; i < array.length; i++) {
            if (array[i].length != SUDOKU_SIZE) throw new IllegalArgumentException("Pole ma mit velikost 9x9");
            for (int j = 0; j < array.length; j++) {
                if (array[i][j] != 0) fixed[i][j] = true;

            }
        }

        //prejdeme na prvni nepredvyplnenou souradnici
        int x = -1;
        int y = 0;
        do {
            x = x + 1; //posun o souradnici dal
            boolean overflow = x >= SUDOKU_SIZE; //pretekl radek?
            if (overflow) {
                x = 0;
                y += 1;
            }
        } while(fixed[y][x]); //dokud je pole zablokovane (soucasti zadani)

        for (int i = 1; i <= SUDOKU_SIZE; i++) {
            solve(array, fixed, x, y, i);
        }
    }
    /**
     * Resi Sudoku
     * @param array pole reseni
     * @param fixed pole, ve kterem true znamena, ze jde o hodnotu ze zadani,
     * @false, ze jde o hodnotu resitele
     * @param x souradnice x, na kterou se bude pridavat dalsi hodnota
     * @param y souradnice y, na kterou se bude pridavat dalsi hodnota
     * @param value hodnota
     */
    private static void solve(int[][] array, boolean[][] fixed, int x, int y, int value) {
        if (!checkConsistency(array, x, y, value)) return; //reseni neni konzistentni
        array[y][x] = value; //set
        do {
            x = x + 1; //posun o souradnici dal
            boolean overflow = x >= SUDOKU_SIZE; //pretekl radek?
            if (overflow) {
                x = 0;
                y += 1;
                if (y == SUDOKU_SIZE) { //pretekl sloupec...konec reseni
                    printArray(array);
                    return;
                }
            }
        } while(fixed[y][x]);//dokud je pole zablokovane (soucasti zadani)
        for (int i = 1; i <= SUDOKU_SIZE; i++) { //backtrack
            solve(array, fixed, x, y, i);
        }
        array[y][x] = EMPTY; //reset policka (aby neprekazelo pri backtracku)
    }
    /**
     * Zkontroluje, jestli je reseni stale korektni
     * @param array pole reseni
     * @param x x souradnice, na kterou je pridavana hodnota
     * @param y y souradnice, na kterou je pridavana hodnota
     * @param value hodnota
     * @return true - pokud je reseni konzistentni, false - pokud reseni neni konzistentni
     */
    private static boolean checkConsistency(int[][] array, int x, int y, int value) {
        //Sloupec
        for (int i = 0; i < array.length; i++) {
            if (i != y && array[i][x] == value) return false;
        }
        //radek
        for (int i = 0; i < array[y].length; i++) {
            if (i != x && array[y][i] == value) return false;
        }
        //ctverec
        int vertical = y/SQUARE_SIZE; //o kolikaty vertikalni ctverec se jedna
        int horizontal = x/SQUARE_SIZE; //o kolikaty horizontalni ctverec se jedna

        for (int i = vertical*SQUARE_SIZE; i < vertical*SQUARE_SIZE + SQUARE_SIZE; i++) {
            for (int j = horizontal*SQUARE_SIZE; j < horizontal*SQUARE_SIZE + SQUARE_SIZE; j++) {
                if (array[i][j] == value) return false;
            }
        }
        return true;
    }
    /**
     * Vypise pole Sudoku
     * @param array pole sudoku
     */
    private static void printArray(int[][] array) {
        for (int i = 0; i < array.length; i++){
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + "|");
            }
            System.out.println("");
        }
        System.out.println("");
    }
}

/**
 * Resicka sudoku vyuzivajici "lidske" strategie
 * @author Pavel Micka
 */
public class HumanizedSudokuSolver {
    private SudokuField[][] sudoku;
    private SudokuStrategy[] strategies;

    /**
     * Zkonstruuje resicku pro zadane sudoku
     * @param setting zadani sudoku, 0 znaci prazdne pole
     * @param strategies pole strategii, ktere maji byt pouzity
     */
    HumanizedSudokuSolver(int[][] setting, SudokuStrategy... strategies) {
        this.strategies = strategies;
        sudoku = new SudokuField[setting.length][setting.length];
        for (int i = 0; i < setting.length; i++) {
            for (int j = 0; j < setting[i].length; j++) {
                if (setting[i][j] == 0) {
                    sudoku[i][j] = new SudokuField();
                } else {
                    sudoku[i][j] = new SudokuField(setting[i][j]);
                }
            }
        }
    }
    /**
     * Vrati reseni sudoku
     * @return
     */
    public int[][] solve() {
        boolean succ;
        do{
            succ = false;
            for (SudokuStrategy s : strategies) {
                succ = s.solve(sudoku);
                if (succ) {
                    break;
                }
            }
        } while(succ);

        int[][] solution = new int[sudoku.length][sudoku.length];
        for (int i = 0; i < sudoku.length; i++) {
            for (int j = 0; j < sudoku.length; j++) {
                solution[i][j] = sudoku[i][j].getSolution();
            }
        }

        return solution;


    }



    /**
     * Testovaci main metoda
     * Program vyresi, co umi, coz jsou s temito strategiemi cca. az pokrocila
     * Sudoku a vypise vysledek
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        int[][] setting = { //MF DNES 23.8.2010, priloha leto
            {0, 0, 4, 0, 3, 6, 9, 2, 7},
            {1, 0, 0, 0, 0, 5, 0, 0, 0},
            {0, 0, 0, 2, 0, 0, 0, 0, 4},
            {0, 0, 5, 0, 0, 0, 0, 6, 0},
            {6, 4, 0, 0, 0, 0, 0, 8, 5},
            {0, 7, 0, 0, 0, 0, 2, 0, 0},
            {5, 0, 0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 7, 0, 0, 0, 0, 2},
            {4, 3, 7, 9, 2, 0, 5, 0, 0}
        };
        SudokuStrategy[] s = {new OneInARowStrategy(), new OneInAColumnStrategy(), new OneInAGroupStrategy()};
        HumanizedSudokuSolver solver = new HumanizedSudokuSolver(setting, s);
        int[][] solution = solver.solve();
        for (int i = 0; i < solution.length; i++) {
            for (int j = 0; j < solution.length; j++) {
                System.out.print(solution[i][j] + " ");
            }
            System.out.println("");
        }
    }
}

/**
 * Specifikuje metodu, kterou by mely mit vsechny strategie pro reseni Sudoku
 * @author Pavel Micka
 */
interface SudokuStrategy {

    /**
     * Provede jeden krok reseni Sudoku
     * @param sudoku pole obsahujici sudoku, 0 oznacuje prazdna mista
     * @return true pokud se povedlo krok provest, false v opacnem pripade
     */
    public boolean solve(SudokuField[][] sudoku);
}

/**
 * Strategie, ktera rika, ze v jednom radku smi byt dane cislo pouze jednou
 * @author Pavel Micka
 */
class OneInARowStrategy implements SudokuStrategy {

    public boolean solve(SudokuField[][] sudoku) {
        for (int i = 0; i < sudoku.length; i++) {
            for (int j = 0; j < sudoku[i].length; j++) {
                int solution = sudoku[i][j].getSolution();
                if (solution != 0) { //pokud pole neni vyreseno
                    for (int k = 0; k < sudoku[i].length; k++) { //overme radku na kandidaty
                        if (sudoku[i][k].getSolution() == 0) { //pokud dane pole neni vyreseno
                            if (sudoku[i][k].hasCandidate(solution)) { //a pokud ma kandidata
                                sudoku[i][k].removeCandidate(solution); //tak kandidata odstranime
                                System.out.println("OneInARow: Odstranuji kandidata " + solution
                                        + " na souradnicich x: " + k + " y: " + i);
                                return true; //a vratime uspech
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
}

/**
 * Strategie, ktera rika, ze v jednom sloupci smi byt dane cislo pouze jednou
 * @author Pavel Micka
 */
class OneInAColumnStrategy implements SudokuStrategy {

    public boolean solve(SudokuField[][] sudoku) {
        for (int i = 0; i < sudoku.length; i++) {
            for (int j = 0; j < sudoku[i].length; j++) {
                int solution = sudoku[j][i].getSolution();
                if (solution != 0) { //pokud pole neni vyreseno
                    for (int k = 0; k < sudoku.length; k++) { //overme sloupec na kandidaty
                        if (sudoku[k][i].getSolution() == 0) { //pokud dane pole neni vyreseno
                            if (sudoku[k][i].hasCandidate(solution)) { //a pokud ma kandidata
                                sudoku[k][i].removeCandidate(solution); //tak kandidata odstranime
                                System.out.println("OneInAColumn: Odstranuji kandidata " + solution
                                        + " na souradnicich x: " + i + " y: " + k);
                                return true; //a vratime uspech
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
}

/**
 * Strategie, ktera rika, ze v jedne skupine muze byt dane cislo pouze jednou
 * @author Pavel Micka
 */
class OneInAGroupStrategy implements SudokuStrategy {

    public boolean solve(SudokuField[][] sudoku) {
        int groupCount = (int) Math.sqrt(sudoku.length); //pocitame se ctvercovym sudoku, pocet skupin na radku a sloupec
        for (int i = 0; i < sudoku.length; i++) {
            for (int j = 0; j < sudoku[i].length; j++) {
                int solution = sudoku[i][j].getSolution();
                if (solution != 0) { //pokud pole neni vyreseno
                    for (int k = i - (i % groupCount); k < i - (i % groupCount) + groupCount; k++) {//radky
                        for (int l = j - (j % groupCount); l < j - (j % groupCount) + groupCount; l++) {//sloupce
                            if (sudoku[k][l].getSolution() == 0){ //pokud pole jeste neni vyreseno
                                if (sudoku[k][l].hasCandidate(solution)){ //a ma odpovidajiciho kandidata
                                    sudoku[k][l].removeCandidate(solution);
                                System.out.println("OneInAGroup: Odstranuji kandidata " + solution
                                        + " na souradnicich x: " + l + " y: " + k);
                                    return true;
                                }
                            }
                        }
                    }
                }
            }
        }
        return false;
    }
}

/**
 * Trida policka sudoku
 * @author Pavel Micka
 */
class SudokuField {

    /**
     * Mnozina kandidatu
     */
    private Set<Integer> candidates;

    /**
     * Vytvori policko, kandidaty jsou cisla 1-9
     */
    public SudokuField() {
        this.candidates = new HashSet<Integer>();
        for (int i = 1; i <= 9; i++) {
            candidates.add(i);
        }
    }

    /**
     * Vytvori policko s jedinym kandidatem (resenim)
     * @param nr reseni
     */
    public SudokuField(int nr) {
        this.candidates = new HashSet<Integer>();
        candidates.add(nr);
    }

    /**
     * Zjisti, jestli je dane cislo kandidatem tohoto pole
     * @param nr cislo
     * @return true pokud je cislo kandidatem, false jinak
     */
    public boolean hasCandidate(int nr) {
        return candidates.contains(nr);
    }
    /**
     * Odstrani kandidata
     * @param nr kandidat
     */
    public void removeCandidate(int nr) {
        boolean succ = candidates.remove(nr);
        assert succ;
    }

    /**
     * Vrati cislo, ktere je resenim tohoto policka
     * @return cislo, ktere je resenim, 0 pokud jeste pole nebylo vyreseno
     */
    public int getSolution() {
        if (candidates.size() != 1) {
            return 0;
        } else {
            return (Integer) (candidates.toArray()[0]);
        }
    }
}

/**
 * Resic Sudoku pomoci backtrackingu. Tato metoda nezjisti, jestli je dane
 * sudoku resitelne clovekem, ale zda-li ma dane zadani vubec reseni, pripadne
 * kolik takovychto reseni umoznuje (zjisti a vypise vsechna reseni).
 * @author Pavel Micka
 */
class SudokuSolver {
public:
    /**
     * Velikost ulohy == klasicke sudoku 9*9, 3x vnitrni ctverec 3*3, kazde cislo
     * (1-9) pouze jednou v radku, sloupci i ctverci
     */
    static const int SUDOKU_SIZE = 9;
    /**
     * Velikost vnitrnich ctvercu (3*3 dle beznych pravidel)
     */
    static const int SQUARE_SIZE = 3;
    /**
     * Prazdne pole
     */
    static const int EMPTY = 0;

    /**
     * Vyresi zadane Sudoku pomoci backtrackingu (najde vsechna reseni)
     * @param array pole zadani
     */
    static void solveSudoku(int ** array) {
        bool ** fixed = new bool *[SUDOKU_SIZE];
        for (int i = 0; i < SUDOKU_SIZE; i++) {
            fixed[i] = new bool[SUDOKU_SIZE];
        }
        
        for (int i = 0; i < SUDOKU_SIZE; i++) {
            for (int j = 0; j < SUDOKU_SIZE; j++) {
                if (array[i][j] != 0) fixed[i][j] = true;
                else fixed[i][j] = false;
            }
        }

        //prejdeme na prvni nepredvyplnenou souradnici
        int x = -1;
        int y = 0;
        do {
            x = x + 1; //posun o souradnici dal
            bool overflow = x >= SUDOKU_SIZE; //pretekl radek?
            if (overflow) {
                x = 0;
                y += 1;
            }
        } while (fixed[y][x]);//dokud je pole zablokovane (soucasti zadani)

        for (int i = 1; i <= SUDOKU_SIZE; i++) {
            solve(array, fixed, x, y, i);
        }

        //dealokace
        for (int i = 0; i < SUDOKU_SIZE; i++) delete fixed[i];
        delete[] fixed;

    }
private:
    /**
     * Resi Sudoku
     * @param array pole reseni
     * @param fixed pole, ve kterem true znamena, ze jde o hodnotu ze zadani,
     * @false, ze jde o hodnotu resitele
     * @param x souradnice x, na kterou se bude pridavat dalsi hodnota
     * @param y souradnice y, na kterou se bude pridavat dalsi hodnota
     * @param value hodnota
     */
    static void solve(int ** array, bool ** fixed, int x, int y, int value) {
        if (!checkConsistency(array, x, y, value)) return; //reseni neni konzistentni
        array[y][x] = value; //set
        do {
            x = x + 1; //posun o souradnici dal
            bool overflow = x >= SUDOKU_SIZE; //pretekl radek?
            if (overflow) {
                x = 0;
                y += 1;
                if (y == SUDOKU_SIZE) { //pretekl sloupec...konec reseni
                    printArray(array);
                    return;
                }
            }
        } while(fixed[y][x]);//dokud je pole zablokovane (soucasti zadani)
        for (int i = 1; i <= SUDOKU_SIZE; i++) { //backtrack
            solve(array, fixed, x, y, i);
        }
        array[y][x] = EMPTY; //reset policka (aby neprekazelo pri backtracku)
    }
    /**
     * Zkontroluje, jestli je reseni stale korektni
     * @param array pole reseni
     * @param x x souradnice, na kterou je pridavana hodnota
     * @param y y souradnice, na kterou je pridavana hodnota
     * @param value hodnota
     * @return true - pokud je reseni konzistentni, false - pokud reseni neni konzistentni
     */
    static bool checkConsistency(int ** array, int x, int y, int value) {
        //Sloupec
        for (int i = 0; i < SUDOKU_SIZE; i++) {
            if (i != y && array[i][x] == value) return false;
        }
        //radek
        for (int i = 0; i < SUDOKU_SIZE; i++) {
            if (i != x && array[y][i] == value) return false;
        }
        //ctverec
        int vertical = y/SQUARE_SIZE; //o kolikaty vertikalni ctverec se jedna
        int horizontal = x/SQUARE_SIZE; //o kolikaty horizontalni ctverec se jedna

        for (int i = vertical*SQUARE_SIZE; i < vertical*SQUARE_SIZE + 3; i++) {
            for (int j = horizontal*SQUARE_SIZE; j < horizontal*SQUARE_SIZE + 3; j++) {
                if (array[i][j] == value) return false;
            }
        }
        return true;
    }
    /**
     * Vypise pole Sudoku
     * @param array pole sudoku
     */
    static void printArray(int ** array) {
        for (int i = 0; i < SUDOKU_SIZE; i++) {
            for (int j = 0; j < SUDOKU_SIZE; j++) {
                cout << array[i][j] << "|";
            }
            cout << "\\n";
        }
        cout << "\\n";
    }
};