Java Sudoku generieren

LINUS19 · Verfasst: Di 09.01.18 00:51

Ich habe eine Methode gemacht um Sudokus zu generieren, die ein leeres Sudokufeld mit zufälligen Zahlen füllt und darauf dann solange die Lösemethode anwendet bis ein lösbares Sudoku entsteht.

Eigentlich müssten ja 2 unterschiedlich gefüllte Sudokus mit 30 Zahlen entstehen wenn ich generiere() 2 mal aufrufe, aber als Ergebnis kommt ein Sudoku mit 30 Zahlen und eins mit 60 Zahlen. Beim 2.Aufruf von generiere() wird wahrscheinlich die anzahl Variable, der Zufallszahlen weiter hochgezählt und deswegen sind es 60 Zahlen.

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:

static int[][] generiere(int Matrix[][]) {
    int counter=0;           
        System.out.println("Wie viele Zahlen sollen vorgegeben sein?");            
      int anzahl=30; //Anzahl der Zufallszahlen
  
    int m,n,random;
    
    Random generator = new Random();
        
    while(counter<anzahl) {
      m=generator.nextInt(9); // zufälliges Feld der Matrix
      n=generator.nextInt(9);
      random=generator.nextInt(10);
      
      if(random==0) { // nur Zahlen von 1-9
        continue;
      }        
      
      if( Matrix[m][n]==0 && check(m, n, random, Matrix)==true ) //übeprüft Zeilen,Spalten und Blöcke
      Matrix[m][n]=random;
            
      else continue;              
                                
    if(counter==anzahl) { // wenn alle Zufallszahlen gesetzt, restliche Felder auf Null setzten
          if(Matrix[m][n]!=random)
            Matrix[m][n]=0;            
        
    }    
    anzahl++;      
  
    
    }        
    for ( m = 0; m < 9; m++) {  //Feld ausgeben      
      for ( n = 0; n < 9; n++) {
        if(Matrix[m][n]==0)
        
          System.out.print(Matrix[m][n]+"");
      }
      System.out.println();
    }            
  }

Und die Main methode:

markieren

Quelltext

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

public static void main(String[] args) {
              
    int  Matrix[][] =         
    
     new  int[][] {          { 0,0,0,0,0,0,0,0,0},
                                 { 0,0,0,0,0,0,0,0,0},
                                 { 0,0,0,0,0,0,0,0,0},                                      
                                 
                                 { 0,0,0,0,0,0,0,0,0},
                                 { 0,0,0,0,0,0,0,0,0},
                                 { 0,0,0,0,0,0,0,0,0},                                     
                                 
                                 { 0,0,0,0,0,0,0,0,0},
                                 { 0,0,0,0,0,0,0,0,0},
                                 { 0,0,0,0,0,0,0,0,0}};       
     
  
           generiere(Matrix);
         System.out.println() ;
           generiere(Matrix);

Und als Ergebnis kommt das:
1 . Aufruf:
600524037
050000000
070000500
080700040
000809002
190005000
000371800
900240003
530008070
Hier sind 30 Zahlen

2.Aufruf:
601524037
258000901
479163580
385702149
704819062
196405008
040371856
910240003
532698070
Hier sind 60 Zahlen

LG
LINUS19

Symbroson · Verfasst: Di 09.01.18 01:38

Wie wäre es damit, dass du Matrix in main() zwischendurch nochmal resettest?

_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)

Th69 · Verfasst: Di 09.01.18 10:34

Zeile 13 der Methode generiere kannst du verbessern (so daß bisherige Zeilen 15-17 entfernt werden können):

markieren

Java

1:	random = 1 + generator.nextInt(9);

Horst_H · Verfasst: Di 09.01.18 15:24

Hallo,

als Anregung:
www1.wdr.de/radio/wd...doku-anzahl-102.html
user profile icon

Gravitar hat ein Programm Sudoku V0.753_Exe.zip mit 100 minimalen Sudoku's www.entwickler-ecke....iewtopic.php?t=65038

Gruß Horst

LINUS19 · Verfasst: Di 09.01.18 16:06

Es funktioniert jetzt, aber es werden auch alle Fehlversuche mit gedruckt ,wie bekomme ich es hin das nur das lösbare Sudoku gedruckt wird?.

markieren

Quelltext

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

 generiere(Matrix);
          while(solve(0, 0, Matrix)==false)  {  
               for(int m=0; m<9; m++) { // Matrix wir wieder auf Null gesetzt
            for(int n=0; n<9; n++) {
              Matrix[m][n]=0;
            }
          }
             generiere(Matrix);                                                         
           
          }
          
            
           if(solve(0, 0, Matrix)==true)                                                                
               return;

LG
LINUS19

Symbroson · Verfasst: Di 09.01.18 16:08

Zitat:

markieren

C++-Quelltext

1:	if(solve(0, 0, Matrix)==true) return;

für mich sieht das so aus als ob du nur nicht lösbare Sudokus ausgibst. Wo ist denn deine Ausgabe?

PS: bitte formatiere deine Quelltexte damit man ihn besser lesen kann

markieren

C++-Quelltext

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

  generiere(Matrix);
  while(solve(0, 0, Matrix)==false)  {  
    for(int m=0; m<9; m++) { // Matrix wir wieder auf Null gesetzt
      for(int n=0; n<9; n++) {
        Matrix[m][n]=0;
      }
    }
    generiere(Matrix);                                                         
  }
  if(solve(0, 0, Matrix)==true) return;

_________________
most good programmers do programming not because they expect to get paid or get adulation by the public, but because it's fun to program. (Linus Torvalds)

LINUS19 · Verfasst: Di 09.01.18 16:20

Ja er gibt alle Versuche aus und das letzte ist lösbar,das habe ich mit dem Löseprogramm probiert.

LINUS19 · Verfasst: Di 09.01.18 20:59

Wenn ich das so mache wird nur das gelöste Sudoku ausgegeben:

markieren

Quelltext

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

if (solve(0, 0, Matrix) == true) {

      for (int m = 0; m < 9; m++) {
        for (int n = 0; n < 9; n++) {          
          System.out.print(Matrix[m][n] + "");
        }
        System.out.println();
      }
            
    }

Die Ausgabe:
364895172
279164835
185732649
712548963
436917528
598623714
647289351
853471296
921356487

LG
LINUS19

Th69 · Verfasst: Mi 10.01.18 10:52

Aber warum rufst du zweimal die solve-Methode auf? Nach der while-Schleife brauchst du den erneuten Aufruf doch nicht mehr.

Du solltest lernen, etwas strukturierter zu programmieren - z.B. das Initialisieren sowie die Ausgabe der Matrix in eine eigene Methode auslagern.
Ein guter Ansatz dafür ist die Top-Down-Methode (s. z.B. Top-Down- und Bottom-Up-Design), d.h. zuerst einmal den Code als groben Methodenaufruf (Pseudocode) zu entwerfen und dann nach und nach die einzelnen Methoden auszuprogrammieren (dann können diese Methoden auch gleich für Unit-Tests herangezogen werden).

LINUS19 · Verfasst: Mi 10.01.18 15:12

Ich habe jetzt eine Ausgabe Methode gemacht und den 2. solve() Aufruf weggenommen.
Aber wenn ich die print(Matrix) Methode innerhalb der while() Schlaufe aufrufe, werden alle Versuche ausgegeben und am Ende das zu lösenden Sudoku und wenn ich die print Methode ausserhalb der while() Schlaufe aufrufe wird nur das komplett gelöste Sudoku ausgegeben.

Th69 · Verfasst: Mi 10.01.18 15:46

Achso, jetzt verstehe ich.
Du mußt dir natürlich nach dem Generieren die Matrix als Kopie speichern, damit du dann dieses Ausgangs-Sudoku nach erfolgreichem Lösen ausgeben kannst (denn innerhalb der solve-Methode veränderst du ja die übergebene Matrix).

LINUS19 · Verfasst: Mi 10.01.18 17:53

Nachdem die Matrix generiert wird wollte ich sie in ein mit Nullen gefülltes Array Kopie[][] kopieren.
Wenn ich dann die print(Kopie) mache wird wieder ein gefülltes Array ausgegeben.

markieren

Quelltext

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

while(solve(0, 0, Matrix)==false)  {  
                         
              for( m=0; m<9; m++) { // Matrix wir wieder auf Null gesetzt
            for( n=0; n<9; n++) {
              Matrix[m][n]=0;
            }
          }  
             generiere(Matrix);                                                                      
             System.arraycopy(Matrix, 0, Kopie, 0, Kopie.length); //Matrix wird in Kopie kopiert
                               
                
         }
 print(Kopie);

Th69 · Verfasst: Mi 10.01.18 18:10

Für ein 2-dimensionales Array mußt du für eine Kopie (wie die print-Methode) selber über die Werte iterieren (zumindestens über die 1. Dimension), s.a. How do I copy a 2 Dimensional array in Java? - so kopierst du nur Array-Referenzen.

PS: Packe am besten auch das Initialisieren (Zurücksetzen) der Matrix in eine eigene Methode.

LINUS19 · Verfasst: Mi 10.01.18 19:16

Das mit dem kopieren funktioniert jetzt. Ich habe jetzt 10 Programmdurchläufe gemacht mit 17 vorgegeben und komischerweise wird das generierte Feld dann immer nur mit Nullen ausgefüllt. Wenn ich aber 35 vorgegebene Zahlen nehme und 10 Durchläufe mache wird immer ein Sudoku mit 35 Zahlen richtig ausgegeben.
Woran könnte das liegen?

Th69 · Verfasst: Do 11.01.18 10:44

Dann wird wohl noch ein Fehler in der generiere-Methode sein.
Ist das immer noch die im Eingangsbeitrag stehende? Dort überprüfe noch mal die Verwendung der Variablen anzahl und counter (wundert mich, daß die Methode so überhaupt [in kurzer Zeit] terminiert)...

LINUS19 · Verfasst: Do 11.01.18 16:47

Th69 hat folgendes geschrieben :

Dann wird wohl noch ein Fehler in der generiere-Methode sein.
Ist das immer noch die im Eingangsbeitrag stehende? Dort überprüfe noch mal die Verwendung der Variablen anzahl und counter (wundert mich, daß die Methode so überhaupt [in kurzer Zeit] terminiert)...

Also wenn ich nur die generiere() Methode einpaar mal ausführe, dann werden die Sudokus mit 17 Zahlen immer richtig erzeugt. Die generiere() Methode habe ich auch nicht verändert. Wieso wundert es dich den, das die Methode terminiert?

Th69 · Verfasst: Do 11.01.18 17:27

Du erhöhst in Zeile 29 anzahl, fragst aber die Schleife auf counter < anzahl ab...

LINUS19 · Verfasst: Do 11.01.18 17:57

Dann habe ich anscheinend doch noch was verändert, da muss natürlich counter ++ stehen sonst würde ja gar nichts ausgegeben werden. Damit habe ich die Methode aber auch getestet. ( Nicht mit anzahl++)

Th69 · Verfasst: Do 11.01.18 18:26

Dann debugge mal die Methode (bzw. lass dir innerhalb der Schleife mal die Matrix testweise ausgeben).

LINUS19 · Verfasst: Do 11.01.18 19:31

Ich bin nochmal die generiere() Methode durchgegeangen und ich glaube doch nicht das dort der Fehler liegt, wahrscheinlich doch bei der main Methode.

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:

  public static void main(String[] args) {
      
        int  Matrix[][] = new  int[9][9];      //     
        int  Clone[][] = new  int[9][9];       // Kopie
       
          generiere(Matrix);          
         
          while( solve(0, 0, Matrix)==false  )  {  
               
            
                 for( int m=0; m<9; m++) { // Matrix wir wieder auf Null gesetzt
            for( int n=0; n<9; n++) {
              Matrix[m][n]=0;
              
            }
          }  
                             
                   generiere(Matrix);                                                                                             
             
             for(int m=0; m<9; m++) {
               for(int n=0; n<9; n++) {
                 Clone[m][n]=Matrix[m][n]; //kopiere
               }
             }            
             print(Clone);                                   
          }
          print(Clone);        
  }

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme