//
//  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[0][0]).
	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 + "nnBrettet 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 <String, Rute> ruter;
	
	//Konstruktør
	SuperKlasse(int nr, int str) {
		this.nr = nr;
		this.str = str;
		ruter = new HashMap <String, Rute> ();
	} // 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);
	}
}