Unterquadrate bei Sudoku füllen

[hvboede]

Aufgabe: Ich will Unterquadrate eines Sudoku mit schon fixierten Werten so füllen, das die Zahlen 1-9
einmal darin vorkommen.


dafür habe ich die Methode

  public static void unterquadrat(int[] hilfsarray) {
        boolean schondrin = false;
        int zaehler = 0, a;
        while (zaehler < hilfsarray.length) {
            if (hilfsarray[zaehler] > 0) {
                zaehler++;
            } else {
//                Suche solange eine Zufallszahl zwischen 1 und 9, bis du eine gefunden hast die noch nicht im array vorkommt dann schreibe sie rein
                while (hilfsarray[zaehler] == 0) {
                    a = (int) (Math.random() * 8 + 1);

                    for (int q = 0; q < hilfsarray.length; q++) {
                        if (hilfsarray[q] == a) {
                            schondrin = true;
                        }
                    }


                    if (schondrin == false) {
                        hilfsarray[zaehler] = a;
                    }

                    schondrin = false;
                }
                zaehler++;
            }
        }
    }

sie funktioniert z.b. für die Instanz 0 9 0
6 0 0
0 0 0

aber für die Instanz 0 0 0
0 8 0
0 7 0

nicht, oder braucht zumindest viel länger so das ich darauß schließe, dass sie überhaupt nicht funktioniert.
Ich hoffe das jemand den Grund sieht und mir helfen kann


mfg

 

[Final_Striker]

Ich würde es so machen:

- alle Zahlen die noch fehlen in einem Array oder einer Liste sammeln
- Array oder Liste mischen
- mit den gemischten Zahlen die Quadrat füllen

 

[timbeau]

Dein Algorithmus ist nicht deterministisch. Soll heißen, das theoretisch dein PC unendlich lang Randomwerte ausspuckt die du aber schon hast.

Besser wäre ein Vorgehen, dass du in einer Liste die noch möglichen Zahlen speicherst und dir dann eine Zufallszahl generieren lässt von 0 bis Liste.size()-1. Dann kannst du die Felder durchgehen und bei jedem den Zufallsaglo laufen lassen und diese Zahl dann aus der Liste rausnehmen.

 

[hvboede]

das Problem ist glaube ich, dass er Unterquadrate in denen noch keine 9 fixiert ist nicht lösen kann, weil

a = (int) (Math.random() * 8 + 1); nur Zufallszahlen bis 8 generiert.

Kann mir da jemand weiterhelfen?


mfg

 

[Final_Striker]

Ich kann nicht verstehen warum sich Leute ständig mit Math.random abquälen, wenn es mit Random eine gescheite Klasse für solche Aufgaben gibt.

Random#nextInt(int)

 

[hvboede]

bei mir ist Frage einfach zu beantworten ich wusste davon bis jetzt nichts

 

[hüteüberhüte]

Ein Unterquadrat kann ja erst dann vollständig ausgefüllt werden, wenn für jedes Feld nur ein Kandidat zum ausfüllen übrig bleibt. Also wiederholt für jedes Feld verbleibende Kandidaten sammeln und immer, wenn nur einer übrig ist, diesen eintragen.

Würde einfach über die 9 Felder iterieren, jedes mal prüfen, ob schon ausgefüllt und ggf. die Kandidaten wie oben beschriebenen ermitteln. Funktioniert das?

 

[hüteüberhüte]

Ach so, es geht darum, die 9 Felder einfach mit zufälligen Zahlen von 1 bis 9 zu füllen, ohne Doppelte dabei/in dem Quadrat zu haben, unabhängig davon, ob sie zum "Rest" des Sudokus passen oder nicht.

Dann könnte das einfach so gehen:

package javaforum;

import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        int[] einQuadrat = {0, 0, 5, 0, 0, 6, 0, 8, 9};

        Set<Integer> vorhandene = new HashSet<Integer>();
        for (int i = 0; i < einQuadrat.length; i++) {
            vorhandene.add(einQuadrat[i]);
        }

        List<Integer> kandidaten = new LinkedList<Integer>();
        for (int i = 1; i <= 9; i++) {
            kandidaten.add(i);
        }
        Collections.shuffle(kandidaten);

        for (int i = 0; i < einQuadrat.length; i++) {
            if (einQuadrat[i] == 0) {
                while (vorhandene.contains(kandidaten.get(0))) {
                    kandidaten.remove(0);
                }
                einQuadrat[i] = kandidaten.get(0);
                vorhandene.add(kandidaten.remove(0));
            }
        }

        System.out.println(Arrays.toString(einQuadrat));
    }
}

einQuadrat ist in diesem Fall das Quadrat, welches ausgefüllt werden soll

vorhandene ist ein Set, das sich bereits ausgefüllte Zahlen merkt

kandidaten ist eine gemischte Liste mit Zahlen, die zum ausfüllen benutzt werden können

Es wird nur einmal über das Array iteriert, dabei wird nur dann der erste "Listen-Kandidat" eingetragen, wenn er (in dem Quadrat) noch nicht vorhanden war

 

[hvboede]

gefällt mir :applaus:

 

[hüteüberhüte]

Ja, mir auch^^ und wenn man es leicht umändert, geht es auch mit vergleichsweise großen Arrays:

        long t1 = System.currentTimeMillis();

        int[] einQuadrat = new int[999999];
        einQuadrat[7] = 7;
        einQuadrat[77] = 77;
        einQuadrat[100] = 100;

        Set<Integer> vorhandene = new HashSet<Integer>();
        for (int i = 0; i < einQuadrat.length; i++) {
            vorhandene.add(einQuadrat[i]);
        }

        List<Integer> kandidaten = new LinkedList<Integer>();
        for (int i = 1; i <= einQuadrat.length; i++) {
            kandidaten.add(i);
        }
        Collections.shuffle(kandidaten);

        for (int i = 0; i < einQuadrat.length; i++) {
            if (einQuadrat[i] == 0) {
                while (vorhandene.contains(kandidaten.get(0))) {
                    kandidaten.remove(0);
                }
                einQuadrat[i] = kandidaten.get(0);
                vorhandene.add(kandidaten.remove(0));
            }
        }

        long t2 = System.currentTimeMillis();

        // System.out.println(Arrays.toString(einQuadrat));
        System.out.println(t2 - t1);

Laufzeit: ~2400ms

Tauscht man LinkedList gegen ArrayList und wählt immer das letzte Element:

        long t1 = System.currentTimeMillis();

        int[] einQuadrat = new int[999999];
        einQuadrat[7] = 7;
        einQuadrat[77] = 77;
        einQuadrat[100] = 100;

        Set<Integer> vorhandene = new HashSet<Integer>();
        for (int i = 0; i < einQuadrat.length; i++) {
            vorhandene.add(einQuadrat[i]);
        }

        List<Integer> kandidaten = new ArrayList<Integer>(einQuadrat.length);
        for (int i = 1; i <= einQuadrat.length; i++) {
            kandidaten.add(i);
        }
        Collections.shuffle(kandidaten);

        for (int i = 0; i < einQuadrat.length; i++) {
            if (einQuadrat[i] == 0) {
                while (vorhandene.contains(kandidaten.get(kandidaten.size() - 1))) {
                    kandidaten.remove(kandidaten.size() - 1);
                }
                einQuadrat[i] = kandidaten.get(kandidaten.size() - 1);
                vorhandene.add(kandidaten.remove(kandidaten.size() - 1));
            }
        }

        long t2 = System.currentTimeMillis();

        // System.out.println(Arrays.toString(einQuadrat));
        System.out.println(t2 - t1);

...ist die Laufzeit: ~1600ms

Fügt man zusätzlich noch eine ArrayDeque ein:

        long t1 = System.currentTimeMillis();

        int[] einQuadrat = new int[999999];
        einQuadrat[7] = 7;
        einQuadrat[77] = 77;
        einQuadrat[100] = 100;

        Set<Integer> vorhandene = new HashSet<Integer>();
        for (int i = 0; i < einQuadrat.length; i++) {
            vorhandene.add(einQuadrat[i]);
        }

        List<Integer> kandidaten = new ArrayList<Integer>(einQuadrat.length);
        for (int i = 1; i <= einQuadrat.length; i++) {
            kandidaten.add(i);
        }
        Collections.shuffle(kandidaten);

        Deque<Integer> kandidaten2 = new ArrayDeque<Integer>(kandidaten);

        for (int i = 0; i < einQuadrat.length; i++) {
            if (einQuadrat[i] == 0) {
                while (vorhandene.contains(kandidaten2.peek())) {
                    kandidaten2.poll();
                }
                einQuadrat[i] = kandidaten2.peek();
                vorhandene.add(kandidaten2.poll());
            }
        }

        long t2 = System.currentTimeMillis();

        // System.out.println(Arrays.toString(einQuadrat));
        System.out.println(t2 - t1);

...gewinnt man nix und die benötigte Laufzeit verschlechtert sich: ~2050ms

Laut API ( ArrayDeque (Java Platform SE 6) ):

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue.

...ist ArrayDeque ja schneller als Stack und schneller als LinkedList, was gegenüber ArrayList aber keinen Vorteil darstellt.

Eine Alternative wäre es noch, kandidaten durch ein einfaches Array zu ersetzen. Dann werden aber zusätzliche Variablen benötigt, was die collection classes von sich aus schon bieten:

        long t1 = System.currentTimeMillis();

        int[] einQuadrat = new int[999999];
        einQuadrat[7] = 7;
        einQuadrat[77] = 77;
        einQuadrat[100] = 100;

        Set<Integer> vorhandene = new HashSet<Integer>();
        for (int i = 0; i < einQuadrat.length; i++) {
            vorhandene.add(einQuadrat[i]);
        }

        int[] kandidaten = new int[einQuadrat.length];
        for (int i = 1; i <= einQuadrat.length; i++) {
            kandidaten[i - 1] = i;
        }
        for (int i = 0; i < kandidaten.length; i++) {
            int j = (int) (Math.random() * kandidaten.length);
            int k = kandidaten[i];
            kandidaten[i] = kandidaten[j];
            kandidaten[j] = k;
        }

        int j = 0;
        for (int i = 0; i < einQuadrat.length; i++) {
            if (einQuadrat[i] == 0) {
                while (vorhandene.contains(kandidaten[j])) {
                    j++;
                }
                einQuadrat[i] = kandidaten[j];
                vorhandene.add(kandidaten[j++]);
            }
        }

        long t2 = System.currentTimeMillis();

        // System.out.println(Arrays.toString(einQuadrat));
        System.out.println(t2 - t1);

...unterscheidet sich in der Laufzeit nicht zu der Variante mit ArrayList.

Genug getestet für den Moment/heut e^^ (Für ein Danke wäre ich dankbar^^)