Changeset 396 in Java_Quellcode_SOOP_Vorlesung

Timestamp:

Dec 4, 2017, 9:21:38 PM (7 years ago)

Author:

tr

Message:

diverse Anpassungen von Kommentaren

Files:

• arrays/ArraysVL.java (moved) (moved from arrays/Arrays.java) (2 diffs)
• rekursion/Rekursion.java (modified) (2 diffs)
• rekursion/SudokuSolverRekursiv.java (modified) (2 diffs)

arrays/ArraysVL.java

@@ -1 +1 @@
 package eu.hsrw.tr.prog.vl.arrays;
 
-public class Arrays {
+import java.util.Arrays;
+
+public class ArraysVL {
     
     public static void main(String[] args) {
@@ -55 +57 @@
         }
     
+        // Alternativ:
+        Arrays.fill(prim, true);
+
         // Vielfache der Primzahlen streichen, beginne bei 2
         for (int i = 2; i < prim.length; i++) {

rekursion/Rekursion.java

@@ -29 +29 @@
      * Berechnet rekursiv n!
      * @param n n
-     * @return
+     * @return n!
      */
     public static int fakultaet(int n) {
@@ -41 +41 @@
      * Berechnet rekursiv 2^n
      * @param n n
-     * @return
+     * @return 2^n
      */
     public static int zweihoch(int n) {

rekursion/SudokuSolverRekursiv.java

@@ -44 +44 @@
     }
 
+    private static int aufrufe = 0;
+    
     /**
      * Löst das übergebene 9x9 Sudoku mittels Brute Force und Backtracking: Es
-     * wird mit dem Feld oben links begonnen und dann spalten- und zeilenweise
+     * wird mit dem Feld oben links begonnen und dann rekursiv spalten- und zeilenweise
      * nach rechts unten gearbeitet. Als erster Wert wird die 1 versucht. Falls
      * der Versuch einen Konflikt auslöst, wird die Zahl immer weiter erhöht,
-     * bis entweder kein Konflikt mehr auftritt oder die Zahl 10 erreicht wurde.
-     * Falls 10 erreicht wurde konnte kein passender Eintrag gefunden werden,
-     * das Problem muss also schon weiter vorn liegen. Es wird um ein Feld
-     * zurückgegangen und dort die nächsthöhere Zahl versucht. Ggf. sind sehr
-     * viele Rücksprünge erforderlich, da viele Kombinationen durchprobiert
-     * werden müssen.
+     * bis entweder kein Konflikt mehr auftritt oder die Zahl 9 überschritten
+     * wurde. Falls 9 überschritten wurde, konnte kein passender Eintrag
+     * gefunden werden, das Problem muss also schon weiter vorn liegen. Es wird
+     * um ein Feld zurückgegangen und dort die nächsthöhere Zahl versucht. Ggf.
+     * sind sehr viele Rücksprünge erforderlich, da viele Kombinationen
+     * durchprobiert werden müssen.
      * 
      * @param a
      *            zu lösendes Sudoku als 9x9 Array
+     * @param position
+     *            Index des aktuellen Feldes
+     * 
+     * @return Indikator, ob eine gültige Einfügung in das Feld gefunden wurde.
+     * 
      */
-    public static boolean solve(int[][] a, int feld) {
+    public static boolean solve(int[][] a, int position) {
+        aufrufe++;
+        
         // sind wir fertig?
-        if (feld == 81) {
+        if (position == 81) {
             return true;
         }
-        
-        int zeile = feld / 9;
-        int spalte = feld % 9;
-        
-        // ist das Feld vorbelegt?
+
+        // Zeile und Spalte aus dem Index der aktuellen Position berechnen
+        int zeile = position / 9;
+        int spalte = position % 9;
+
+        // ist das Feld an der aktuellen Position vorbelegt?
         if (a[zeile][spalte] != 0) {
-            return solve(a, feld + 1);
+            // gehe zum nächsten Feld
+            return solve(a, position + 1);
         }
-        
-        // Zahl testen
+
+        // Zahlen von 1 bis 9 testen: Konnte eingefügt werden, wird rekursiv die
+        // nächste Position angesprungen
         for (int kandidat = 1; kandidat <= 9; kandidat++) {
             if (kandidatOK(a, zeile, spalte, kandidat)) {
+                // Zahl an Position einfügen
                 a[zeile][spalte] = kandidat;
-                if (solve(a, feld + 1)) {
+                // Rekursiver Aufruf mit nächster Position
+                if (solve(a, position + 1)) {
+                    // Wir geben ein erhaltenes true weiter nach oben
                     return true;
                 }
-            }   
+            }
         }
-        
-        // keine Zahl hat gepasst
-        // aktuelle Zelle nullen und zurückspringen
+
+        // keine Zahl hat gepasst: Feld an der aktuellen Position nullen und
+        // zurückspringen.
+        // Durch den rekursiven Aufruf dieser Methode kehrt return einen Schritt
+        // nach oben zurück. Dort war die Position noch um 1 kleiner, es wird
+        // also nach vorn gegeangen.
         a[zeile][spalte] = 0;
         return false;
@@ -150 +168 @@
 
         solve(sudoku, 0);
+        
+        printSudoku(sudoku);
 
-        printSudoku(sudoku);
+        System.out.println("Aufrufe: " + aufrufe);
     }
 }