//
//  Sudoku.java
// 
//
//  Created by Audun Ask Blaker on 26.02.07.
//  Copyright 2007 Audun Ask Blaker. All rights reserved.
//

import easyIO.*;
import java.util.*;

/********************************************
*        ** Class Sudoku/ Main **           *
********************************************/
public class Sudoku {
    public static void main(String[] args) {
       
        System.out.println("**_* SuDoKu *_** \n");
        String fnavn = "";
       
        // Sjekker om vi har fÂtt med et filnavn fra terminal/bruker / pr¯ver  sette fnavn lik dette.
        try {
                fnavn = args[0];
            }
           
            // Hvis vi fÂr en outofboundsexeption vil denne bli fanget opp og erstattet med en eminent Feilmelding.
        catch (ArrayIndexOutOfBoundsException e) {
            System.out.println("FEIL: Du m taste inn et filnavn. " + "f.eks: java Sudoku sudokuoppgave3.txt");
        } // Slutt catch
       
        if (!fnavn.contains(".txt")) {
          System.out.println("Nei nei nei... du m nok bruke en .txt fil gitt.");
        } else {
          Kontroll ktrl = new Kontroll();
          ktrl.gogo(fnavn);
        }
       
    } // Slutt main
} // Slutt Sudoku

/*********************************************
*            ** Utsyn/ View **               *
**********************************************/
class Utsyn {
    Out skjerm;
   
    // Konstrukt¯r til Utsyn
    Utsyn() {
        skjerm = new Out();
    } // Slutt utsyn
   
    // Utskriftsmetode
    void skriv(String tilskjerm) {
        System.out.print(tilskjerm);
    } // Slutt skriv
   
    void skriv(int tall) {
        System.out.print(tall);
        System.out.print(" ");
    }
   
    void skriv(char abc) {
        System.out.print(abc);
        System.out.print(" ");
    }
} // Slutt class Utsyn



/*********************************************
*            ** Kontroll **                  *
**********************************************/
class Kontroll {
    Utsyn utsynet;
    In tast;
    Brett brett;
    int[][] ruter;
   
    Kontroll() {
        utsynet = new Utsyn();
        tast = new In();
    } // Slutt Kontroll()
   
    // F¯rste skritt mot  l¯se oppgaven. Innlesning og klargj¯ring. Oppretter rutenettverket og lager et brett av det.
    // for s  starte det rekursive kallet i den f¯rste ruta (rute).
    void gogo(String fnavn) {
        In innfil = new In(fnavn);
       
        int kvdr = innfil.inInt();
        int boksRad = innfil.inInt();
        int boksKol = innfil.inInt();
        innfil.skipWhite();
       
        int[][] ruter = new int[kvdr][kvdr];
       
        String sjekk = "Filnavn: " + fnavn + "\nBrettst¯rrelse: " + kvdr +
        "\nRader pr. boks: " + boksRad + "\nKolonner pr. boks: " + boksKol + "\n\nBrettet ser slik ut : \n";
        utsynet.skriv(sjekk);
       
        for(int i = 0; i < kvdr; i++) {
            for(int j = 0; j < kvdr; j++) {
               
                char rute = innfil.inChar();
                int verdi = (int) rute;
                innfil.skipWhite();
               
                if(verdi == 46) {                            // Hvis verdien er ./0
                    ruter[i][j] = 0;
                    utsynet.skriv(ruter[i][j]);
                } else if (verdi >= 49 && verdi <= 57) {    // Hvis verdien er 0-9
                    ruter[i][j] = (verdi - 48);
                    utsynet.skriv(ruter[i][j]);
                } else if (verdi >= 65 && verdi <= 91) {    // Hvis verdien er 10-36
                    ruter[i][j] = (verdi - 55);
                    utsynet.skriv(ruter[i][j]);
                }
            } utsynet.skriv("\n"); // Linjeskift // Slutt f¯rste for
        } utsynet.skriv("\n"); // Linjeskift // Slutt andre for
       
        // Etter  ha lest inn og satt riktige verdier opprettes ett brett med de innleste verdiene
        brett = new Brett(kvdr, boksRad, boksKol, ruter);
       
        // SÂ settes den rekursive metoden i gang i rute (0,0) (¯verst til venstre)
        Rute rut = brett.getRute(0,0);
        rut.pr0vAlleSifferMegOgResten(0,0);
       
    } // Slutt gogo()
} // Slutt

/********************************
*           Brett               *
* Skal holde p all informasjon *
* om det innleste brettet       *
********************************/
class Brett {
    int kvdr; // St¯rrelsen p brettet
    int boksRad; // Antall rader pr boks
    int boksKol; // Antall kolonner pr boks
    Rute[][] alleRuter; // 2d array som holder p alle rute-objektene i et Brett
    SuperKlasse[] kolonner; //array som holder p alle kolonne-objektene
    SuperKlasse[] rader; // array som holder p alle rad-objektene
    SuperKlasse[] bokser; // array som holder p alle boks-objektene
    Utsyn utsynet = new Utsyn();;
    int antallL0sninger = 0;
   
    Brett(int kvdr, int boksRad, int boksKol, int[][] ruter) {
        this.kvdr = kvdr;
        this.boksRad = boksRad;
        this.boksKol = boksKol;
        alleRuter = new Rute[kvdr][kvdr];
        kolonner = new Kolonne[kvdr];
        rader = new Rad[kvdr];
        bokser = new Boks[kvdr];
       
       
        // Jobber seg gjennom brettet og lager arrayer for kolonner, rader og bokser
        for(int i = 0; i < kvdr; i++) {
            kolonner[i] = new Kolonne(i, kvdr);
            rader[i] = new Rad(i, kvdr);
            bokser[i] = new Boks(i, kvdr);
        }
       
        int nr = 0;
       
        for(int i = 0; i < kvdr; i++) {
            for(int j = 0; j < kvdr; j++) {
               
                // Regnestykke som gj¯r at vi finner hvilken boks en rute ligger i, gitt
                // st¯rrelse p brettet, antall rader og kolonner og hvilket nummer ruten er i
                // rekkef¯lgen p brettet
                int a = ((nr/(boksRad * kvdr)) * boksRad);
                int c = (nr / kvdr);
                int d = (nr - (c * kvdr));
                int boks = (d / boksKol) + a;
               
                alleRuter[i][j] = new Rute(ruter[i][j], i, j, boks, nr, kvdr);
               
                kolonner[j].leggTilRute(alleRuter[i][j]);
                rader[i].leggTilRute(alleRuter[i][j]);
                bokser[boks].leggTilRute(alleRuter[i][j]);
               
                nr++;
            } // Slutt f¯rste for
        } // Slutt andre for
       
        alleRuter[0][0].settBrett(this);
       
    } // Slutt konstrukt¯r
   
    Rute getRute(int rad, int kol) {
        return alleRuter[rad][kol];
    }
   
    void skrivBrett() {
        antallL0sninger++;
       
        utsynet.skriv("L¯sning nr: " + antallL0sninger + "\n");
       
        for(int i = 0; i < kvdr; i++) {
            for(int j = 0; j < kvdr; j++) {
                int tall = alleRuter[i][j].getVerdi();
               
                if(tall < 10) {
                    utsynet.skriv(tall);
                } else {
                    tall = tall + 55;
                    char abc = (char) tall;
                    utsynet.skriv(abc);
                }
            } utsynet.skriv("\n");
        } utsynet.skriv("\n");
    }
}



/********************************
*           RUTE                *
* Skal holde p all informasjon *
* for hver enkelt rute          *
********************************/
class Rute {
   
    int verdi;
    int rad;
    int kol;
    int nummer;
    int boks;
    int kvdr;
   
    static Brett brett;
   
    // Konstrukt¯r
    Rute(int verdi, int rad, int kol, int boks, int nummer, int kvdr) {
       
        this.verdi = verdi;
        this.rad = rad;
        this.kol = kol;
        this.nummer = nummer;
        this.boks = boks;
        this.kvdr = kvdr;
    } // Slutt konstrukt¯r
   
    int getVerdi() {
        return verdi;
    }
   
    int getNummer() {
        return nummer;
    }
   
    void setVerdi(int n) {
        verdi = n;
    }
   
    // Mottar en peker til et brett-objekt, og setter pekeren brett til  peke p det. angir rutens tilh¯righet
    void settBrett(Brett b) {
        brett = b;
    }
   
    void pr0vAlleSifferMegOgResten(int x, int y) {
        boolean ferdig = false;
        // GÂr ett skritt til h¯yre
        y++;
       
        // Hvis vi har kommet til h¯yresiden av brettet
        if(y == kvdr) {
            y = 0; // S skal vi begynne p venstresiden igjen
            x++; // men n skal vi ned en kolonne
           
            // Hvis vi er kommet til bunn av brettet
            if (x == kvdr) {
                // Så er vi endelig ferdig :)
                ferdig = true;
            }
        }
       
        if(verdi == 0) { // I dette tilfellet har vi en tom rute, som da trenger en ny verdi.
            for(int i = 1; i <= kvdr; i++) { // Vi pr¯ver da med verdier f.o.m 1 - t.o.m st¯rrelsen p brettet
               
                if (!brett.bokser[boks].finnesFraF0r(i) && // Hvis verdien ikke finnes fra f¯r i den aktuelle boksen
                    !brett.kolonner[kol].finnesFraF0r(i) && // - .. - kolonna
                    !brett.rader[rad].finnesFraF0r(i)) { // -- .. -- raden
                   
                    setVerdi(i); // SÂ skal rutas verdi settes til den verdien vi snakker om (i for l¯kka)
                   
                    if(ferdig) {
                        brett.skrivBrett();
                        ferdig = false;
                    } else {
                        brett.getRute(x, y).pr0vAlleSifferMegOgResten(x, y);
                    }
                }
            }
           
            setVerdi(0); // For at den rekursive metoden skal virke, m vi sette verdien p ruta til null igjen
                         // fordi at hvis "en vei" ikke gÂr greit, s m vi kunne endre verdien p ruta. Og det kan
                         // vi bare hvis verdien er null. (if(verdi == 0)).
           
        } else {
           
            if(ferdig) {   
                brett.skrivBrett();
                ferdig = false;
            } else {
                brett.getRute(x, y).pr0vAlleSifferMegOgResten(x, y);
            }
        }
    }
}



/*****************************
*      SUPERKLASSEN          *
* Inneholder alle variabler  *
* de tre subklassene         *
* Rad, Kolonne og Boks deler *
*****************************/

class SuperKlasse {
    int nr;
    int str;
    HashMap ruter;
   
    //Konstruktør
    SuperKlasse(int nr, int str) {
        this.nr = nr;
        this.str = str;
        ruter = new HashMap ();
    } // Slutt konstruktør
   
    void leggTilRute(Rute r) {
        String nummer = r.getNummer() + "";
        ruter.put(nummer, r);
    }
   
    boolean finnesFraF0r(int verdi) {
        boolean finnes = false;
       
        for(Rute r: ruter.values()) {
            if(r.getVerdi() == verdi) {
                finnes = true;
            }
        }
        return finnes;
    }
} // end class Brett

//Klassen boks er bare en kopi av klassen SuperKlasse
class Boks extends SuperKlasse {
   
    Boks(int nr, int kvdr) {
        super(nr, kvdr);
    }
} // End class Boks

//Klassen Rad er bare en kopi av klassen Superklasse
class Rad extends SuperKlasse {
   
    Rad(int nr, int kvdr) {
        super(nr, kvdr);
    }
} // End class Rad

//Klassen Rad er bare en kopi av klassen SuperKlasse
class Kolonne extends SuperKlasse {
   
    Kolonne(int nr, int kvdr) {
        super(nr, kvdr);
    }
}