Arrays

Java Insel: ​Arrays

Ein Array ist eine Zusammenfassung von Daten desselben Typs unter einem gemeinsamen Namen (Variable). Häufig verwendet man Arrays, um zusammengehörige Daten gemeinsam abzuspeichern, beispielsweise Messreihen einer Wetterstation oder Teilnehmer an einer Lehrveranstaltung.

Da alle Datensätze des Arrays unter demselben Namen ansprechbar sind, ist es notwendig, eine Möglichkeit zum Zugriff auf einzelne Werte zu schaffen. Dies geschieht durch eine Nummerierung. Die Werte sind im Array nummeriert gespeichert. Die Nummer, unter der ein Wert angesprochen (gelesen oder geschrieben) werden kann, nennt man Index.

Achtung

Arrayindizes sind nullbasiert. Die Zählung der Werte in einem Array beginnt mit der Zahl 0. Der erste Wert hat also den Index 0 und der letzte Wert den Index n - 1, wenn n die Anzahl der Werte ist.

Einführendes Beispiel

Temperaturmesswerte einer Wetterstation:

Uhrzeit	00:00	04:00	08:00	12:00	16:00	20:00
Temperatur	17.3	16.5	17.2	26.0	33.7	29.6

Zugehöriges Array:

Index	Wert
0	17.3
1	16.5
2	17.2
3	26.0
4	33.7
5	29.6

In Java:

// Arrays werden durch [] hinter dem Typ der Werte gekennzeichnet
double[] temperatur = {17.3, 16.5, 17.2, 26.0, 33.7, 29.6};

// Der Zugriff auf einen Wert erfolgt mit [] unter Angabe des Index
double mittagshitze = temperatur[3];

// mittagshitze enthält jetzt den Wert 26.0

Deklaration und Definition

Arrays werden durch eckige Klammern hinter dem Datentyp gekennzeichnet. Damit wird festgelegt, welcher Typ im Array gespeichert werden kann. Alle Elemente des Arrays müssen denselben Typ haben.

Allgemeine Form

datentyp[] name = new datentyp[Länge];

Arrays können auf verschiedene Arten deklariert und definiert werden:

// Array der Länge 5 mit Ganzzahlen
// Deklaration und Initialisierung getrennt
int[] zahlen;
zahlen = new int[5];

// Array der Länge 5 mit booleschen Werten
// Deklaration mit direkter Initialisierung
boolean[] bits = new boolean[5];

// Array der Länge 5 mit Zeichen
// Deklaration mit direkter und expliziter Initialisierung
// Diese Art der Initialisierung darf nur zusammen mit der
// Deklaration erfolgen, später nicht mehr.
char[] buchstaben = {'a', 'w', 'd', 's', 'q'};

Lesen und Schreiben von Daten

Auf die einzelnen Zellen (Werte) eines Arrays wird mit dem Namen des Arrays und eckigen Klammern [] zugegriffen. Zur Identifikation des einzelnen Wertes dient dabei dessen Index:

double[] temperatur = {17.3, 16.5, 17.2, 26.0, 33.7, 29.6};

// Der Zugriff auf einen Wert erfolgt mit [] unter Angabe des Index
double mittagshitze = temperatur[3];

// Der Zelle mit dem Index 2 wird der Wert 21.3 zugewiesen
// Beachte: Die Zelle mit dem Index 2 ist der DRITTE Wert (nullbasiert)
temperatur[2] = 21.3;

// temperatur enthält jetzt {17.3, 16.5, 21.3, 26.0, 33.7, 29.6}
//                                       ^^^^

Repräsentation im Speicher

Der Speicher der Java Virtual Machine ist sequenziell organisiert. Das bedeutet, dass die Speicherzellen, bei Null beginnend, aufsteigend nummeriert sind. Die Größe einer Speicherzelle entspricht dabei der Breite des Datenbusses, das sind aktuell üblicherweise 32 oder 64 bit.

Arrays sind sogenannte Referenztypen: Das Array belegt einen Speicherbereich einer festgelegten Größe (im oben gezeigten Beispiel mit den Temperaturmesswerten sechs Zellen der Größe double). Die Variable, unter der das Array angesprochen werden kann enthält die Nummer (auch Adresse genannt) der Speicherzelle 0 des Speicherbereiches des Arrays. Man sagt: Die Variable referenziert den Speicher des Arrays.

Beispiel mit Temperaturmesswerten:

Codebeispiel

Darstellung des Speichers

double[] temperatur = {17.3, 16.5, 17.2, 26.0, 33.7, 29.6}; double mittagshitze = temperatur[3]; // Der Variablen temp wird der Inhalt von temperatur, // die Adresse 42, zugewiesen. Es werden keine Daten kopiert. double[] temp = temperatur; // temp und temperatur verweisen jetzt auf denselben Speicherbereich // Der Zugriff erfolgt also in denselben Speicherbereich double morgenfrische = temp[1];

Die Speicheradressen sind willkürlich gewählt. Es gibt keinen besonderen Zusammenhang zwischen dem Quellcode und den Adressen. Wichtig ist an dieser Stelle nur, dass die Werte des Arrays an aufeinanderfolgenden Adressen (im Beispiel 42 - 47) liegen. Variable oder Array-Index Speicheradresse Speicherinhalt ... 0 42 17.3 1 43 16.5 2 44 17.2 3 45 26.0 4 46 33.7 5 47 29.6 ... temperatur 77 42 (Referenz auf die Arraydaten) mittagshitze 78 26.0 ... temp 93 42 (Referenz auf die Arraydaten) morgenfrische 94 16.5 ...

call-by-reference

Arrays unterscheiden sich grundlegend von primitiven Datentypen in Bezug auf ihre Nutzung als Methodenparameter. Wegen des ggf. großen Speicherbereiches, den ein Array belegt, wäre es sehr teuer, bei jedem Methodenaufruf den gesamten Speicherbereich zu kopieren und an die Methode zu übergeben.

Daher wird beim Methodenaufruf nur die Referenz an die Methode übergeben, so dass die Methode Vollzugriff auf den Speicherbereich des Arrays erhält. Für Arrays gilt im Gegensatz zu primitiven Typen, dass Methoden, die ein Array als Parameter erhalten, das Original, das außerhalb der Methode angelegt wurde, verändern können. Man spricht in diesem Zusammenhang von call-by-reference, da beim Aufruf die Referenz übergeben wird.

// Methode erhält ein Array und ändert einen Wert
public static void tuWas(int[] a) {
  a[3] = 42;
}

public static void main(String[] args) {
  // Array anlegen und initialisieren
  int[] tmp = {5, -3, 76, 33, -16, 7};

  // Methode aufrufen
  tuWas(tmp);

  // tmp enthält jetzt die Werte {5, -3, 76, 42, -16, 7}
  //                                         ^^
  // Es wurde in der Methode also das außerhalb definierte Array verändert.
}

Anmerkung: Technisch gesehen findet trotzdem ein call-by-value statt, denn die Methode erhält eine Kopie der Referenz (das ist eine Zahl, s. o.). Da diese Kopie aber auf denselben Speicherbereich verweist wie das Original, hat die Methode Zugriff auf die Originaldaten.

java.util.Arrays

Die Klasse ​Arrays der Java API enthält zahlreiche Methoden zum Umgang mit Arrays.

Ausgabe auf der Konsole

Ein Array lässt sich auf der Konsole ausgeben, indem man dessen String-Repräsentation ausgibt. Die String-Repräsentation liefert die Methode ​toString der Klasse Arrays:

import java.util.Arrays;

...

int[] a = {5, -3, 76, 33, -16, 7};

// Array ausgeben
// Ausgabe auf der Konsole: [5, -3, 76, 33, -16, 7]
System.out.println(Arrays.toString(a));

// Ohne toString wird nur die Objekt-ID des Arrays ausgegeben.
System.out.println(a);

Kopieren von Arrays

Da es sich bei Arrays um Referenztypen handelt, kann eine Kopie nicht durch einfache Zuweisung der Referenz erfolgen (Erläuterung siehe oben), sondern es muss eine explizite Kopie aller Werte erfolgen.

Beispiel Kopie "von Hand"

int[] a = {5, -3, 76, 33, -16, 7};

// zweites Array mit derselben Länge
int[] b = new int[a.length];

// Zellenweise kopieren
for (int i = 0; i < a.length; i++) {
  b[i] = a[i];
}

// das Array b ist jetzt eine echte Kopie des Arrays a

In der Klasse Arrays gibt es zum Kopieren von Arrays mehrere Methoden, die eine eigene Implementierung mit Schleifen obsolet machen:

• ​copyOf: kopiert das gesamte Array oder einen Abschnitt, beginnend bei Index 0
• ​copyOfRange: Kopiert einen frei wählbaren Abschnitt des Arrays
• Darüberhinaus gibt es in der Klasse ​System die Methode ​arraycopy, die es ebenfalls erlaubt, einen beliebigen Abschnitt zu kopieren. Die Klasse System muss nicht mittels import eingebunden werden.

import java.util.Arrays;

...

int[] a = {5, -3, 76, 33, -16, 7};

// Array mit copyOf kopieren
// b wird eine vollständige Kopie von a
int[] b = Arrays.copyOf(a, a.length);

// Nur einen Abschnitt kopieren
// c enthält dann die Werte {76, 33, -16}
// zweiter Parameter: Beginn des Abschnitts, inklusiv
// dritter Parameter: Ende des Abschnitts, EXKLUSIV
// Achtung! Der dritte Parameter gibt den ersten Index an, der NICHT mehr in die Kopie
// übernommen wird. Bei Angabe des Index 5 wird der Wert 7 aus a nicht kopiert.
int[] c = Arrays.copyOfRange(a, 2, 5);

// denselben Abschnitt mit System.arraycopy kopieren
// Das Zielarray muss vorher angelegt werden und ausreichend groß sein.
int[] d = new int[3];
System.arraycopy(a, 2, d, 0, 3);

Weitere nützliche Methoden

• ​Arrays.equals: Vergleicht zwei Arrays elementweise
• ​Arrays.fill: Weist jedem Element im Array den angegebenen Wert zu
• ​Arrays.sort: Sortiert das Array aufsteigend

Mehrdimensionale Arrays

Ein Array kann mehrere Dimensionen haben. Ein zweidimensionales Array kann beispielsweise als Matrix betrachtet werden, die aus Zeilen und Spalten aufgebaut ist. Für jede Dimension wird bei der Deklaration ein Paar eckige Klammern []angegeben.

Allgemeine Form

datentyp[][] name = new datentyp[Zeilen][Spalten];

datentyp[][][] name = new datentyp[Länge1][Länge2][Länge3];

usw.

Beispiel

int[][] m = new int[2][3];

erzeugt ein zweidimensionales Array mit zwei Zeilen und drei Spalten:

0	0	0
0	0	0

Mehrdimensionale Arrays lassen sich ebenfalls explizit initialisieren:

int[][] m = {{3, 1, 7}, {6, 0, 4}};

erzeugt

3	1	7
6	0	4

Aus diesem Beispiel wird deutlich, dass es sich bei mehrdimensionalen Arrays um Arrays von Arrays handelt. Das zweidimensionale int-Array m besteht aus den beiden eindimensionalen int-Arrays {3, 1, 7} und {6, 0, 4}. Die eindimensionalen Teilarrays können ganz normal über ihren Index angesprochen und verwendet werden:

int[][] m = {{3, 1, 7}, {6, 0, 4}};

// a verweist auf {3, 1, 7}
int[] a = m[0];

// b verweist auf {6, 0, 4}
int[] a = m[1];

Damit lassen sich auch mehrdimensionale Arrays definieren, deren Teilarrays nicht dieselbe Länge haben:

int[][] m = {{3}, {0, 4}, {6, 9, -2}};

// ergibt ein Array der Form
// 3
// 0 4
// 6 9 -2

Zugriff und Längen

Der Zugriff auf die einzelnen Werte erfolgt unter Angabe der Indizes in eckigen Klammern:

int[][] m = {{3, 1, 7}, {6, 0, 4}};

// n wird der Wert 4 zugewiesen (Zeile 1, Spalte 2)
int n = m[1][2];

Die Länge in mehrdimensionalen Arrays wird ebenfalls mit dem Attribut length bestimmt:

int[][] m = {{3}, {0, 4}, {6, 9, -2}};

// Array m ausgeben
for (int i = 0; i < m.length; i++) {

  // Die Länge der Einzelkomponenten kann ebenfalls mit length ermittelt werden
  for (int j = 0; j < m[i].length; j++) {

    System.out.print(m[i][j] + " ");
  }

  System.out.println();
}

Grundlegende Operationen auf / mit Arrays

Arraylänge

Arrays haben das Attribut length, das mit dem Punktoperator abgefragt werden kann. Es enthält die Anzahl der Werte im Array:

int[] a = {2, 5, 0, -8, 9, 2, 4};

// Ausgabe: 7
System.out.println(a.length);

Eine Zuweisung an das Attribut length ist nicht möglich, da in Java wegen der Art der Organisation des Speichers eine Änderung der Arraylänge nicht zulässig ist. Sofern ein Array vergrößert werden soll, muss eine echte Kopie angelegt werden, wobei das Zielarray die neue Größe hat:

import java.util.Arrays;

...

int[] a = {5, -3, 76, 33, -16, 7};

// Neues Array der Länge 10 als Kopie von a anlegen
// Durch die Zuweisung an a wird der zuvor von a belegte Speicher nach Abschluss
// der Operation freigegeben, SOFERN es keine weitere Referenz auf das Array gibt.
// copyOf füllt zusätzliche Zellen mit 0
// a enthält dann {5, -3, 76, 33, -16, 7, 0, 0, 0, 0}
a = Arrays.copyOf(a, 10);

Array-Durchlauf

Sehr häufig müssen Arrays durchlaufen werden, um eine Operation auf jedem Wert im Array auszuführen. Dafür empfiehlt sich die folgende for-Schleife:

int[] a = new int[20];

...

// Ausgabe aller Werte im Array
for (int i = 0; i < a.length; i++) {
  System.out.println(a[i]);
}

Alternativ kann eine erweiterte for-Schleife (auch for-each oder Iteratorschleife genannt) verwendet werden:

Allgemeine Form

for (Arraytyp Bezeichner: Array) {
  Anweisungsblock
}

Beispiel

int[] a = new int[20];

...

// Ausgabe aller Werte im Array
for (int e : a) {
  System.out.println(e);
}

Bei der Verwendung der erweiterten for-Schleife ist zu beachten, dass auf die Elemente des Arrays nur lesend zugegriffen werden kann. Eine Zuweisung wie z. B. e = e * 2; an die Elemente des Arrays ist nicht möglich.

Außerdem besteht kein Zugriff auf die benachbarten Elemente eines Elements. Mit der ausformulierten for-Schleife aus dem ersten Beispiel könnte mit a[i - 1] und a[i + 1] beispielsweise auf den Vorgänger und den Nachfolger des Elements a[i]zugegriffen werden.

Beispiele

Minimum bestimmen

int[] zahlen = {4, 0, -3, 7, 2};

// Ergebnis, wird mit erstem Wert des Arrays initialisiert
int min = zahlen[0];

// Position des Ergebnisses, wird mit erstem Index initialisiert
int minpos = 0;

// Array durchlaufen
for (int i = 0; i < zahlen.length; i++) {
  // Prüfen, ob der aktuelle Wert ein neues Minimum ist
  if (zahlen[i] < min) {
    // Minimum aktualisieren
    min = zahlen[i];
    // Position ebenfalls sichern
    minpos = i;
  }
}

System.out.println("Minimum: " + min + " an Position [" + minpos + "]");

Element suchen

int[] a = {4, 0, -3, 7, 2};

// gesuchter Wert
int x = 5;

// So lange weitergehen, bis entweder x gefunden oder Array komplett durchsucht
// Beachte: zuerst Länge prüfen, da sonst beim letzten Durchlauf ein zu großer
// Index geprüft wird --> IndexOutOfBoundsException
while (i < a.length && a[i] != x) {
  i++;
}

// Warum wurde die Schleife verlassen?
// (i == a.length): Bis zum Ende durchgelaufen, x nicht gefunden
// sonst: x gefunden
System.out.println(x + " gefunden: " + (i != a.length));

Primzahlen mit dem Sieb des Eratosthenes ausgeben

// Marker für Primzahlen
boolean[] prim = new boolean[200];

// Array initialisieren
// Alle Zahlen werden vorerst als prim betrachtet: setzte auf true
Arrays.fill(prim, true);

// Vielfache der Primzahlen streichen, beginne bei 2
for (int i = 2; i < prim.length; i++) {
  // ist die aktuelle zahl eine Primzahl?
  if (prim[i]) {
    // ja, ausgeben
    System.out.print(i + " ");

    // Vielfache streichen
    for (int j = i + i; j < prim.length; j = j + i) {
      prim[j] = false;
    }
  }
}

Endlicher Automat

Der endliche Automat berechnet für eine Binärzahl, ob sie durch 3 teilbar ist. Das gesamte Programm des Automaten steckt in der Zustandsübergangsfunktion im Array delta.

import java.util.Scanner;

/**
 * Demonstration zur Implementierung endlicher Automaten in Java mit
 * einem Array für die Zustandsübergangsfunktion
 *
 * Beispiel: Teilbarkeit einer Binärzahl durch 3
 *
 * @author Thomas Richter
 *
 */
public class EndlicherAutomat {

  public static void main(String[] args) {
    // Zustandsübergangsfunktion:
    //
    //                     |       neuer Zustand nach
    // aktueller Zustand   |   Eingabe 0    |     Eingabe 1
    //                     |                |
    //           0         |       0        |         1
    //           1         |       2        |         0
    //           2         |       1        |         2
    //
    int[][] delta = {{0, 1}, {2, 0}, {1, 2}};

    // Binärzahl als String einlesen
    Scanner scan = new Scanner(System.in);
    System.out.print("Eingabe (Binärzahl): ");
    String eingabe = scan.nextLine();

    // Startzustand setzen
    int zustand = 0;

    // Eingabe zeichenweise durchgehen
    for (int i = 0; i < eingabe.length(); i++) {
      // aktuelles Zeichen der Eingabe
      char ziffer = eingabe.charAt(i);

      // neuer Zustand: Eintrag in delta
      // Zeile: aktueller Zustand
      // Spalte: Eingabe
      // ASCII-Code der Ziffer muss noch in 0 oder 1 transformiert werden
      zustand = delta[zustand][ziffer - '0'];
    }

    // eingegebene Zahl binär und dezimal ausgeben
    System.out.print(eingabe + " (dezimal " + Integer.parseInt(eingabe, 2) + ")");

    // Der Automat akzeptiert die Eingabe, wenn der Endzustand 0 ist
    System.out.println(" teilbar durch 3: " + (zustand == 0));
  }
}

Beispiel Sudoku Solver

Als ausführliches Beispiel für die Verwendung von Bedingungen, Schleifen, Methoden und Arrays wird im Folgenden ein Sudoku Solver entwickelt. Das Programm ist in der Lage, 9x9 ​Sudokus mittels Brute Force zu lösen. Brute Force bedeutet, dass das Programm systematisch so lange Lösungsmöglichkeiten ausprobiert, bis die richtige Lösung gefunden ist.

Lösungsansatz

Das folgende Bild zeigt beispielhaft die initiale Belegung eines Sudoku (rote Zahlen). Es ist zu beachten, dass diese Belegung kein eindeutig lösbares Sudoku darstellt, sondern nur der Erläuterung dient.

Das Verfahren beginnt im obersten linken Feld und arbeitet zeilenweise nach unten rechts. Es wird die Zahl 1 in das aktuelle Feld gesetzt. Dann wird geprüft, ob diese Belegung nach den Sudokuregeln zulässig ist: jede Zahl darf in jeder Zeile, jeder Spalte und jedem Block nur genau einmal vorhanden sein. Die Prüfung auf Korrektheit erfolgt, indem geprüft wird, ob die einzusetzende Zahl bereits in der jeweiligen Zeile, Spalte oder dem Block vorhanden ist. Falls das nicht der Fall ist, wird sie eingesetzt. Im Beispiel ist die Einfügung der 1 oben links zulässig.

Danach wird zum nächsten Feld weitergerückt. Hier wird ebenfalls mit der 1 begonnen. Dies erleichtert die Implementierung, da kein Wissen über die Inhalte der anderen Felder erforderlich ist. Die Korrektheitsprüfung wird angesichts der 1 im ersten Feld fehlschlagen. In diesem Fall wird die einzusetzende Zahl so lange erhöht, bis eine Einfügung zulässig ist. Im Beispiel kann als nächstes die Zahl 4 eingesetzt werden, da die Zahlen 1, 2 und 3 bereits in demselben Block vorhanden sind.

Durch das Erhöhen der einzusetzenden Zahl nach fehlgeschlagener Korrektheitsprüfung kann der Fall eintreten, dass keine regelkonforme Zahl gefunden wird (das Verfahren erhöht bis zur 10). Im Beispiel kann für das orange gefärbte Feld keine gültige Einfügung gefunden werden:

• 1, 2, 3, 4 und 7 sind in demselben Block vorhanden
• 5, 6, 8, 9 sind in derselben Spalte vorhanden

In diesem Fall muss eine vorherige Einfügung fehlerhaft gewesen sein. Das Verfahren geht nun feldweise zurück, bis eine Einfügung gefunden wird. Trifft das Verfahren beim Zurückgehen auf initial belegte Felder, so werden diese übersprungen, da sie nicht geändert werden dürfen. Die gefundene Einfügung (im Beispiel die 4 im zweiten Feld) wird nun so lange erhöht, bis die Korrektheitsprüfung erfolgreich ist oder keine Einfügung möglich ist. Im ersten Fall wird die Zahl eingefügt (im Beispiel die 5 im zweiten Feld), während im zweiten Fall erneut ein Feld zurückgegangen wird, da der Fehler noch weiter vorn liegen muss.

Nach der erfolgreichen Einfügung der 5 im zweiten Feld kann im dritten Feld die 4 eingefügt werden:

Die weitere Anwendung des Verfahrens führt für die erste Zeile zum folgenden (vorläufigen) Ergebnis:

Bei genauer Betrachtung der initialen Belegung ist leicht zu erkennen, dass die gefundene Belegung der ersten Zeile nicht korrekt sein kann, da in den orange markierten Feldern des ersten Blocks die Zahlen 5, 6, 8 und 9 stehen müssen. Das Verfahren wird also im weiteren Verlauf noch bis zum ersten Feld zurückkehren (evtl. sogar mehrmals) und dort Änderungen vornehmen.

Das Verfahren endet, sobald für das letzte Feld (rechts unten) eine gültige Einfügung gefunden wurde.

Datenstruktur

Als Datenstruktur bietet sich ein zweidimensionales Array vom Typ int an. Das Verfahren muss in der Lage sein, eingefügte Zahlen von der Vorbelegung zu unterscheiden, da die Vorbelegung nicht verändert werden darf. Dazu gibt es verschiedene Möglichkeiten:

1. Es wird ein weiteres zweidimensionales Array, diesmal von Typ boolean verwendet, das an den Stellen der Vorbelegung jeweils true enthält.
2. Es wird die Tatsache genutzt, dass in einem gültigen Sudoku nur die Zahlen 0 (leeres Feld) bis 9 enthalten sein dürfen. Vorbelegungen können dann durch die Zahlen 11 bis 19 markiert werden.
3. Es werden für die Vorbelegungen die Zahlen -9 bis -1 verwendet.

Die ersten beiden Ansätze haben den Nachteil, dass bei vielen Zugriffen auf das Array zusätzliche Prüfungen notwendig sind. Beim zweiten Ansatz muss darüberhinaus noch subtrahiert werden. Außerdem wird es mit diesem Ansatz schwieriger, die Lösung auf Sudokus beliebiger Größe zu erweitern. Mit dem dritten Ansatz (negative Zahlen) kann der Zugriff in das Array ohne Bedingungsprüfung erfolgen, indem immer der Betrag des Feldinhalts verwendet wird. Zur Prüfung, ob es sich um ein vorbelegtes Feld handelt, genügt es, festzustellen, ob die Zahl kleiner als Null ist.

Korrektheitsprüfung

Bevor eine Zahl (Kandidat) in das Array eingefügt werden darf, ist es erforderlich zu prüfen, ob die Einfügung entsprechend der Sudoku-Regeln zulässig ist. Die Einfügung ist dann zulässig, wenn der Kandidat nicht bereits in der aktuellen Zeile und nicht in der aktuellen Spalte und nicht im aktuellen Block vorhanden ist.

Die entsprechenden Prüfungen werden in Methoden ausgelagert:

SELECT ALL Methoden zeileOK, spalteOK und blockOK:

During the example analyzing the following problems appear:

• Path element is not found.

Alternativ können die drei oben angegebenen Methoden zu einer Methode zusammengefasst werden, die mit jedem Schleifendurchlauf alle drei Kriterien prüft:

/**
 * Testet, ob die Zahl an der Stelle ohne Verletzung der Sudokubedingung
 * eingefügt werden kann. Die Methode ist eine Kombination der 3 Methoden
 * zeileOK, spalteOK und blockOK, die mit insgesamt nur einer Schleife auskommt.
 *
 * @param a
 *            9x9 Array mit dem Sudoku
 * @param zeile
 *            Zeile der zu prüfenden Zelle
 * @param spalte
 *            Spalte der zu prüfenden Zelle
 * @param kandidat
 *            Kandidat für die Einfügung
 * @return false, falls die Kandidatenzahl die Sudkobedingung verletzt,
 *         sonst true
 */
public static boolean kandidatOK(int[][] a, int zeile, int spalte, int kandidat) {
  // Feststellen in welchem Block wir eigentlich sind -> wir benötigen die
  // kleinste Zeile und die kleinste Spalte dieses Blocks als Offset
  int startZeile = zeile - zeile % 3;
  int startSpalte = spalte - spalte % 3;

  for (int i = 0; i < a.length; i++) {

    // teste Zeile, Spalte, Block, in dieser Reihenfolge
    if (Math.abs(a[zeile][i]) == kandidat
        || Math.abs(a[i][spalte]) == kandidat
        || Math.abs(a[startZeile + i / 3][startSpalte + i % 3]) == kandidat) {

      return false;
    }
  }
  return true;
}

Im Weiteren werden die drei erstgenannten Methoden verwendet, da sie intuitiver erscheinen. Im Gegenzug handelt man sich einen höheren Aufwand zur Prüfung ein, da eine erfolgreiche Prüfung mit den drei Methoden 27 Schleifendurchläufe benötigt, mit der Methode kandidatOK jedoch nur 9 Schleifendurchläufe.

Lösungsverfahren

Der oben genannte Lösungsansatz wird in der Methode

public static void solve(int[][] a) { ... }

implementiert. Die Methode nimmt ein zweidimensionales int-Array mit der Vorbelegung entgegen und löst das Sudoku in diesem Array. Das Array ist also nach dem Ende der Methode solve verändert und enthält das gelöste Sudoku.

Die Methode solve muss als lokale Daten im Wesentlichen nur die Zeile und Spalte des aktuell betrachteten Feldes sowie die Kandidatenzahl für dieses Feld speichern. Beim Speichern von Zeile und Spalte empfiehlt sich eine Überlegung zum Rechenaufwand:

Sobald um ein Feld vorgegangen wird, muss die Spaltennummer um Eins erhöht werden, beim Zurückgehen muss sie um Eins verringert werden. Dementsprechend muss am Zeilenende die Zeile um Eins erhöht und die Spalte auf Null gesetzt werden (vorwärts) bzw. die Zeile um Eins verringert und die Spalte auf Acht gesetzt werden (rückwärts). Dies erfordert, dass bei jedem Feldwechsel geprüft wird, ob ein Zeilenende oder -anfang überschritten wurde. Eine Vereinfachung lässt sich erreichen, wenn man sich die Felder als fortlaufende nummerierte Folge von Positionen (im 9x9 Sudoku von 0 .. 80) vorstellt und Zeile und Spalte aus der Position errechnet:

int zeile = position / 9;
int spalte = position % 9;

Der Wechsel zwischen den Feldern erfordert dann keine besondere Prüfung mehr, sondern kann mittels position++ und position-- erfolgen.

Unter Berücksichtigung dieser Überlegungen ergibt sich die Methode solve:

SELECT ALL Methode solve:

During the example analyzing the following problems appear:

• Path element is not found.

Übungsaufgaben

Sudoku Solver

Passen Sie den in der Vorlesung diskutierten Sudoku Solver Java_Quellcode_SOOP/vl/arrays/SudokuSolver.java so an, dass er für beliebig große Sudokus funktioniert. Beachten Sie, dass die Seitenlänge eines Sudokus eine Quadratzahl sein muss. In das Sudoku sollen dann jeweils die Zahlen [1 ... Seitenlänge] eingetragen werden. Es gelten dieselben Regeln wie für 9x9 Sudokus.