class Oblig3 {
    public static void main(String[] args) {
        javax.swing.SwingUtilities.invokeLater(new Runnable() {
            public void run() {
                HovedGUI g = new HovedGUI();
            }
        });
    }
}

abstract class GUI extends JFrame {
    JPanel[] bokser;
    JTextField[] ruter;
    JPanel sudokuBrett = new JPanel();
    
    static Brett sudoku;
    static char[] guiData;
    static int[][] brettData;

    final JFileChooser fc = new JFileChooser();

    static int str, boksX, boksY;
    boolean nyttBrett = false;

    /** Tegner brettet med riktig antall bokser og ruter */
    public void tegnBrett(int str, int boksX, int boksY) {
        this.str = str; this.boksX = boksX; this.boksY = boksY;
        
        // sjekk om vi har noen andre data som må fjernes.
        if (nyttBrett == true) {
            // fjerner tidligere brett.
            sudokuBrett.removeAll();
            sudokuBrett.invalidate();
        }

        bokser = new JPanel[(str/boksX) * (str/boksY)];
        ruter = new JTextField[str * str];

        int ctr = 0;

        for (int i = 0; i < bokser.length; i++) {
            bokser[i] = new JPanel();
            bokser[i].setLayout(new GridLayout(boksX, boksY));
            bokser[i].setBorder(BorderFactory.createEmptyBorder(2,2,2,2));
            sudokuBrett.add(bokser[i]);

            for (int j = ctr; j < ruter.length; j++) {
                ruter[j] = new JTextField("", 1);
                ruter[j].setBorder(BorderFactory.createLineBorder(Color.BLACK, 1));
                ruter[j].setHorizontalAlignment(JTextField.CENTER);
                ruter[j].setFont(new Font("sans serif", Font.BOLD, 20));

                bokser[i].add(ruter[j]);
                ctr++;

                if (ctr % (boksX * boksY) == 0) {
                    break;
                }
            }
        }
        
        // Setter layout til 
        sudokuBrett.setLayout(new GridLayout(str/boksX, str/boksY));

        // Får tegnet brett på nytt.
        sudokuBrett.validate();
    }

    public void fyllData(char[] data) {
        for (int i = 0; i < ruter.length; i++) {
            // litt matte for å finne ut hvor er plassert.
            int ruteX = i % boksY;
            int ruteY = (int) i / str;
            int boksNr = ((int)((i % str) / boksY)) + (ruteY - (ruteY % boksX));
            int j = ((boksNr % boksX) * str) + ruteX + ((ruteY % boksX) * boksY);
            j += ((int) ruteY / boksX) * (str * boksX);

            // plasserer tallene i gui
            if (data[i] != '.')
                ruter[j].setText("" + data[i]);
        }
    }
    
    public void nyttBrett() {
        // Viser dialog for å spørre om størrelsen på brettet.
        // Forholder meg til standard-størrelsene fra oppgavemappa.
        Object[] valg = {"6x6", "9x9", "12x12", "16x16"};
        
        String svar = (String) JOptionPane.showInputDialog(this, "Velg st\u00F8rrelse p\u00E5 brettet:", "Velg st\u00F8rrelse",
            JOptionPane.PLAIN_MESSAGE, null, valg, "9x9");

        // Sjekker at vi har et svar og lager nytt brett i forhold til størrelse valgt.
        if ((svar != null) && (svar.length() > 0)) {
            nyttBrett = true;

            if (svar.equals("6x6")) tegnBrett(6,2,3);
            else if (svar.equals("9x9")) tegnBrett(9,3,3);
            else if (svar.equals("12x12")) tegnBrett(12,3,4);
            else if (svar.equals("16x16")) tegnBrett(16,4,4);
        }

        // Setter tittel i hovedvindu.
        setTitle("Sudokusolver");
    }
}

/** Hovedbrukergrensesnittet */
class HovedGUI extends GUI {
    /** Tar seg av å starte opp GUI */
    HovedGUI() {
        // Forsøker å sette brukergrensesnittet lik plattformens eget utseende.
        try {
            UIManager.setLookAndFeel(UIManager.getSystemLookAndFeelClassName());
        } catch (Exception e) {}

        setTitle("Sudokusolver");
        setSize(500,500);
        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);

        tegnMeny();
        // spør om et nytt brett til å begynne med.
        nyttBrett();
        
        guiData = new char[str * str];

        setVisible(true);
    }

    /** Tar seg av tegning av meny */
    private void tegnMeny() {
        JMenuBar menuBar = new JMenuBar();
        MenyLytter m = new MenyLytter();

        // Filmeny
        JMenu fileMenu = new JMenu("Fil");
        fileMenu.setMnemonic(KeyEvent.VK_F);
        menuBar.add(fileMenu);
            JMenuItem filNy = new JMenuItem("Nytt brett", KeyEvent.VK_N);
            filNy.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_N, ActionEvent.CTRL_MASK));
            filNy.addActionListener(m);
            filNy.setActionCommand("new");
            fileMenu.add(filNy);

            JMenuItem filApne = new JMenuItem("\u00C5pne brett", KeyEvent.VK_O);
            filApne.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_O, ActionEvent.CTRL_MASK));
            filApne.addActionListener(m);
            filApne.setActionCommand("open");
            fileMenu.add(filApne);

            fileMenu.addSeparator();

            JMenuItem filAvslutt = new JMenuItem("Avslutt", KeyEvent.VK_A);
            filAvslutt.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_Q, ActionEvent.CTRL_MASK));
            filAvslutt.addActionListener(m);
            filAvslutt.setActionCommand("exit");
            fileMenu.add(filAvslutt);


        // Verktøy-meny
        JMenu toolMenu = new JMenu("Verkt\u00F8y");
        fileMenu.setMnemonic(KeyEvent.VK_V);
        menuBar.add(toolMenu);
            JMenuItem toolFinnLosning = new JMenuItem("Finn l\u00F8sninger");
            toolFinnLosning.setAccelerator(KeyStroke.getKeyStroke(KeyEvent.VK_F, ActionEvent.CTRL_MASK));
            toolFinnLosning.addActionListener(m);
            toolFinnLosning.setActionCommand("solve");
            toolMenu.add(toolFinnLosning);

        // Hjelp-meny
        JMenu helpMenu = new JMenu("Hjelp");
        helpMenu.setMnemonic(KeyEvent.VK_H);
        menuBar.add(helpMenu);
            JMenuItem helpAbout = new JMenuItem("Om...");
            helpAbout.addActionListener(m);
            helpAbout.setActionCommand("about");
            helpMenu.add(helpAbout);

        setJMenuBar(menuBar);
    }

    /** Underklasse for å ta seg av brukerens valg fra menyen. */
    class MenyLytter implements ActionListener {
        public void actionPerformed(ActionEvent e) {
            if ("exit".equals(e.getActionCommand())) { 
                // avslutter programmet.
                System.exit(0);
            } else if ("new".equals(e.getActionCommand())) { 
                // fjerner data og lager nytt brett.
                nyttBrett();
            } else if ("open".equals(e.getActionCommand())) { 
                // åpner fildialogen og henter brukerens returverdi.
                int retVal = fc.showOpenDialog(null);

                // Henter filen dersom brukeren har trykket Åpne.
                if (retVal == JFileChooser.APPROVE_OPTION) {
                    File fil = fc.getSelectedFile();

                    // tolk innholdet og skriv verdiene i GUI.
                    tolkFil(fil);
                }
            } else if ("solve".equals(e.getActionCommand())) {
                // sjekker om det er noen endringer og åpner løsningsvindu
                startLosning();
            } else if ("about".equals(e.getActionCommand())) { 
                // åpner about-dialog.
                String helpMsg = "Dette programmet er laget av Michael Kjelbergvik Thung,\n" +
                    "ved hjelp av flittig bruk av Java API og Sun Java Tutorials, samt\n" +
                    "Rett p\u00E5 Java av Arne Maus\n";
                // vis dialog.
                JOptionPane.showMessageDialog(null, helpMsg);
            }
        }
    }

    private void tolkFil(File f) {
        minIO io = new minIO();
        String[] brettInfo = null;
        String filNavn = f.getName();

        // Leser filinnhold inn i array.
        brettInfo = io.lesFil(f).split(System.getProperty("line.separator"));

        // henter størrelser.
        this.str = Integer.parseInt(brettInfo[0]);
        this.boksX = Integer.parseInt(brettInfo[1]);
        this.boksY = Integer.parseInt(brettInfo[2]);
        brettData = new int[str][str];
        guiData = new char[str * str];

        // hent data fra selve brettet.
        int ctr = 0;
        for (int x = 0; x < brettInfo.length - 3; x++) {
            char[] r = brettInfo[x + 3].toCharArray();

            for (int y = 0; y < r.length; y++) {
                // sørger for at vi får riktige tall inn.
                if (r[y] == '.') brettData[x][y] = 0;
                else if ((int) r[y] - '0' < 10) brettData[x][y] = (int) r[y] - '0';
                else if (r[y] == '@') brettData[x][y] = 36;
                else brettData[x][y] = (int) r[y] - 55;

                // leser det samme inn i array for GUI.
                guiData[ctr] = r[y];
                ctr++;
            }
        }

        // tegn nytt brett og endre tittel på hovedvindu.
        nyttBrett = true;
        tegnBrett(this.str, this.boksX, this.boksY);
        setTitle("Sudokusolver - " + filNavn);
        
        // Fyller data inn i sudokubrettet.
        fyllData(guiData);

        // Initialiserer brett-objekt
        sudoku = new Brett(brettData, str, boksX, boksY);
    }

    private void startLosning() {
        // Gå gjennom dataene og sjekk om det er noen endringer.
        int rad = 0, kol = 0;
        for (int i = 0; i < ruter.length; i++) {
            // litt matte for å finne ut hvor er plassert.
            int ruteX = i % boksY;
            int ruteY = (int) i / str;
            int boksNr = ((int) ((i % str) / boksY)) + (ruteY - (ruteY % boksX));
            int j = ((boksNr % boksX) * str) + ruteX + ((ruteY % boksX) * boksY);
            j += ((int) ruteY / boksX) * (str * boksX);

            // Legger til i GUI-data.
            String ruteInnhold = ruter[j].getText();
            if (ruteInnhold.length() != 0) guiData[i] = ruteInnhold.charAt(0);
            else guiData[i] = '.';
            
            // Legger til i brett-data.
            if (guiData[i] == '.') brettData[rad][kol] = 0;
            else if ((int) guiData[i] - '0' < 10) brettData[rad][kol] = (int) guiData[i] - '0';
            else if (guiData[i] == '@') brettData[rad][kol] = 36;
            else brettData[rad][kol] = (int) guiData[i] - 55;
            
            // Sørger for å gå gjennom brettdata-arrayet riktig.
            kol++;
            if (kol == str) {
                kol = 0;
                rad++;
            }
        }

        sudoku = new Brett(brettData, str, boksX, boksY);
        
        // Starter løsningsvinduet og løsningstråden.
        LosningsGUI l = new LosningsGUI(str, boksX, boksY);
        System.out.println("Starter tråd");
        sudoku.startThread(l);
    }

    public void tegnBrett(int s, int x, int y) {
        super.tegnBrett(s, x, y);
        
        add(sudokuBrett, BorderLayout.CENTER);
    }
}

/** Tar seg av løsningenes GUI */
class LosningsGUI extends GUI implements Runnable {
    GridBagConstraints c = new GridBagConstraints();
    LosningLytter l = new LosningLytter();
    JLabel statusBar;
    JButton nesteLos;
    int antLeste = 0, antLoste = 0;

    LosningsGUI(int str, int boksX, int boksY) {
        setTitle("Sudokusolver - L\u00F8sningsvindu");
        setSize(500,510);
        setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
        
        // Bruker GridBagLayout for å få fin størrelse på knapper og brett.
        setLayout(new GridBagLayout());

        // Bestemmer størrelser for knapperaden.
        c.anchor = GridBagConstraints.FIRST_LINE_START;
        c.weighty = 0.01;

        // Label
        c.ipady = 12;
        c.fill = GridBagConstraints.HORIZONTAL;
        c.gridwidth = 5;
        JLabel hlpTekst = new JLabel("Trykk i ruta du \u00F8nsker \u00E5 se, eller en av knappene under:");
        hlpTekst.setVerticalTextPosition(JLabel.BOTTOM);
        add(hlpTekst, c);

        // Setter knapper.
        c.gridy = 2;
        c.gridx = 2;
        c.ipady = 0;
        c.gridwidth = 1;
        c.fill = GridBagConstraints.NONE;
        JButton rndSvar = new JButton("Vis ett og ett tall");
        rndSvar.addActionListener(l);
        rndSvar.setActionCommand("nextnum");
        add(rndSvar, c);

        c.gridx = 3;
        JButton heleLos = new JButton("Vis hele l\u00F8sningen");
        heleLos.addActionListener(l);
        heleLos.setActionCommand("show");
        add(heleLos, c);
        
        c.gridx = 4;
        nesteLos = new JButton("Vis neste l\u00F8sning");
        nesteLos.setEnabled(false);
    	nesteLos.addActionListener(l);
        nesteLos.setActionCommand("next");
        add(nesteLos, c);

        // Tegner sudoku-brettet.
        tegnBrett(str, boksX, boksY);

        // Tegner status-linje
        c.gridx = 0;
        c.gridy = 4;
        c.weightx = 0.0;
        c.weighty = 0.0;
        c.anchor = GridBagConstraints.FIRST_LINE_START;
        c.fill = GridBagConstraints.HORIZONTAL;
        statusBar = new JLabel("St\u00F8rrelse: " + str + "x" + str + " - Antall l\u00F8sninger hittil: " + antLoste);
        statusBar.setBorder(BorderFactory.createLoweredBevelBorder());
        add(statusBar, c);

        setVisible(true);
    }

    public void tegnBrett(int str, int boksX, int boksY) {
        super.tegnBrett(str, boksX, boksY);

        if (guiData != null) fyllData(guiData);
        
        // Bestemmer plassering og størrelse på brettet.
        c.fill = GridBagConstraints.BOTH;
        c.anchor = GridBagConstraints.CENTER;
        c.gridwidth = 5;
        c.gridx = 0;
        c.gridy = 3;
        c.weightx = 1.0;
        c.weighty = 1.0;

        add(sudokuBrett, c);
    }

    class LosningLytter implements ActionListener {
        public void actionPerformed(ActionEvent e) {
        	if ("next".equals(e.getActionCommand())) {
        		System.out.println("Finn neste!");
        		hentNeste();
        	}
        }
    }
    
    public void dispose() {
    	sudoku.fjernLosninger();
    }
    
    synchronized void hentNeste() {
    	System.out.println("Henter neste");
    	antLeste++;
    	if (antLeste > antLoste) siFra();
    	System.out.println("Sier fra til brett");
    	sudoku.sudokuVarsle();
    	
    	try {
    		wait();
    	} catch(InterruptedException e) {}
        System.out.println("hentNeste vekket");
    }
    
    synchronized void guiVarsle() {
        System.out.println("Sagt fra til GUI");
    	antLoste++;
    	statusBar.setText("St\u00F8rrelse: " + str + "x" + str + " - Antall l\u00F8sninger hittil: " + antLoste);
    	nesteLos.setEnabled(true);
    	notify();
    }
    
    public void run() {
    	sudoku.sudokuVarsle();
    }
    
    private void siFra() {
    	// meldingsboks om at dette var siste løsning her.
    }
}

/**
 * Tar for seg hvert hele brett
 */
class Brett extends Thread {
    private final int str;
    private final int boksX;
    private final int boksY;
    private Rute[][] ruter;
    private Rad[] rader;
    private Kolonne[] kolonner;
    private Boks[][] bokser;
    private ArrayList <String> losninger = new ArrayList<String>();
    private static int antLoste = 0;
    LosningsGUI losnGUI = null;

    /** Initialiserer brettet */    
    Brett(int[][] data, int str, int boksX, int boksY) {
        this.str = str;
        this.boksX = boksX;
        this.boksY = boksY;
        rader = new Rad[str];
        kolonner = new Kolonne[str];
        bokser = new Boks[str/boksX][str/boksY];
        ruter = new Rute[str][str];

        // Loop for å opprette rader og kolonner.
        for (int x = 0; x < str; x++) {
            rader[x] = new Rad();
            kolonner[x] = new Kolonne();
        }

        // Oppretter bokser.
        for (int x = 0; x < str/boksX; x++) 
            for (int y = 0; y < str/boksY; y++) bokser[x][y] = new Boks();

        // Loop for å opprette ruter
        for (int x = 0; x < str; x++) {
            for (int y = 0; y < str; y++) {
                int v;
                if (data[x][y] == 0) v = 0;
                else v = data[x][y];
                    
                // Fyller brettet med ruter
                ruter[x][y] = new Rute(v, kolonner[x], rader[y], bokser[x / boksX][y / boksY], this);
            }
        }

        // Fyll inn ruter ved siden av seg selv korrekt.
        for (int y = 0; y < str; y++) {
            for (int x = 0; x < str - 1; x++) ruter[x][y].settNeste(ruter[x + 1][y]);

            // Sørg for at vi går til neste rad på slutten.
            if (y < str - 1) ruter[str - 1][y].settNeste(ruter[0][y + 1]);
            // Pass på at siste rute på brettet får nullpeker ved siden av seg.
            else ruter[str - 1][y].settNeste(null);
        }
    }
    
    /** Selve algoritmen for å finne løsninger */
    public void finnLosninger() {
        ruter[0][0].provAlleSifferMegOgResten(str);
    }

    /** Legger til en løsning til løsningslista. */
    synchronized void leggTilLosning() {
        String l = "";

        char[] tegn = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ@".toCharArray();

        // Stapper løsningsforslag (med hensyn til tall og bokstaver) inn i en string.
        for (int x = 0; x < str; x++) {
            for (int y = 0; y < str; y++) {
                if (ruter[x][y].hentVerdi() == 0)
                    l += ".";
                else
                    l += String.valueOf(tegn[ruter[x][y].hentVerdi()-1]);
            }

            l += "// ";
        }
        
        // Legger til løsning.
        losninger.add(l);
        
        // Si fra til løsningsGUI.
        System.out.println("Sier fra til GUI");
        losnGUI.guiVarsle();
        
        // Vent til notify.
        System.out.println("Venter på GUI.");
        try {
        	wait();
        } catch (InterruptedException e) {}
        System.out.println("Går videre.");
    }

    /** Returnerer løsninger */
    public ArrayList <String> hentLosninger() {
        return losninger;
    }
    
    /** Fjerner alle løsninger */
    public void fjernLosninger() {
    	losninger.clear();
    }
   
    /** Trådstarter */
    public void startThread(LosningsGUI l) {
    	losnGUI = l;
    	run();
        System.out.println("Startet tråd.");
    }
    
    public void run() {
    	finnLosninger();
        System.out.println("Finner løsninger");
    }
    
    /** Varsler seg selv om å fortsette */
    public void sudokuVarsle() {
    	notify();
        System.out.println("Sagt fra til brett.");
    }
}

/**
 *  Tar seg av hver enkeltrute
 */
class Rute {
    static int antallLosninger;
    private int ruteVerdi;
    private boolean erFast;
    private Rute nesteRute;
    private Kolonne egenKol;
    private Rad egenRad;
    private Boks egenBoks;
    private Brett egetBrett;

    /** Konstruktør */
    Rute(int v, Kolonne k, Rad r, Boks b, Brett brett) {
        this.ruteVerdi = v;
        this.egenKol = k;
        this.egenRad = r;
        this.egenBoks = b;
        this.egetBrett = brett;

        if (v == 0) erFast = false;
        else erFast = true;

        k.leggTil(this);
        r.leggTil(this);
        b.leggTil(this);
    }

    /** Setter verdi til ruta */    
    public void settVerdi(int i) { ruteVerdi = i; }

    /** Henter verdi fra ruta */
    public int hentVerdi() { return ruteVerdi; }

    /** Setter rutas neste rute */
    public void settNeste(Rute r) { nesteRute = r; }

    /** Henter ruta ved siden av seg */
    public Rute hentNeste() { return nesteRute; }

    /** Sjekker om vi er på siste rute */
    public boolean harNeste() {
        if (nesteRute == null) return false;
        return true;
    }
    
    /** Algoritme for å sette siffer i rutene */
    public void provAlleSifferMegOgResten(int str) {
        // sjekk om ruten er forhåndsutfylt
        if (!erFast) {
            // sjekk om vi kan sette et tall i ruta.
            for (int t = 1; t <= str; t++) {
                if (egenBoks.sjekkTall(t) && egenRad.sjekkTall(t) && egenKol.sjekkTall(t)) {
                    // Sett tall og gå videre.
                    settVerdi(t);
                    
                    // gå til neste.
                    if (harNeste()) hentNeste().provAlleSifferMegOgResten(str);
                    // øk antall løsninger.
                    else {
                       antallLosninger++;
                       egetBrett.leggTilLosning();
                    }
                }
                 
                // finn neste mulige løsning 
                settVerdi(0);
            }
        } else {
            // gå til neste
            if (harNeste()) hentNeste().provAlleSifferMegOgResten(str);
            // øk antall løsninger.
            else {
                antallLosninger++;
                egetBrett.leggTilLosning();
            }
        }
    }

    /** toString-metode */
    public String toString() { return String.valueOf(ruteVerdi); }
    
    public int hentAntLoste() { return antallLosninger; }
}

/**
 * Super-klasse for boks, kolonne og rad.
 */
abstract class Underdel {
    ArrayList <Rute> ruter = new ArrayList<Rute>();

    /** Legger til en rute i lista */
    public void leggTil(Rute r) { ruter.add(r); }

    /** Sjekker om et tall er satt i lista */
    public boolean sjekkTall(int i) {
        boolean ikkeSatt = true;

        for (int x = 0; x < ruter.size(); x++) {
            Rute r = (Rute) ruter.get(x);

            if (r.hentVerdi() == i) ikkeSatt = false;
        }

        return ikkeSatt;
    }
}

// Tomme subklasser for de mindre delene av et sudoku-brett.
class Boks extends Underdel {}
class Kolonne extends Underdel {}
class Rad extends Underdel {}

/** Egendefinert IO-klasse */
class minIO {    
    /** Leser innhold fra fil. */
    public String lesFil(File filNavn) {
        StringBuffer innhold = new StringBuffer();

        BufferedReader input = null;

        // Forsøker å lese fra filen, og skriv ut eventuelle feilmeldinger om noe går galt.
        try {
            input = new BufferedReader(new FileReader(filNavn));
            String line = null;

            // Legg inn data.
            while ((line = input.readLine()) != null)
                innhold.append(line + System.getProperty("line.separator"));
        }
        catch (FileNotFoundException e) {}
        catch (IOException e) {} 
        finally {
            try {
                // pass på at vi får lukket filen.
                if (input != null) input.close();
            } catch (IOException e) {}
        }

        return innhold.toString();
    }
}