# sudoku generieren



## florian1x (4. Aug 2008)

Also ich wollte mich an ein Sudoku traun. Hab hierfür schon eins zwei sachen fertig


```
import java.util.Random;

/**
 * Eine Klasse zum erstellen eines Sudokufeldes
 *
 * @author Florian Weinhold
 * @version 1.0
 */
public class Sudoku {
	private int field[][] = null; //Das Feld in dem die Werte gespeichert werden
	private int n = 9; //Anzahl der Felder pro Reihe, Spalte
	private int num_box; //Anzahl der Boxen pro Reihe, Spalte
	private Random r = new Random();
	
	/**
	 * Konstuktor
	 */
	public Sudoku(){
		field = new int[n][n];
		num_box = (int)Math.sqrt(n); //Anzahl berechnen	
		generate(); //füllt soduko mit werten
	}

	/**
	 * Gibt den Integer-Wert des Feldes an der Position x,y zurück.
	 * 
	 * @param x verticale Angabe
	 * @param y horizontale Angabe
	 * 
	 * @return Wert des Feldes in INT.
	 */
	public int getField(int x, int y){
		return field[x][y];
	}
	
	/**
	 * Gibt das array mit allen Werten zurück.
	 * 
	 * @return Alle werte vom sudoku.
	 */
	public int[][] getAll(){
		return field;
	}
	/**
	 * Sezt den Integer-Wert des Feldes an der Position x,y.
	 * 
	 * @param x verticale Angabe
	 * @param y horizontale Angabe
	 */
	public void setField(int value, int x, int y){
		field[x][y] = value;
	}
	/**
	 * Sezt den Integer-Wert des Feldes an der Position x,y.
	 * 
	 * @param field enthält alle werte
	 */
	public void setall(int[][] field){
		this.field = field;
	}
	
	/**
	 * Füllt das gesammte Sudoku mit Werten
	 */
	public void generate(){
		int current = 0; //zwischenspeicher
		for(int x = 0; x < 9; x++){
			for(int y = 0; y < 9; y++){
				do{
					current = r.nextInt(n+1);
				}while(check(current, x, y));
				setField(current, x, y);
				System.out.println(Math.random());
			}
		}
	}
	
	/**
	 * Prüft auf Fehler
	 * 
	 * @param value zu prüfender Wert
	 * @param x Reihe in der geprüft wird
	 * @param y Spalte in der geprüft wird
	 * 
	 * @return bei einem Fehler wird true zurück gegeben
	 */
	public boolean check(int value,int x, int y){
		if(checkVertical(value, y)||checkHorizontal(value, x)||checkBox(value, x, y)){
			return true;
		}
		
		return false;
	}
	
	/**
	 * Prüft ob der Wert schon in einer Reihe vorkommt
	 * 
	 * @param value zu prüfender Wert
	 * @param y Spalte in der geprüft wird
	 * 
	 * @return bei einem Fehler wird true zurück gegeben
	 */
	public boolean checkVertical(int value, int y){
		for(int x = 0; x < n; x++){
			if(getField(x, y) == value){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Prüft ob der Wert schon in eine Spalte vorkommt
	 * 
	 * @param value zu prüfender Wert
	 * @param x Reihe in der geprüft wird
	 * 
	 * @return bei einem Fehler wird true zurück gegeben
	 */
	public boolean checkHorizontal(int value, int x){
		for(int y = 0; y < n; y++){
			if(getField(x, y) == value){
				return true;
			}
		}
		return false;
	}
	
	/**
	 * Prüft ob der Wert schon in einer Box vorkommt
	 * 
	 * @param value zu prüfender Wert
	 * @param x Reihe in der geprüft wird
	 * @param y Spalte in der geprüft wird
	 * 
	 * @return bei einem Fehler wird true zurück gegeben
	 */
	public boolean checkBox(int value, int x, int y){
		//erste Feld der Box herrausfinden
		int field_x = (int)(x/num_box)*num_box;
		int field_y = (int)(y/num_box)*num_box;
		
		for(x = field_x; x < field_x+num_box; x++){
			for(y = field_y; y < field_y+num_box; y++){
				if(value == getField(x, y)){
					return true;
				}
			}
		}
		return false;
	}
	
	public static void main(String[] args) {
		Sudoku S = new Sudoku();
		S.checkBox(10, 1, 1);
	}
}
```

enthalten sind bis jetzt ein paar check methoden, die überprüfen sollen ob ein fehler gefunden wurde
und ein paar get bzw set methoden

das funktioniert soweit ich weiß auch alles
mir macht die generate methode probleme


```
/**
	 * Füllt das gesammte Sudoku mit Werten
	 */
	public void generate(){
		int current = 0; //zwischenspeicher
		for(int x = 0; x < 9; x++){
			for(int y = 0; y < 9; y++){
				do{
					current = r.nextInt(n+1);
				}while(check(current, x, y));
				setField(current, x, y);
				System.out.println(Math.random());
			}
		}
	}
```
also die, die mein array mit werten füllt
meine methode macht dies zwar aber braucht wenn cih pech habe ewig
wenn sagen wa ma nur ne 2 in der reihe fehlt und der zufall es so will dass
diese einfach net gerandomed wird dann dauerts ewig bis die zahl vorkommt.


mein Lösungsansatz:
ein array mit den werten erzeugen mit den werten von 1-9
(bzw muss ich mein quelltext noch so umschreiben dass 0 als nicht gefüllt annimmt 
aber dass is ja net mein prob)
dieses array soll dann zufälluig gemischt werden




oder habt ihr nen besseren vorschlag, bzw einen quelltextauszug der mir weiterhelfen würde
ps: ich will keine fertiglösung... will ja auch noch was lernen 

mfG Florian Weinhold[/code]


----------



## 0001001 (4. Aug 2008)

Hm, 

wenn ich einen Sudoku Generator schreiben müsste, dann würde ich mir ein 9x9 Array anlegen, ein paar Werte darin zufällig festlegen und dann per Backtracking durchlaufen und prüfen ob das Sudoku valide ist. Just my 2 cents.


----------



## Campino (4. Aug 2008)

Meine Vorgehensweise, die ziemlich gut funktioniert: 

Erstelle eine beliebige Anordnung der Zahlen 1..9. 
Füll die erste Zeile mit dieser Reihe. Die zweite Zeile ebenfalls mit diesen Zahlen, allerdings um drei Felder verschoben. Die nächste Zeile wieder mit diesen Zahlen, erneut um drei Felder verschoben. Die ersten drei Zeilen sehen jetzt so aus (der Einfachheit halber habe ich als erste Folge die numerisch sortierte Abfolge genommen): 

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

Wie du siehst ergeben sich 3 richtige Felder und drei richtige Zeilen. 
Die nächste Reihe wird wieder mit dieser Folge gefüllt, diesmal um 4(!) Felder verschoben. Für die nächsten Beiden verschiebst du wieder um 3, zwischen der 6. und 7. Zeile (hier endet die zweite Felder- Zeile) wieder um 4, die letzten beiden erneut um 3 Felder. 

Das vollständige Sudoku sieht jetzt so aus (wieder mit der numerisch sortierten Startfolge): 

1 2 3 | 4 5 6 | 7 8 9 
7 8 9 | 1 2 3 | 4 5 6
4 5 6 | 7 8 9 | 1 2 3
----------------------
9 1 2 | 3 4 5 | 6 7 8
6 7 8 | 9 1 2 | 3 4 5
3 4 5 | 6 7 8 | 9 1 2
-----------------------
8 9 1 | 2 3 4 | 5 6 7
5 6 7 | 8 9 1 | 2 3 4
2 3 4 | 5 6 7 | 8 9 1

Leider ist dieses Sudoku relativ einfach, das Verschiebungsmuster ist klar zu erkennen. 
Um das zu ändern kannst du jetzt jeweils Zeilen 1- 3, 4- 6 und 7 bis 9 beliebig untereinander tauschen, dasselbe gilt für die Spalten 1- 3, 4- 6 und 7- 9 (Jeweils die innerhalb eines Feldes).


----------



## florian1x (4. Aug 2008)

mhhhh ma schaun ob mir noch was gutes einfällt


----------



## florian1x (5. Aug 2008)

ok alsoe ich habe mir jetzt ein array mit den werten von 1-9 erstellt
mit den namen values[]

das misch ich dann mit 

legende:
n - anzahl der felder pro reihe / spalte
values[] - array mit werten von 1-9 
check() - überprüft auf fehler


```
public void mixValues(){
		int save, z; //variablen zum speichern von zwischenwerten
		for(int count = 0; count < n ; count++){
			z = r.nextInt(n);
			save = values[count];
			values[count] = values[z];
			values[z] = save;
		}
		
	}
```

sooo nun hab ich ein gemischtes array bsp.:
2 9 5 3 1 4 8 6 7

soo nun kommt die funktion generate zum einsatz


```
public void generate(){
		int current = 0; //zwischenspeicher
		for(int x = 0; x < n; x++){
			for(int y = 0; y < n; y++){
				mixValues();
				for(int count = 0; check(current, x, y) ; count++){
					current = values[count];
				}
				setField(current, x, y);		
			}
		}
	}
```

diese funktion geht nun wie folgt vor
1. zuerst wird die erste reihe genommen und das erste feld mit dem ersten wert des gemischten arrays gefüllt.
2. dass array wird neu gemischt
3. jetzt das zweite feld der ersten reihe - hier wird das gemischte array solange durchgegangen wie ein Fehler gefunden wurde ( bsp 2 gleiche zahlen pro reihe) ist kein fehler vorhanden wird der wert des arras im feld gespeichert
4. das macht die schleife nun bis zum letzten feld 
5. das ganze nun auch mit den restlichen zeilen

nur irgendwann hab ich dann folgende fehler meldung



> Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
> at Sudoku.generate(Sudoku.java:83)
> at Sudoku.<init>(Sudoku.java:33)
> at Sudoku.main(Sudoku.java:196)



line 83 ist


```
current = values[count];
```


so und nun meine Theorie:
irgendwann passt keine zahl aus dem array da er immer einen fehler findet und dann zählt count übsers array hinaus
aber da im array die zahlen 1-9 sind und eine dieser zahlen ins array passen muss is das für mich net erklärlich


wäre nett wenn ihr ma schaun könnten
die check methoden sind weiter oben im threat schon aufgeführt


----------



## florian1x (5. Aug 2008)

ok also ich hab ma nen beispiel durchlaufen lassen

der erzeugt folgende tabelle 

4 3 1 | 8 6 5 | 9 7 2
2 8 7 | 3 9 1 | 6 5 4
9 5 6 | 7 4 2 | 8 1 3
------ | ------ | ------
3 2 5 | 4 8 6 | 1 9 7
7 6 8 | 1 2 3 | 4 x

bei x bricht er dann ab
da in der reihe nur noch die 5 und die 9 fehlen also muss eine der beiden zahlen vorkommen
nun sind beide aber schon in der spalte vorhanden 
ergo count zählt zu hoch.

jetzt hab ich nur keine idee wie ich das verhindere oder ob ich nicht schon den falschen ansatz hatte
war grad schon ein wenig stolz drauf dass ich das so hinbekommen hab 
mit dem array mischen ohne irgendwas zu kopieren, abzugucken oder hilfe aus dem netz

das mischen des arrays funktioniert schonma super 
hier ein bsp so wurden die zahlen für die oberste reihe in meinem bsp oben gemischt

Feld [0][0]:	4 1 6 2 9 7 5 8 3 
Feld [0][1]:	3 1 5 6 9 2 4 8 7 
Feld [0][2]:	1 3 4 6 2 8 5 9 7 
Feld [0][3]:	8 9 5 4 1 3 6 7 2 
Feld [0][4]:	8 4 6 7 2 1 5 9 3 
Feld [0][5]:	5 7 2 4 9 3 8 1 6 
Feld [0][6]:	8 9 4 1 7 5 6 3 2 
Feld [0][7]:	9 8 4 5 7 1 2 6 3 
Feld [0][8]:	7 5 6 2 1 3 9 8 4 

oder meint ihr das liegt dadran?

ich hab schon mit etwas glück fast ein ganzes hinbekommen ^^
bevor die fehlermeldung kam 

edit:
um nicht nochn post zu machen editier ich den hier ma

also hier nochma der quelltext auf das nötigste zusammengestaucht 
leider uach ohne beschreibungen die findet ihr aber oben


```
import java.util.Random;

public class Sudoku {
	private int field[][] = null; //Das Feld in dem die Werte gespeichert werden
	private int values[];
	private int n = 9; //Anzahl der Felder pro Reihe, Spalte
	private int num_box; //Anzahl der Boxen pro Reihe, Spalte
	private Random r = new Random();
	
	public Sudoku(){
		field = new int[n][n];
		num_box = (int)Math.sqrt(n); //Anzahl berechnen	
		values = new int[n+1]; 
		for(int count = 0; count < n; count++){
			values[count] = count+1;
		}
		generate();
	}
	
	public int getField(int x, int y){
		return field[x][y];
	}

	public void setField(int value, int x, int y){
		field[x][y] = value;
	}

	public void generate(){
		int current = 0; //zwischenspeicher
		for(int x = 0; x < n; x++){
			for(int y = 0; y < n; y++){
				mixValues();
				for(int count = 0; check(current, x, y) ; count++){
					current = values[count];
				}
				setField(current, x, y);		
			}
		}
	}
	

	public void mixValues(){
		int save, z; //variablen zum speichern von zwischenwerten
		for(int count = 0; count < n ; count++){
			z = r.nextInt(n);
			save = values[count];
			values[count] = values[z];
			values[z] = save;
		}
	}

	public boolean check(int value,int x, int y){
		if(checkVertical(value, y)){
			return true;
		}
		if(checkHorizontal(value, x)){
			return true;
		}
		if(checkBox(value, x, y)){
			return true;
		}
		
		return false;
	}
	
	public boolean checkVertical(int value, int y){
		for(int x = 0; x < n; x++){
			if(getField(x, y) == value){
				return true;
			}
		}
		return false;
	}
	
	public boolean checkHorizontal(int value, int x){
		for(int y = 0; y < n; y++){
			if(getField(x, y) == value){
				return true;
			}
		}
		return false;
	}
	
	public boolean checkBox(int value, int x, int y){
		//erste Feld der Box herrausfinden
		int field_x = (int)(x/num_box)*num_box;
		int field_y = (int)(y/num_box)*num_box;
		
		for(x = field_x; x < field_x+num_box; x++){
			for(y = field_y; y < field_y+num_box; y++){
				if(value == getField(x, y)){
					return true;
				}
			}
		}
		return false;
	}
}
```

mah das will mich nicht in ruhe lassen ^^
ich will den fehler jetzt finden oder mir soll was besseres einfallen


----------



## xysawq (6. Aug 2008)

Also ganz ehrlich ichfand die lösung von campino bis jetzt am besten. Und ich würde dir raten das auch so zu machen, weil das einfach, schnell und garantiert fehlerfrei ist.


----------



## florian1x (6. Aug 2008)

ich hab ne andere idee
mit meinem füllsystem fülle ich 2 beliebige reihen, dass is garantiert fehlerfrei
und dann lös ich den rest mit einer solve methode und fertig is das individuelle sudoku 
jetzt muss ich nur noch ne backtracking methode hinkriegen oder wenns besser geht ne bessere


----------



## Campino (6. Aug 2008)

Florian: 
Zum Thema Backtracking: 
Wenn zwei Zeilen gefüllt sind, muss der Computer noch 63 Werte ermitteln. Zum Ermitteln eines Wertes braucht er 3 Schleifen über je neun Felder (er muss ja gucken ob der Wert hier rein darf, also Reihe, Zeile und Feld prüfen), ich hab jetzt keine Lust zu zählen, aber grob geschätzt sind das 44 Operationen. 
Wenn bei einem Feld keine Zahl passt geht er zurück und versucht die nächste Zahl im vorherigen Feld. 
Bestenfalls (wenn bei jedem Feld die erste Zahl passt) braucht der Algorithmus also 44*63= 252 Operationen (+ den Teil für die ersten zwei Reihen). 

Im schlimmsten Fall prüft er für jedes Feld jede Zahl. Das sind dann 44*63^9 = 6,87*10^(17) Operationen. 
Ein aktueller Prozesser schafft grob geschätzt 2000 Operationen pro Sekunde (hier wird das ganze extrem ungenau, da in Java ja Bytecode interpretiert wird. Eine Java- Anweisung benötigt also mehrere Maschinenanweisungen. Deshalb können wir die Gigahertz- Anzahl des Prozessors nicht genau übernehmen.  Trotzdem halte ich 2000 für eine halbwegs exakte Schatzung). Im schlimmsten Fall braucht dein Algorithmus also 6,87*10^17 / 2000 = 3,43*10^14 Sekunden, das sind 10 906 389,89 Jahre. 
Ich persönlich habe keine Lust so lange zu warten, bis mein Sudoku fertig ist.


----------



## xysawq (6. Aug 2008)

naja... wenn du merkst, dass es länger als ein jahr dauert, kannst du den ja neu starten und hoffen, dass es diesmal schneller geht


----------



## xysawq (6. Aug 2008)

Sudoku Algorithmus

Schau mal da, wurde vor nichtmal 2 Jahren gepostet.
Und funktioniert wunderbar.


----------



## Marco13 (6. Aug 2008)

Verwendet aber, wenn ich das richtig sehe, auch Backtracking - ohne irgendwelche besonderen Tricks ... oder ???:L


----------



## xysawq (6. Aug 2008)

Nicht, dass ich wüsste... also in weniger als einer sekunde hat man ein fertiges sudoku (keine million jahre oder ne stunde).

Man muss allerdings den code noch leicht abändern, da es sonst eine klitzekleinen fehler gibt bei


```
public int[][] createSpielfeld(int showFields)
```

und zwar statt

```
int[][] field = cur;
```

sollte man

```
int[][] field = new int[cur.length][cur[0].length];
for(int x=0; x<cur.length; x++)
{
	System.arraycopy(cur[x], 0, field[x], 0, cur[x].length);
}
```

nehmen, weil man sonst die lösung vernichtet. 

EDIT:

Hab mal noch ne kleine main-methode dazu gemacht für die ausgabe:

```
public static void main(String[] args)
{
	int[][] loesung = null;
	int[][] feld = null;
	Sudo sudoku = new Sudo();
	
	sudoku.generateSudo();
	loesung = sudoku.getMatrix();
	feld = sudoku.createSpielfeld(10);
	
	for(int x=0; x<9; x++)
	{
		for(int times=0; times<2; times++)
		{
			int[][] temp = null;
			
			if(times==0)
			{
				temp = feld;
			}
			if(times==1)
			{
				temp = loesung;
			}
			
			for(int y=0; y<9; y++)
			{
				System.out.print(temp[x][y]+" ");
				if(y==2 || y==5)
				{
					System.out.print("| ");
				}
			}
			
			System.out.print("  ");
		}
		if(x==2 || x==5)
		{
			System.out.println();
			for(int times=0; times<2; times++)
			{
				System.out.print("------+-------+------   ");
			}
		}
		System.out.println();
	}
}
```


----------



## Marco13 (6. Aug 2008)

Campino's Rechnung bezog sich auch auf einen theoretischen Worst-Case-Fall - der ... rein vom Bauchgefühl her(!) ... spontan gesagt wohl nicht auftreten KANN: 

_Im schlimmsten Fall prüft er für jedes Feld jede Zahl. Das sind dann 44*63^9 = 6,87*10^(17) Operationen. _

Hab' jetzt den Teil davor (mit den "grob geschätzten" 44 (warum nicht 42?)) nicht nachvollzogen, aber ... : Beim ersten Feld hat man maximal 9 Möglichkeiten, beim zweiten maximal 8, dann maximal 7... also irgendwie könnte das auch "nur" xxx * 9! sein... (da müßte ich jetzt genauer drüber nachdenken, und es genauer nachvollziehen, aber ... nee.... )


----------



## florian1x (6. Aug 2008)

@campino: OK hast mich überzeugt ^^
@xysawq: ich schaus mir ma an, aber ich wollt ja selber eins schreiben und keins abkupfern ^^(halt mir nen bissle hilfe ausm forum)

soooo ma schaun ob ich heute noch was zu stande kriege

die version sieht auch nett und vorallem eigentlich recht leicht verständlich aus 
http://www.easy-coding.de/sudoku-algorithmus-backtracking-t1024.html

Edit
wobei mir bei eurer rechnung grad einfällt, dass ich das ja erst über zufall machen wollte also alles füllen, da hab ich sogar eins voll gekriegt aber hat auchn paar minuten gedauert


----------



## xysawq (7. Aug 2008)

@florian1x: Du kannst dir ja auch nur die Art und Weise von meinem Tipp anschauen, also funktionieren tuts auf jeden Fall. Deshalb mal anschauen, drüber nachdenken und selber programmieren (nicht abschreiben). 

@Marco13: Und dass es niemals 10 Millionen Jahre dauern wird ist mir auch klar. Aber im möglichen Worst-Case denke ich schon, dass es unerträglich lang sein wird.


----------



## W7FE (23. Mai 2012)

@xysawq:
Wie funktioniert denn dieser Algorithmus so genau?
Gibt es eventuell ne Möglichkeit diesen Code zu kommentieren, da es für den Anfang
gar nicht mal schlecht wäre, da ich erst vor kurzem mit JAVA angefangen und ich diesen Code
besonders interessant finde, aufgrund des interessant aussehendem Algorithmuses und 
der Nutzung von mehrdimensionalen Arrays. Das mit den Kommentaren muss nicht sein, jedoch wäre 
es für den Anfang nicht schlecht oder eine kurze Beschreibung vom Gesamtprogramm nochmal.

Vielen dank im voraus


----------

