Sudoku Backtracking

[xyZman]

Hi Forum !
Habe ein Sudoku geschrieben welches mittels backtracking eine Lösung finden soll.
Er gibt schon ein neues Sudokufeld aus aber halt
111
222
333...
Das Problem liegt denke ich hier.
Ich weis nicht so recht was ich in diese Methode reinschreiben soll.
Hab einiges versucht aber Ausgabe war leider immernoch falsch.
-1 steht für ein leeres Feld
Es wäre super wenn es sich wer anschaut : )

Flo

1
2
5
public void zahlanders(int zeile, int spalte){
 
}

Das Ganze Programm

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
mport AlgoTools.IO;
 
public class Sudoku {
 
public static final int LEERES_FELD=-1;
/* zeile[z][x] wird true wenn in Zeile z die Zahl x gesetzt ist
 */
private boolean [][]zeile= new boolean[9][10];
 
/* spalte[s][x] wird true wenn in Spate s die Zahl x gesetzt wird
 */
private boolean[][]spalte=new boolean[9][10];
 
/*
 * box[][] ist true genau dann, wenn in der 3x3 Box die Zahl x gesetzt ist
 * Eine Zelle (z,s) ist in Box mit Index 3*(z /3 ) + (s / 3 )
 */
private boolean[][]box=new boolean[9][10];
 
/* SPIELFELD
 
 */
private int[][] sudokufeld=new int[9][9];
/* Vorgegebene Zahlen als Teilloesung
 */
private int[][]teilloesung;
 
/*
 *Sudoku mit Teilloesung erzeugen
 */public Sudoku(int[][]teilloesung)
{
this.teilloesung=teilloesung;
initialisieren();
}
/* Methode initialisieren,Teillösung wird generiert
 
 */
private void initialisieren(){
for(int boxnummer=0;boxnummer<9;boxnummer++)
{
  for(int zahl =1;zahl<10;zahl++)
  {
    this.box[boxnummer][zahl] = false;
}
}
  for(int zeile=0;zeile<9;zeile++)
  {
    for(int spalte=0;spalte<9;spalte++){
     this.zeile[zeile][spalte+1]=false;
     this.spalte[zeile][spalte+1]=false;
     this.sudokufeld[zeile][spalte] = LEERES_FELD;
     if(!isLeeresFeld(teilloesung[zeile][spalte])){
/*Fall hier ein bestimmter Wert hingehört
 *wird dies in den entsprechenden Datenstrukturen eingetagen
*/
     this.sudokufeld[zeile][spalte]=teilloesung[zeile][spalte];
     this.zeile[zeile][teilloesung[zeile][spalte]]=true;
     this.spalte[spalte][teilloesung[zeile][spalte]]=true;
     this.box[getBoxNummer(zeile,spalte)][teilloesung[zeile][spalte]]=true;
 
}
}
}
}
/* Erzeugung isLeeresFeld
 */
private boolean isLeeresFeld(int zahl){
return zahl<=0 || zahl >9;
 
}
/* Spielfeld ausgeben
 */
 
public void print(){
 for (int zeile=0;zeile <9; zeile++){
  for (int spalte=0;spalte<9; spalte++){
   System.out.print(sudokufeld[zeile][spalte]);
}
System.out.println();
 
}
}
 
/*Backtracking rekursiv suchen nach Lösung 
 *zaehler gibt die Anzahl belegter Zeilen an
 *Wenn ene Lösung gefunden wurde return true
 */
public boolean sucheLoesung(int zaehler) {
  int zeile = zaehler /9;
  int spalte = zaehler %9;
 
  for (int zahl =1; zahl < 10; zahl++){
    if (istOkay(zeile,spalte,zahl)){
            boolean z=this.zeile[zeile][zahl];
            boolean s=this.spalte[spalte][zahl];
            boolean b=this.box[getBoxNummer(zeile,spalte)][zahl];
            this.sudokufeld[zeile][spalte] = zahl;
            this.zeile[zeile][spalte] = true;
            this.spalte[zeile][spalte] = true;
            this.box[getBoxNummer(zeile,spalte)][zahl] = true;
      zahlanders(zeile,spalte);
      if (zaehler<80) {
    if (sucheLoesung(zaehler +1)) {
            return true;
          } else {
                this.sudokufeld[zeile][spalte]= teilloesung[zeile][spalte];
                this.zeile[zeile][zahl] = z;
                this.spalte[spalte][zahl] =s;
                this.box[getBoxNummer(zeile,spalte)][zahl] =b;
      zahlanders(zeile,spalte);
}
}
else
{
return true;
}
}
}
return false;
}
 
private int getBoxNummer(int zeile,int spalte){
   return 3*(zeile/3) + (spalte /3 );
}
 
/**
 * Sudoku zufällig erzeugen
 */
 
public void erzeugeSudoku(int anzahlVorgaben) {
      do {
        for (int zeile = 0; zeile < teilloesung.length; zeile++) {
           for (int spalte = 0; spalte < teilloesung[zeile].length; spalte++) {
                  teilloesung[zeile][spalte] = LEERES_FELD;
         }
     }
initialisieren();
 
 for (int i = 0; i < anzahlVorgaben; i++) {
   int zeile = (int) (Math.random() * 9);
      int spalte = (int) (Math.random() * 9);
        int zahl = 1 + (int) (Math.random() * 9);
       if (istOkay(zeile, spalte, zahl)) {
         this.sudokufeld[zeile][spalte] = zahl;
         this.zeile[zeile][zahl] = true;
         this.spalte[spalte][zahl] = true;
         this.box[getBoxNummer(zeile, spalte)][zahl] = true;
         teilloesung[zeile][spalte] = zahl;
   }
    }
  print();
  System.out.println();
initialisieren();
    }
while ( ! sucheLoesung(0));
 
  print();
  initialisieren();
            }
 
      /**
       * Gibt true zurück, wenn die gegebene zahl noch nicht in
       * der gegeben spalte, zeile oder zugehörigen 3 x 3 Box vorkommt
       */
    private boolean istOkay(int zeile, int spalte, int zahl) {
        return  (teilloesung[zeile][spalte] == zahl || isLeeresFeld(teilloesung[zeile][spalte])
                    && ! this.zeile[zeile][zahl]
                    && ! this.spalte[spalte][zahl]
                    && ! this.box[getBoxNummer(zeile, spalte)][zahl]);
      }
 
     public void zahlanders(int zeile, int spalte){
//hier//////////////////////////////////////////////////
////////////////////////////////////////////////////////
   }
 
 public int getZahl(int zeile, int spalte) {
         return this.sudokufeld[zeile][spalte];      }
  
      public int [] [] getTeilloesung() {
              return teilloesung;
      }
 
      public void printBoxNummern() {
              for (int zeile = 0; zeile < 9; zeile++) {
                      for (int spalte = 0; spalte < 9; spalte++) {
                              System.out.print(getBoxNummer(zeile, spalte));
                      }
                      System.out.println();
              }
      }
      public static void main(String argv[]) {
 
        Sudoku sudoku = new Sudoku(new int[][] {
            { 9,  -1, 3, -1,  1, -1,  7, -1, -1},
            {-1,  6, -1, -1, -1,  8,  5, -1, -1},
            {-1,  5, -1, -1, -1, -1, -1,  9,  6},
            {-1, -1, -1, -1,  3, -1,  6, -1,  4},
            {-1,  4, -1,  9, -1,  1,  3,  7,  2},
            {-1, -1, -1,  8,  7,  4, -1,  1, -1},
            {-1, -1,  5, -1, -1,  3,  2, -1,  1},
            { 6,  8,  7, -1, -1, -1, -1, -1, -1},
            { 3, -1, -1, -1, -1, -1, -1,  5, -1}
        });
       sudoku.printBoxNummern();
        if ( sudoku.sucheLoesung(0) ) {
          System.out.println("Lösung gefunden");
          sudoku.print();
        } else {
          System.out.println("Keine Lösung gefunden");
        }
 
      }
    }

[The_S]

Evtl. kannst du dir ja hier: Java Blog Buch : C) Sudoku Solver was abgucken.

[xyZman]

Danke für den Link aber das ist glaube ich nicht nach dem Schema nachdem ich arbeiten soll gestrickt.
So würde es gehen, aber kann ich das anders schreiben ?
Ich möchte diesen Listenerkram nicht benutzen

1
2
3
4
5
6
7
8
9
10
11
12
13
 public void zahlanders(int zeile, int spalte) {
204              for (SudokuListener sudokuListener : sudokuListeners ) {
205                      sudokuListener.zahlanders(zeile, spalte, sudokufeld[zeile][spalte]);
206              }
207      }
208      
209      public void addSudokuListener(SudokuListener sudokuListener) {
210              sudokuListeners.add(sudokuListener);
211      }
212      
213      public void remoeSudokuListener(SudokuListener sudokuListener) {
214              sudokuListeners.remove(sudokuListener);
215      }

[Andi_CH]

Listener brauchst du für die Konsolenapplikation definitv nicht.

Ich hab vorhin auch kurz in den Code geschaut und habe ihn nicht verstanden. Ohne nähere Info was "zahlanders" denn machen soll kann ich nicht helfen. (Die Zeit für ein ausführliches Reverse engineering fehlt mir)

Ich habe allerdings das Gefühl, dass mit der Ausgabe etwas nicht stimmt - ich würde das erst einmal untersuchen.

[xyZman]

naja wenn die Zahl sich geändert hat bzw also ungültig ist da dies im Backtracking ja ständig überprüft wird.
z.b wenn in einer Box 2 gleiche Nebeneinander stehen wird dieser Schritt ja Rückgängig gemacht.
199
256
378

Die Ausgabe kann somit nicht stimmen da dieser Entscheidene Schritt leider fehlt.

[Andi_CH]

... und was ist nun dein konkretes, Java-spezifisches Problem?

[Sonecc]

btw. zu dem Thema könnte die Forensuche helfen (meiner Erinnerung nach, gabs das nun schon zig mal als Thema)