/*
 * MagickyCverec.java
 *
 * Vytvoreno 27. březen 2007, 14:28 GMT
 *
 */
package cz.cvut.fel.cs.x36pjv.magickyctverec;

import java.util.Collection;
import java.util.HashSet;
import java.util.Arrays;
import java.text.DecimalFormat;

/**
 * Reseni magickeho ctverce pruchodem do hloubky
 * - prvni nalezene reseni nebo hlaseni ze zadne neexistuje
 *
 * @author Tomas Kadlec
 */
public class MagickyCverec {
    // konstanty pro generovani nahodnych magickych ctvercu
    private static final int POCET_PRUCHODU_GENERATORU = 10000;
    private static final int MIN_ROZMER = 3;
    private static final int MAX_ROZMER = 4;
    
    // rozmery ulohy
    private int n, ns, n2, k;
    
    // magicky ctverec
    private int[][] ctverec;
    private int soucet;
    
    // kolekce, zasobnik
    private Collection<Integer> volnaCisla;
    private Zasobnik zasobnik;
    
    // formatovac cisel
    private static DecimalFormat df;
    static {
        df = new DecimalFormat("000");
    }
    
    /**
     * metoda pro vygenerovani nahodneho nezaporneho celeho cisla
     *
     * @param min - dolni mez intervalu
     * @param max - horni mez intervalu
     * @throws Exception kdyz min >= max, nebo min nebo max je zaporne
     * @returns nezaporne cele cislo z intervalu <min,max)
     */
;    private static int randomInt(int min, int max) throws MagickyCtverecGeneratorException {
        if (min < 0 || max < 0 || min >= max)
            throw new MagickyCtverecGeneratorException(min, max);
        return (min + ((int)(Math.random()*(max - min))));
    }
    
    /**
     * generator vychozi konfigurace, pozor muze vyhodit vyjimku - ne vzdy se musi podarit
     * vypocitat vhodnou pocatecni konfiguraci (pokud to chcete nekdo naprogramovat poradne
     * tak samozrejme nikomu nebranim, jen se musi zachovat podminka n^2/4 <= k <= n^2/2)
     *
     * @param pocetPruchodu urcuje, jak dlouho se generator bude snazit
     * @throws MagickyCtverecException kdyz se nepodari vygenerovat pocatecni konfiguraci
     */
    public void generator(int pocetPruchodu)throws MagickyCtverecException {
        int[] limitRadky = new int[n];
        int[] limitSloupce = new int[n];
        Arrays.fill(limitRadky, n);
        Arrays.fill(limitSloupce, n);
        for (int i = 1; i <= k; i++) {
            int radek, sloupec, hodnota, pruchod = 0;
            
            // pozor na tenhle kod, je to docela proti vsemu javovskemu
            znova:
            do {
                
                radek = randomInt(0, n);
                sloupec = randomInt(0, n);          
                hodnota = randomInt(1, n2 + 1); // vcetne druhe mocniny rozmeru
                             
                // kontrola poctu pruchodu
                if (pruchod++ >= pocetPruchodu)
                    break;
                        
                // neni misto uz obsazeno a mame jeste vubec hodnotu k dispozici a neporusujeme podminku,
                // ze musi v kazdem radku i sloupci zustat dve volne pozice
                else if (ctverec[radek][sloupec] != 0 || !volnaCisla.contains(new Integer(hodnota)) || limitRadky[radek] <= 2 || limitSloupce[sloupec] <= 2)
                    continue znova;
                
                // vsechno je splneno - mame vhodnou pozici i vhodne cislo
                else 
                    break;
                
            } while (true);
            
            // ulozeni, pokud lze
            if (ctverec[radek][sloupec] == 0 && volnaCisla.contains(new Integer(hodnota)) && limitRadky[radek] >= 2 && limitSloupce[sloupec] >= 2) {
                volnaCisla.remove(new Integer(hodnota));
                limitRadky[radek]--;
                limitSloupce[sloupec]--;
                ctverec[radek][sloupec] = hodnota;
            }
            // nebo vyhozeni vyjimky
            else
               throw new MagickyCtverecInstanceException();
        }
    }
    
    /**
     * konstruktor bez parametru pro tridu MagickyCverec
     * vygeneruje nahodnou instanci a nakonec spusti jeji reseni
     */
    public MagickyCverec() throws MagickyCtverecException {
        System.out.println("INICIALIZACE:");
        // zasobnik
        zasobnik = new Zasobnik();
        
        // vypocet rozmeru - chceme i vcetne MAX_ROZMER a navic si pridame bunky pro soucty
        n = randomInt(MIN_ROZMER, MAX_ROZMER + 1);
        ns = n + 1;
        n2 = n * n;
        // pocet nahodne umistenych cisel
        k = randomInt((int) Math.round(n2 / (double) 4), (int) Math.round(n2 / (double) 2));
        
        System.out.println(" rozmer n = " + n + "\n rozmer vc. souctu ns = " + ns + "\n druha mocnina rozmeru n2 = " + n2
                           + "\n nahodne umisteno cisel k = " + k);
        
        // inicializace cisel, ktera jsou k dispozici
        volnaCisla = new HashSet<Integer>(n2);
        for (int i = 1; i <= n2; i++) {
            soucet += 2 * i; // kazde cislo se ucastni souctu v jednom radku a jednom sloupci
            volnaCisla.add(new Integer(i));
        }
        soucet /= 2 * n; // souctu je tolik jako radku a sloupcu
        System.out.println(" volnaCisla (" + volnaCisla.size() + ") = " + volnaCisla + "\n soucet = " + soucet);

        // inicializace pole, vychozi konfigurace
        ctverec = new int[ns][ns];
        generator(POCET_PRUCHODU_GENERATORU);
        System.out.println(" volnaCisla (" + volnaCisla.size() + ") = " + volnaCisla);
    }
    
    /**
     * konstruktor pro tridu MagickyCverec
     * inicializuje ctverec jednou ze ctyr instanci
     * @param velikost velikost instance, pripustna hodnota: 3, 4
     * @param resitelnost true pokud ma byt instance resitelna, jinak false
     * @throws MagickyCtverecKonstruktorException pokud nejsou parametry v poradku
     */    
    public MagickyCverec(int velikost, boolean resitelnost) throws MagickyCtverecKonstruktorException {
        if (!(velikost == 3 || velikost == 4))
            throw new MagickyCtverecKonstruktorException();
         System.out.println("INICIALIZACE (" + velikost + ", " + resitelnost + "):");
        // zasobnik
        zasobnik = new Zasobnik();
        
        // vypocet rozmeru - chceme i vcetne MAX_ROZMER a navic si pridame bunky pro soucty
        n = velikost;
        ns = n + 1;
        n2 = n * n;
        // pocet umistenych cisel
        k = -1;
        
        System.out.println(" rozmer n = " + n + "\n rozmer vc. souctu ns = " + ns + "\n druha mocnina rozmeru n2 = " + n2
                           + "\n umisteno cisel k = " + k);
        
        // inicializace cisel, ktera jsou k dispozici
        volnaCisla = new HashSet<Integer>(n2);
        for (int i = 1; i <= n2; i++) {
            soucet += 2 * i; // kazde cislo se ucastni souctu v jednom radku a jednom sloupci
            volnaCisla.add(new Integer(i));
        }
        soucet /= 2 * n; // souctu je tolik jako radku a sloupcu
        System.out.println(" volnaCisla (" + volnaCisla.size() + ") = " + volnaCisla + "\n soucet = " + soucet);

        // inicializace pole, vychozi konfigurace - resitelna, neresitelna
        ctverec = new int[ns][ns];
        if (velikost == 3 && resitelnost) {
            ctverec[0][2] = 4;
            ctverec[1][0] = 7;
            volnaCisla.remove(new Integer(4)); volnaCisla.remove(new Integer(7));
            k = 2;
        }
        else if (velikost == 3) {
            ctverec[0][2] = 5;
            ctverec[2][0] = 7;
            volnaCisla.remove(new Integer(5)); volnaCisla.remove(new Integer(7));
            k = 2;
        }
        else if (velikost == 4 && resitelnost) {
            ctverec[0][0] = 4;
            ctverec[1][1] = 7;
            ctverec[1][2] = 6;
            ctverec[2][0] = 5;
            ctverec[3][3] = 13;
            volnaCisla.remove(new Integer(4)); volnaCisla.remove(new Integer(7));
            volnaCisla.remove(new Integer(6)); volnaCisla.remove(new Integer(5));
            volnaCisla.remove(new Integer(13));
            k = 5;
        }
        else if (velikost == 4) {
            ctverec[0][0] = 4;
            ctverec[1][1] = 7;
            ctverec[1][2] = 6;
            ctverec[2][0] = 5;
            ctverec[3][3] = 14;
            volnaCisla.remove(new Integer(4)); volnaCisla.remove(new Integer(7));
            volnaCisla.remove(new Integer(6)); volnaCisla.remove(new Integer(5));
            volnaCisla.remove(new Integer(14));
            k = 5;
        }
        System.out.println(" volnaCisla (" + volnaCisla.size() + ") = " + volnaCisla);
    }
    
    /**
     * vyresi magicky ctverec
     * @return true, pokud reseni existuje, false jinak
     * @throws ZasobnikJePrazdnyException kvuli pouziti instance tridy Zasobnik
     */
    public boolean vyres() throws ZasobnikJePrazdnyException  {
        System.out.println("\nRESENI:");
        
        // vezmeme prvni cislo, ktere budeme zkouset vlozit do ctverce (hruba sila == vsechny mozne kombinace)
        int cislo = volnaCisla.iterator().next().intValue();
        volnaCisla.remove(new Integer(cislo));
        // inicializace zasobniku a zaroven se vypocitaji vychozi castecne soucty
        boolean posledni = true; // posledni s danym cislem v zasobniku bude prvni vlozena polozka
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                // vypocet castecnych souctu
                ctverec[i][n] += ctverec[i][j];
                ctverec[n][j] += ctverec[i][j];
                // zjisteni, zda uz vychozi konfigurace je neresitelna
                if (ctverec[i][n] > soucet || ctverec[n][j] > soucet)
                    return false;
                // vlozeni zasobnikove polozky odpovidajici zkoumane pozici
                if (ctverec[i][j] == 0) {
                    zasobnik.push(new Polozka(cislo, i, j, posledni));
                    posledni = false;
                }
            }
        
        // DEBUG
        /* System.out.println(" Inicializace zasobniku:");
        System.out.println("  cislo = " + cislo + "\n  volnaCisla = " + volnaCisla);
        vypisMagickyCtverec();
        System.out.println("  vychozi obsah zasobniku: ");
        vypisZasobnik();
        System.out.println(" -----------------------\n"); */
        
        // resime tak dlouho, dokud se nenalezneme reseni nebo se vyprazdni zasobnik == neni reseni
        while (!zasobnik.isEmpty()) {
            // vybereme polozku ze zasobniku
            Polozka p = zasobnik.pop();
            
            //DEBUG
            //System.out.println(" vybrano ze zasobniku: " +  p);
            
            // pokud je to navratova polozka, vratime ctverec do stavu v kterem byl pred jejim zpracovanim
            if (p.isNavratova()) {
                
                // DEBUG
                //System.out.println(" Navratova polozka - ctverec pred:");
                //vypisMagickyCtverec();
                
                // uvolnime bunku ve ctverci a opravime castecne soucty
                ctverec[p.getRadek()][p.getSloupec()] = 0;
                ctverec[p.getRadek()][n] -= p.getHodnota();
                ctverec[n][p.getSloupec()] -= p.getHodnota();

                // DEBUG
                //System.out.println(" Navratova polozka - ctverec po:");
                //vypisMagickyCtverec();
                
                // navic pokud je posledni, tak vratime hodnotu zpet mezi volna cisla
                if (p.isPosledni()) {
                    volnaCisla.add(new Integer(p.getHodnota()));
                    // DEBUG
                    //System.out.println(" posledni polozka - vraceno: " + volnaCisla);
                }
                // DEBUG
                //System.out.println();
            }
            
            // pokud je normalni, zpracujeme (zanorime se)
            else {
                // zkusime, jestli ma vubec smysl takovou polozku uvazovat (nepocitame soucet diagonal!)
                if (ctverec[p.getRadek()][n] + p.getHodnota() <= soucet && ctverec[n][p.getSloupec()] + p.getHodnota() <= soucet) {
                    // DEBUG
                    //System.out.println(" Bezna polozka:");
                    
                    // vlozime navratovou polozku, abychom mohli vratit ctverec do stavu pred nasledujici zmenou
                    zasobnik.push(new Polozka(p));
                    
                    // vlozime hodnotu do ctverce a upravime castecne soucty
                    ctverec[p.getRadek()][p.getSloupec()] = p.getHodnota();
                    ctverec[p.getRadek()][n] += p.getHodnota();
                    ctverec[n][p.getSloupec()] += p.getHodnota();
                    
                    // DEBUG
                    //vypisMagickyCtverec();
                    
                    // pokud jsme vycerpali vsechna cisla, muze to byt reseni
                    if (volnaCisla.isEmpty()) {
                        // pokud mam reseni, tak koncim
                        if (jeCtverecMagicky())
                            return true;
                    }

                    // jinak nagenerujeme polozky s dalsim cislem (jdem hloubeji) - polozky a staci jen pro volne pozice (== 0)
                    else {
                        cislo = volnaCisla.iterator().next().intValue();
                        volnaCisla.remove(new Integer(cislo));
                        posledni = true;
                        for (int i = 0; i < n; i++)
                            for (int j = 0; j < n; j++)
                                if (ctverec[i][j] == 0) {
                                    zasobnik.push(new Polozka(cislo, i, j, posledni));
                                    posledni = false;
                                }
                    }
                    // DEBUG
                    //vypisZasobnik();
                    //System.out.println();
                }
                else {
                    if (p.isPosledni()) {
                        volnaCisla.add(new Integer(p.getHodnota()));
                        // DEBUG
                        //System.out.println(" posledni polozka - vraceno: " + volnaCisla);
                    }
                    // DEBUG
                    //System.out.println(" Polozka je k nicemu.\n");
                }
                // DEBUG
                //System.out.println(" zasobnik.isEmpty() == " + zasobnik.isEmpty() + "\n");
            }
        }
        return false;
    }
    
    /**
     * Zjisti zda je ctverec doopravdy magicky, tj. pokud jsou soucty na 
     * na obou diagonalach i ve vsech radcich a sloucich stejne a rovny
     * n * (1 + n^2) / 2
     *
     * @return true pokud je ctverec magicky, jinak false
     */
    private boolean jeCtverecMagicky() {
        boolean jeMagicky = false;
        
        // soucty diagonal
        int hd = 0, vd = 0;
        for (int i = 0; i < n; i++) {
            hd += ctverec[i][i];
            vd += ctverec[i][n - i - 1];
        }
        
        // radkove a sloupcove soucty pocitam, jen kdyz sedi diagonaly
        if (hd == soucet && vd == soucet) {
            jeMagicky = true;
            for (int i = 0; i < n; i++) {
                if (ctverec[i][n] != soucet || ctverec[n][i] != soucet) {
                    jeMagicky = false;
                    break;
                }
            }
        }
        
        return jeMagicky;
    }
    
    /**
     * vypis magickeho ctverce vc. souctu
     */
    public void vypisMagickyCtverec() {
        for (int i = 0; i < ctverec.length; i++) {
            System.out.print(" ");
            for (int j = 0; j < ctverec[i].length; j++)
                System.out.print("" + df.format(ctverec[i][j]) + " ");
            System.out.println("");
        }
    }
    
    /**
     * vypis magickeho ctverce
     * @param iSoucty pokud je true, vypise i soucty
     */
    private void vypisMagickyCtverec(boolean iSoucty) {
        for (int i = 0; i < (iSoucty ? ctverec.length : ctverec.length -1); i++) {
            System.out.print(" ");
            for (int j = 0; j < (iSoucty ? ctverec[i].length : ctverec[i].length -1); j++)
                System.out.print("" + df.format(ctverec[i][j]) + " ");
            System.out.println("");
        }
    }

    @Override
    public String toString() {
        return zasobnik.toString();
    }


    
    /**
     * vypis zasobniku
     */
    private void vypisZasobnik() {
        System.out.println("  obsah zasobniku (vrchol nahore, hodnota, radek, sloupec, navratova, posledni)");
        System.out.println("" + zasobnik);
    }
    
    /**
     * @param args argumenty prikazove radky
     */
    public static void main(String[] args) throws Exception {
        
            // inicializace mag. ctverce
            MagickyCverec mc = new MagickyCverec(3,true);

            // vygenerovana vychozi konfigurace
            System.out.println("\nVYCHOZI KONFIGURACE: ");
            mc.vypisMagickyCtverec(false);

            // reseni
            if (mc.vyres()) {
                System.out.println(" Ctverec MA reseni.");
                mc.vypisMagickyCtverec();
            }
            else {
                System.out.println(" Ctverec NEMA reseni.");
                mc.vypisMagickyCtverec();
            }

            Zasobnik muj=new Zasobnik();
            muj.push(new Polozka(1, 2,3, true));
            muj.push(new Polozka(2, 2,3, true));
            muj.push(new Polozka(3, 2,3, true));
            muj.push(new Polozka(4, 2,3, true));
            muj.pop();
            muj.push(new Polozka(5, 2,3, true));

            System.out.println("\nVYPIS mého zásobníku ");
            System.out.println(""+muj);
            
    }
}