Java Sudoku Löser

LINUS19 · Verfasst: Sa 30.12.17 13:21

Hallo,
Ich wollte einen Sudoku Löser machen, den Lösungsalgorithmus mit rekursivem backtracking habe ich so weit verstanden, doch ich komme bei der Lösemethode nicht weiter. Vielleicht kann mir ja wer einen Tipp geben.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:

 
public class SudokuSolver {
  
  static boolean solve(int i, int j,int Matrix[][]) {
    if(i==9 && j==9)
      return true; //rechtes unteres Feld erreicht
    
    if(i==9) { // Eine Zeile weiter nach unten
      i=0;
    j++;
    }  
    
    if(Matrix[i][j] ==0) {    
      for(int value=1; value<=9; value++)   { // Alle Zahlen von 1-9 werde getestet
      
        if(save(i, j, value, Matrix)==true) { // GEhe auf nächstes freies Feld
        return solve(i+1, j, Matrix);
      }              
      }        
    }    
    Matrix[i][j]=0;  //Feld wird auf Null gesetzt
    return false;    
  }  
  
  static boolean save(int i,int j, int value, int Matrix[][]) {
    for(int k=0; k<9; k++) { // Zahl in Reihe doppelt
      if(value== Matrix[i][k])
        return false;
    }
    for(int k=0; k<9; k++) { // Zahl in Spalte doppelt
      if(value== Matrix[k][j])
        return false;
    }    
    
    // Block{
    
  //return false;  Zahl im 3*3 Block doppelt
    //}
    
    return true; // Zahl ist richtig  
}

  public static void print(int Matrix[][]) { // Sudoku Ausgabe
    System.out.printf("Lösung:");
    System.out.println();
    for (int x = 0; x < Matrix.length; x++) {
       for (int y = 0; y < Matrix.length; y++) {
      System.out.print(Matrix[x][y] + " ");
                                       
        }
      System.out.println();
                                               }
                                  } 
  
  public static void main(String[] args) {
  int  Matrix[][] =         // Sudoku was gelöst wird
      
       new  int[][] {{ 1,0,0,0,0,0,0,0,3},
                                      { 4,6,0,0,0,0,7,0,0},
                                      { 6,0,5,0,0,8,0,0,0},
                                      { 0,7,0,8,0,2,0,3,0},
                                      { 0,0,2,0,9,0,0,0,0},
                                      { 0,0,0,0,7,0,0,0,5},
                                      { 0,0,0,0,0,9,4,0,0},
                                      { 0,8,0,4,0,0,0,0,1},
                                      { 3,0,0,0,0,1,0,8,6}};       
       solve(1, 1, Matrix);
        print(Matrix); // bei der Ausgabe verändert sich nichts
System.out.println(save(0, 0, 3, Matrix));
  
  }
}

Jann1k · Verfasst: Sa 30.12.17 14:30

Es wäre gut, wenn du etwas mehr beschreiben könntest, wo genau das Problem ist. Terminiert der Algorithmus nicht? Kommst du mit der "Blocküberprüfung" nicht weiter? Bekommst du falsche Ergebnisse?

Beim ersten Überlesen: Ich glaube deine Abbruchbedingung ist nicht korrekt (i und j sollten niemals beide 9 sein, da j nur erhöht wird, wenn i wieder auf 0 gesetzt wird. Ich denke da müsste eher ein (i==9 && j==8) hin. Habs aber nicht getestet.

Moderiert von Th69: Code-Tags hinzugefügt

LINUS19 · Verfasst: Sa 30.12.17 15:21

Die Blocküberprüfung wollte ich später machen.
Das Programm hört auch auf, aber das Sudoku was ausgegeben wird ist unverändert zu dem was ich eingegeben habe.

Th69 · Verfasst: Sa 30.12.17 15:36

Du veränderst die Matrix ja auch nicht (außer das Nullsetzen)...

Am besten du verwendest dafür den Debugger, um Schritt für Schritt durch den Code zu gehen.

PS: Du solltest in der main für den solve-Aufruf bei (0,0) anfangen (Arrays sind null-basiert) - und daher auch die Abbruchbedingung anpassen (wundert mich allerdings, daß keine Exception fliegt)...

LINUS19 · Verfasst: Sa 30.12.17 16:05

Ich habe die solve( Methode jetzt so verändert:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

if(i==8 && j==8)
      return true; //rechtes unteres Feld erreicht
    
    if(i==9) { // Eine Zeile weiter nach unten
      i=0;
    j++;
    }  
    
    
    if (Matrix[i][j] != 0)  { // Nur Felder mit 0 sollen verändert werden                                       
             solve(i+1,j,Matrix);  //-> gehe einen Schritt weiter  
    }
    
      
      for(int value=1; value<=9; value++)   { // Alle Zahlen von 1-9 werde getestet
      
        if(save(i, j, value, Matrix)==true) { // Gehe auf nächstes freies Feld
        Matrix[i][j]=value; //setze den Wert
          if(solve(i+1,j,Matrix)==true) 
            return true;
      }              
      }        
      
    Matrix[i][j]=0;  //Feld wird auf Null gesetzt
    return false;

Und das Ergebnis:

Lösung:
0 2 4 5 6 7 8 9 3
0 6 1 2 3 8 9 7 5
0 1 5 3 2 9 7 4 8
0 7 6 9 8 1 2 3 4
0 8 3 1 9 4 5 6 2
0 4 9 8 1 6 3 5 7
0 5 2 6 7 3 4 1 9
0 3 8 7 4 5 6 2 1
0 9 7 4 5 2 1 8 6

Achso wegen dem Debbuger, ich habe schon öfter versucht ihn einzusetzen hat mir aber auch nicht viel gebracht ,weil ich damit nicht umgehen kann

Th69 · Verfasst: Sa 30.12.17 17:14

Aber wie willst du programmieren (lernen), wenn du die Tools nicht beherrschst?
Welche IDE verwendest du denn?

Und wegen dem Ergebnis (die Null-Spalte) schau dir mein PS aus meinem vorherigen Beitrag an.

LINUS19 · Verfasst: Sa 30.12.17 19:32

Ich verwende Eclipse Oxygen.

Das mit der Nullten Spalte funktioniert immer noch nicht(auch nicht mit i==9 && j==8), ich weiss nicht was ich da noch ändern könnte.
Warum wird die 8 zu so einem Smiley?

Moderiert von Th69: Code-Tags hinzugefügt

Th69 · Verfasst: So 31.12.17 10:39

Benutzt du jetzt solve(0, 0, Matrix) ?
Und dann die Abbruchbedingung auf >=8 ändern (der Smiley entsteht hier im Forum bei bestimmten Zeichenkombinationen, daher Code immer in Code-Tags packen!).

Und zum Debugger lies dir mal Eclipse IDE Debugging für Java-Entwickler durch und führe die Aktionen alle mal selber testweise aus...

LINUS19 · Verfasst: So 31.12.17 16:14

Ich habe den Fehler jetzt gefunden vordem solve(i+1,j,Matrix)

markieren

Quelltext

1:
2:
3:

 if (Matrix[i][j] != 0)  { // Nur Felder mit 0 sollen verändert werden                                                 
      return solve(i+1,j,Matrix);  //-> gehe einen Schritt weiter  
    }

fehlte einfach ein return, damit es übersprungen wird.

Das ist jetzt das Ergebnis:
Lösung:
1 2 4 5 6 7 8 9 3
4 6 1 3 8 5 7 2 9
6 1 5 7 3 8 9 4 2
5 7 9 8 1 2 6 3 4
7 3 2 6 9 4 1 5 8
2 4 8 9 7 6 3 1 5
8 5 3 1 2 9 4 6 7
9 8 6 4 5 3 2 7 1
3 9 7 2 4 1 5 8 6

Christian S. · Beiträge: 20451 Erhaltene Danke: 2264 Win 10 C# (VS 2019)

Da kommt im oberen, linken Block jetzt aber dreimal eine Eins vor. Oder habe ich Deine Darstellung missverstanden :gruebel:

LINUS19 hat folgendes geschrieben :

Lösung:
1 2 4 5 6 7 8 9 3
4 6 1 3 8 5 7 2 9
6 1 5 7 3 8 9 4 2
5 7 9 8 1 2 6 3 4
7 3 2 6 9 4 1 5 8
2 4 8 9 7 6 3 1 5
8 5 3 1 2 9 4 6 7
9 8 6 4 5 3 2 7 1
3 9 7 2 4 1 5 8 6

//edit: Ah, sorry, hatte das hier überlesen:

LINUS19 hat folgendes geschrieben :

Die Blocküberprüfung wollte ich später machen.

_________________
Zwei Worte werden Dir im Leben viele Türen öffnen - "ziehen" und "drücken".

LINUS19 · Verfasst: So 31.12.17 18:50

Bei der Blocküberprüfung habe ich doch noch ein Problem, wenn ich folgendes in die Methode einfüge:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

for (i = 0; i < 9; i = i + 3) { // Blocküberprüfung
      for (j = 0; j < 9; j = j + 3) {

        for (int a = 0; a < 3; a++) {
          for (int b = 0; b < 3; b++) {

            if (Matrix[a + i][b + j] == value)
              return false;
          }
        }
      }

    }

Wird das Sudoku was gelöst werden soll unverändert ausgegeben.

ub60 · Beiträge: 764 Erhaltene Danke: 127

Du prüfst hier alle Blöcke auf einmal. Du solltest jeweils nur einen Block prüfen und (in einer eigenen Funktion) i und j (und value) als Parameter übergeben.

ub60

LINUS19 · Verfasst: Mo 01.01.18 16:14

Ich habe die Blocküberprüfung nochmal verändert:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:

 int n =i-(i%3); //Blocküberprüfung 
  int m = j-(j%3);
        for (int a = 0; a < 3; a++) {
          for (int b = 0; b < 3; b++) {
            if (Matrix[a + n][b + m] == value)
              return false;
          }        
        }

Das Sudoku verändert sich wieder nicht. Dann habe ich den Debugger verwendet und das ganze Schrittweise ausgeführt und habe mir die Variablen anzeigen lassen, bis sich der erste Wert verändert hat : [[1, 0, 3, 0, 0, 0, 0, 0, 0] ( vorher { [0,0,3,0,0,0,0,0,0]}ich habe ein anderes Sudoku eingegeben, als beim ersten Post,nicht das ihr euch wundert).
Dann habe ich das Programm bis zum Ende ausgeführt und das ausgegebene Sudoku ist genauso geblieben wie das was ich eingeben habe. Ich kann mir nicht erklären woran das liegt

ub60 · Beiträge: 764 Erhaltene Danke: 127

Mein Java ist gerade etwas eingerostet, aber ich meinte etwa so:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

public boolean untersucheBlock(int i, int j, int value) 
{
  gefunden=false;
  for (int a = 0; a < 3; a++) 
  {
    for (int b = 0; b < 3; b++) 
    {
      if (Matrix[3*i+a][3*j+b] == value)
        gefunden=true;
    }
  }
  return gefunden;
}

Hiermit kannst du einen Neunerblock (i von 0-2, j von 0-2) auf das Vorhandensein eines bestimmten Wertes (value) untersuchen.

Ich hoffe zumindest, dass das Prinzip klar wird.

ub60

LINUS19 · Verfasst: Mo 01.01.18 19:26

Das Prinzip ist mir einigermaßen klar, ich hatte bei meinem Post vorher es ja auch ähnlich gemacht wie du, bei deinem Beispiel wird nur eine ArrayindexoutofBounds Exception geworfen. Und brauche ich dafür unbedingt noch eine extra Methode?

LINUS19

LINUS19 · Verfasst: Di 02.01.18 19:56

Ich habe es jetzt hinbekommen. Sowie ich die Blocküberprüfung vorher geschickt habe war es doch richtig, es wird jetzt die die richtige Lösung ausgegeben ich hatte mich wohl nur bei der Eingabe vom Sudoku vertippt.
Und ich habe ewig irgendwo anders nach einem Fehler gesucht...

GuaAck · Verfasst: So 07.01.18 00:02

Hallo Linus19,

ich wollte Deinen Code nachvollziehen und mal laufen lassen. (Ich habe mal einen eigenen Löser nach einem ganz anderen Algorithnus gemacht.) Leider habe ich dabei aber den Überblick über die verschiedenen Versionen verloren. Wäre sdhön, Du würdest den jetzt anscheindend korrekt laufenden Code noch einmal vollständig posten.

Gruß
GuaAck

LINUS19 · Verfasst: So 07.01.18 00:50

Hallo GuaAck,
Hier ist der der Code:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:

import java.util.Scanner;

public class SudokuSolver {  // Löst Sudokus von der Kommandozeile

  static boolean solve(int i, int j, int Matrix[][]) {
    if (i == 9 && j == 8)
      return true; // rechtes unteres Feld erreicht,abbruch

    if (i == 9) { // Eine Zeile weiter nach unten
      i = 0;
      j++;
    }

    if (Matrix[i][j] != 0) { // Nur Felder mit 0 sollen verändert werden
      return solve(i + 1, j, Matrix); // -> gehe einen Schritt weiter
    }

    for (int value = 1; value <= 9; value++) { // Alle Zahlen von 1-9 werde getestet

      if (check(i, j, value, Matrix) == true) { // Gehe auf nächstes freies Feld
        Matrix[i][j] = value; // setze den Wert
        if (solve(i + 1, j, Matrix) == true)
          return true;

        
      }

    }
    Matrix[i][j] = 0; // Feld wird auf Null gesetzt(backtrack)
    return false;
  }

  static boolean check(int i, int j, int value, int Matrix[][]) {
    for (int k = 0; k < 9; k++) { // Zahl in Reihe doppelt
      if (value == Matrix[i][k])
        return false;
    }
    for (int k = 0; k < 9; k++) { // Zahl in Spalte doppelt
      if (value == Matrix[k][j])
        return false;
    }

    int n = i - (i % 3); // Blocküberprüfung
    int m = j - (j % 3);
    for (int a = 0; a < 3; a++) {
      for (int b = 0; b < 3; b++) {
        if (Matrix[a + n][b + m] == value)
          return false;
      }
    }

    return true; // Zahl ist richtig
  }

  public static void print(int Matrix[][]) { // Sudoku Ausgabe
    System.out.println("Lösung:");
    System.out.println();
    int x;
    int y;
    for (x = 0; x < Matrix.length; x++) {
      if (x % 3 == 0)
        System.out.println("---------------------");

      for (y = 0; y < Matrix.length; y++) {

        if (y % 3 == 0)
          System.out.print("|");
        System.out.print(Matrix[x][y] + " ");

      }
    System.out.println();
    }
  }

  public static void main(String[] args) {
    
    int  Matrix[][] =         // Sudoku was gelöst wird direkt übergeben
      
       new  int[][] {{ 0,5,0,0,0,0,0,0,0},
                                      { 4,0,0,0,8,0,0,0,3},
                                      { 0,0,0,0,2,5,0,0,0},                                      
                                      
                                      { 0,0,0,0,0,0,6,0,0},
                                      { 0,1,0,0,0,2,0,0,0},
                                      { 5,0,0,6,0,9,0,0,4},                                     
                                      
                                      { 0,0,0,2,0,0,7,3,0},
                                      { 0,0,9,0,0,6,0,2,0},
                                      { 7,2,8,0,0,0,0,1,0}};       
       
    solve(0,0,Matrix);
                                                                               
    
// Oder über die Konsole eingeben
int Matrix[][] = new int[9][9];

    Scanner sc = new Scanner(System.in); //  Scanner zur Eingabe von Konsole

    System.out.println("Gib die Zahlen so ein:123456789, wenn das Feld leer ist -> 0 und 9 Zeilen 9 Spalten");

    for (int m = 0; m < 9; m++) {
      String eingabe = sc.nextLine();
      for (int n = 0; n < 9; n++) {

        Matrix[m][n] = eingabe.charAt(n) - '0'; // charAt() gibt Zeichencode zurück -'0' umwadlung in lesbar
      }
    }

    final long timeStart = System.currentTimeMillis(); // Zeitmessung
    solve(0, 0, Matrix);

    if (solve(0, 0, Matrix) == true) // wenn Sudoku lösbar ->
      print(Matrix); // wird es ausgegeben

    else
      System.out.println("Keine Lösung"); 

    final long timeEnd = System.currentTimeMillis();
    System.out.println("Lösungszeit: " + (timeEnd - timeStart) + " Millisek.");

  }
}

Welches Lösungsverfahren hast du den verwendet?

Gruß
LINUS19

GuaAck · Verfasst: So 07.01.18 19:56

Hallo Linus19,

ich hatte vor ein paar Jahren meine Lösung an die Logik angelenht, die ein Mensch auch macht, habe also Kriterien untersucht wie

- Ist für ein feld nur eine einzige Zahl erlaubt?
- Ist das Feld die einzige Möglichkeit in einer Zeile, ein bestimmte Zahl unterzubringen?
- usw.

Leider ist bei diesem Verfahren nicht sicher, dass man die Lösung findet. Ich habe 20 Beipiele, bei einem davon wird die Lösung nicht gefunden. Bei diesem Beispiel wird mit Deinem Algorithmus die Function Solve fast 2 Mio. mal aufgerufen, das ist deutlich mehr als bei allen anderen meiner Beispiele.

Gruß
GuaAck

Delphi-Laie · Verfasst: Mo 08.01.18 00:04

Wie man so etwas löst, ist mir seit Jahren klar. Nur hatte ich nie echte Muße und Antrieb, das umzusetzen.

Also, man geht das gesamte Feld - egal, bei welcher Zelle man beginnt - einmal durch. Für jede Zelle prüft man, wieviele Zahlen (oder irgendein anderes Symbol*) infragekommen. Ist nur eine(s) möglich, hat man den nächsten Lösungs(fort)schritt, und der nächste, das gesamte Feld durchschreitende Zyklus kann beginnen. Gelangt man jedoch ohne einen solchen Fortschritt wieder zur Ausgangszelle, ist man mit seinem Latein erstmal am Ende. Und jetzt kommt der zweite Teil:

GuaAck hat folgendes geschrieben :

Leider ist bei diesem Verfahren nicht sicher, dass man die Lösung findet.

Eben. Ist es nicht mehr so determiniert zu lösen, wie zuvor beschrieben, hilft nur noch - möglichst syxstematisches - Probieren, weshalb bei den Wettkämpfen auch Bleistifte verwandt werden. Dazu gibt es auf dem Computer die mächtige Möglichkeit der Rekursion, die sog. Backtracking ermöglicht. Damit kommt man noch viel weiter.

In einem Spektrum-Sonderheft (Mathematische Unterhaltungen, Nr. weiß ich jetzt nicht) gibt es ein ganzes Kapitel zu Sudokus. Dort ist eines mit nur 17 belegten Zellen enthalten, das dennoch eindeutig lösbar ist, allerdings mit systematischem Probieren.

*
"Für Freunde der Zahlenlogik", wenn ich einen solchen Blödsinn schon lese. Erstmal gibt es keine "Zahlenlogik", zweitens spielen nur die (verschiedenen) Symbole eine Rolle, es könnten also genausogut auch Buchstaben oder sonstwas sein, und drittens vergrault man sich per se schon viele potentielle Rätsler mit einer solchen Ankündigung, weil die meisten Mathematik nicht ausstehen können. Diese (fehlerhafte!) "Anpreisung" ist die größte, widersinnigste Abwerbung, die mir bis dato unterkam.

_________________
Ordnung ist das halbe Leben - und sie zu schaffen die andere Hälfte.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme