123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358 |
- import java.io.File;
- import java.util.Scanner;
- import java.util.ArrayList;
- import java.util.List;
-
- class Brett {
- class Rute {
- int verdi;
- Rad rad;
- Kolonne kolonne;
- Boks boks;
- Brett brett;
-
- Rute neste = null;
-
- Rute(int verdi, Brett brett) {
- this.verdi = verdi;
- this.brett = brett;
- }
-
- public boolean harVerdi() {
- return verdi != -1;
- }
-
- public int[] finnAlleMuligeTall() {
- ArrayList<Integer> ugyldige = new ArrayList<>();
-
- for (Rute r: rad.ruter) {
- if (r.harVerdi()) {
- ugyldige.add(r.verdi);
- }
- }
- for (Rute r: kolonne.ruter) {
- if (r.harVerdi()) {
- ugyldige.add(r.verdi);
- }
- }
- for (Rute r: boks.ruter) {
- if (r.harVerdi()) {
- ugyldige.add(r.verdi);
- }
- }
-
- ArrayList<Integer> gyldige = new ArrayList<>();
- for (int i = 1; i <= brett.storrelse; ++i) {
- if (!ugyldige.contains(i)) {
- gyldige.add(i);
- }
- }
-
- int[] res = new int[gyldige.size()];
- for (int i = 0; i < res.length; ++i) {
- res[i] = gyldige.get(i);
- }
- return (int[])res;
- }
-
- /*
- * fyllUtDenneRuteOgResten
- * Jeg ga den et annet navn, som jeg mener er bedre. Maalet er ikke
- * aa fylle ut ruten, men aa finne losninger.
- */
- public List<List<Integer>> finnLosning() {
-
- // Bare skip denne ruten hvis vi har en verdi; ingenting aa lose
- if (harVerdi()) {
- List<List<Integer>> losninger;
- if (neste != null) {
- losninger = neste.finnLosning();
- } else {
- losninger = new ArrayList<>();
- losninger.add(new ArrayList<>());
- }
- for (List<Integer> losning: losninger) {
- losning.add(verdi);
- }
- return losninger;
- }
-
- List<List<Integer>> losninger = new ArrayList<>();
- int[] mulige = finnAlleMuligeTall();
- for (int mulig: mulige) {
- verdi = mulig;
-
- List<List<Integer>> nestesLosninger;
- if (neste == null) {
- nestesLosninger = new ArrayList<>();
- List<Integer> l = new ArrayList<Integer>();
- nestesLosninger.add(l);
- } else {
- nestesLosninger = neste.finnLosning();
- }
-
- for (List<Integer> l: nestesLosninger) {
- l.add(verdi);
- losninger.add(l);
- }
- }
- verdi = -1;
-
- return losninger;
- }
- }
-
- class Kolonne {
- private int index = 0;
- Rute[] ruter;
-
- Kolonne(int storrelse) {
- ruter = new Rute[storrelse];
- }
-
- public void settInn(Rute r) {
- ruter[index++] = r;
- }
- }
-
- class Rad {
- private int index = 0;
- Rute[] ruter;
-
- Rad(int storrelse) {
- ruter = new Rute[storrelse];
- }
-
- public void settInn(Rute r) {
- ruter[index++] = r;
- }
- }
-
- class Boks {
- private int index = 0;
- Rute[] ruter;
- int bredde;
- int hoyde;
-
- Boks(int bredde, int hoyde) {
- this.bredde = bredde;
- this.hoyde = hoyde;
- ruter = new Rute[bredde * hoyde];
- }
-
- public void settInn(Rute r) {
- ruter[index++] = r;
- }
- }
-
- File fil;
- int raderPerBoks;
- int kolonnerPerBoks;
- int antallBokserX;
- int antallBokserY;
- int storrelse;
-
- Rute[] ruter;
- Rad[] rader;
- Kolonne[] kolonner;
- Boks[] bokser;
-
- Brett(File fil) throws Exception {
- this.fil = fil;
- read();
- }
-
- public SudokuBeholder los() {
- List<List<Integer>> losninger = ruter[0].finnLosning();
- SudokuBeholder sb = new SudokuBeholder(this);
-
- for (List<Integer> losning: losninger) {
- SudokuBeholder.Losning l = new SudokuBeholder.Losning();
- for (int i = losning.size() - 1; i >= 0; --i) {
- Rute r = ruter[losning.size() - 1 - i];
- l.leggTil(losning.get(i), r.harVerdi());
- }
- sb.leggTil(l);
- }
-
- return sb;
- }
-
- public SudokuBeholder.Losning tilLosning() {
- SudokuBeholder.Losning losning = new SudokuBeholder.Losning();
- for (Rute r: ruter) {
- losning.leggTil(r.verdi, r.harVerdi());
- }
- return losning;
- }
-
-
- public void print() throws Exception {
- int x = 0;
- int y = 1;
- int modX = storrelse / antallBokserX;
- int modY = storrelse / antallBokserY;
-
- for (Rute r: ruter) {
- if (x % modX == 0 && x != 0) {
- System.out.print("|");
- }
-
- if (r.harVerdi()) {
- System.out.print(toChar(r.verdi));
- } else {
- System.out.print(" ");
- }
-
- x += 1;
- if (x >= storrelse) {
- x = 0;
-
- if (y % modY == 0 && y < storrelse) {
- System.out.println("");
- for (int i = 0; i < storrelse; ++i) {
- if (i % modX == 0 && i != 0) {
- System.out.print("+");
- }
- System.out.print("-");
- }
- }
- System.out.println("");
- y += 1;
- }
- }
- }
-
- public int toInt(char c) throws Exception {
- if (c == '.') {
- return -1;
- } else if (c >= '1' && c <= '9') {
- return (int)c - 49 + 1;
- } else if (c >= 'A' && c <= 'Z') {
- return (int)c - 65 + 10;
- } else if (c == '@') {
- return 36;
- } else if (c == '#') {
- return 37;
- } else if (c == '&') {
- return 38;
- } else if (c >= 'a' && c <= 'z') {
- return c - 97 + 39;
- } else {
- throw new IllegalArgumentException();
- }
- }
-
- public char toChar(int c) throws Exception {
- if (c == -1) {
- return '.';
- } else if (c >= 1 && c <= 9) {
- return (char)(c + 49 -1);
- } else if (c >= 10 && c <= 35) {
- return (char)(c + 65 - 10);
- } else if (c == 36) {
- return '@';
- } else if (c == 37) {
- return '#';
- } else if (c == 38) {
- return '&';
- } else if (c >= 39 && c <= 64) {
- return (char)(c + 97 - 39);
- } else {
- throw new IllegalArgumentException();
- }
- }
-
- private void read() throws Exception {
- Scanner s = new Scanner(fil);
-
- try {
- raderPerBoks = Integer.parseInt(s.nextLine());
- kolonnerPerBoks = Integer.parseInt(s.nextLine());
- } catch (Exception ex) {
- throw new Exception("Filen starter ikke med dimensjoner!");
- }
-
- try {
- storrelse = raderPerBoks * kolonnerPerBoks;
- antallBokserX = storrelse / kolonnerPerBoks;
- antallBokserY = storrelse / raderPerBoks;
- } catch (Exception ex) {
- throw new Exception("Filen inneholder feil!");
- }
-
- if (storrelse > 64) {
- throw new Exception("For stort brett!");
- }
-
- ruter = new Rute[storrelse * storrelse];
-
- // Les inn alle ruter
- int i = 0;
- Rute forrige = null;
- for (int y = 0; y < storrelse; ++y) {
- if (!s.hasNextLine()) {
- throw new Exception("For faa rader!");
- }
-
- char[] rad = s.nextLine().toCharArray();
- if (rad.length > storrelse) {
- throw new Exception("For mange kolonner i rad "+(y+1)+"!");
- }
-
- for (int x = 0; x < storrelse; ++x) {
- char c;
- try {
- c = rad[x];
- } catch (ArrayIndexOutOfBoundsException ex) {
- throw new Exception("For faa kolonner i rad "+(y+1)+"!");
- }
-
- Rute r = new Rute(toInt(c), this);
- if (forrige != null) {
- forrige.neste = r;
- }
- ruter[i++] = r;
- forrige = r;
- }
- }
- if (s.hasNextLine()) {
- throw new Exception("For mange rader!");
- }
-
- // Opprett rader, kolonner, og bokser
- // (obligens `void opprettDatastruktur()`, jeg mener det ikke gir mening
- // aa ha det som en egen metode, da det vil skje hvis og bare hvis vi
- // leser inn ny informasjon)
-
- rader = new Rad[storrelse];
- kolonner = new Kolonne[storrelse];
- bokser = new Boks[storrelse];
- for (i = 0; i < storrelse; ++i) {
- rader[i] = new Rad(storrelse);
- kolonner[i] = new Kolonne(storrelse);
- bokser[i] = new Boks(kolonnerPerBoks, raderPerBoks);
- }
-
- int x = 0;
- int y = 0;
- for (Rute r: ruter) {
- r.rad = rader[y];
- rader[y].settInn(r);
- r.kolonne = kolonner[x];
- kolonner[x].settInn(r);
-
- int boxx = (x / kolonnerPerBoks) % antallBokserX;
- int boxy = (y / raderPerBoks) % antallBokserY;
- int boxi = boxx + (boxy * antallBokserX);
- bokser[boxi].settInn(r);
- r.boks = bokser[boxi];
-
- x += 1;
- if (x >= storrelse) {
- x = 0;
- y += 1;
- }
- }
- }
- }
|