# Rekursion-Probleme mit return



## Weenzeal (7. Mrz 2011)

Hi
ich habe folgendes Problem:
Ich bin dabei einen Sudoku-Solver umzusetzen. Ich habe die Zahlen in einem 2 dimensionalen Array abgespeichert (0 = leeres feld). Jetz überpüfe ich jedes feld(,dass die Zahl 0 gespeichert hat) des arrays auf die Übereinstimmung mit den "spielregeln" ab. Wenn eine Zahl in einem Feld eine "Regel" nicht erfüllt, wird die Zahl um 1 erhöht und die Methode ruft sich nocheinmal auf und probiert das solange bis sie bei 9 ist... Das geht alles super bis zur Abbruch bedingung. Wenn keine der zahlen 1 bis 9 passt springt das Programm zum letzten Feld das 0 war zurück und erhöht dort den Wert weiter bis zur nächsten passenden Zahl(geht denk ich auch noch aber soweit bin ich noch nicht gekommen). Andernfalls soll er einfach weiter machen. Hier liegt das Problem.
Hier ist mein code um das nochmal ein bisschen deutlicher zu machen. Programmiere noch nicht soo lange und ist deshalb wahrscheinlich ziemlich hässlich programmiert...


```
public void checken(){//ruft die lösungsmethode auf.
								//Hierhin soll zurückgekehrt werden, wenn eine passende Zahl gefunden wurde
			
			
			for(this.x=0;x < 9;x++){
				for(this.y=0;y < 9;y++){
					if(this.array[x][y] == 0){
						this.solve(1);
						xdavor = x;
						ydavor =y;
					}
				}
			}
			
		}
	public void solve(int i){//Überprüfungsmethode
			for(int a=0;a < 9;a++){
				if(i == this.array[x][a]){
					 solve(i+1);
				}else if(i == this.array[a][y]){
					solve(i+1);
				}
			}
			for(int b=0;b < 3;b++){
				for(int c=0;c < 3;c++){
					if(b == x && c == y){
						
					}else{
					if(x < 3 && y < 3){
						if(i == this.array[b][c]){
							solve(i+1);
						}
					
					}
					}
					if(b == x && c+3 == y){
						
					}else{
					if(x < 3 && y < 6 && y > 2){
						if(i == this.array[b][c+3]){
							solve(i+1);
						}
					
					}}
					if(b == x && c+6 == y){
						
					}else{
					if(x < 3 && y < 9 && y > 5){
						if(i == this.array[b][c+6]){
							solve(i+1);
						}
					
					}
					}
					if(b+3 == x && c == y){
						
					}else{
					if(x < 6 && x > 2 && y < 3){
						if(i == this.array[b+3][c]){
							solve(i+1);
						}
					
					}}
					if(b+3 == x && c+3 == y){
						
					}else{
					if(x < 6 && x > 2 && y < 6 && y > 2){
						if(i == this.array[b+3][c+3]){
							solve(i+1);
						}
					
					}}
					if(b+3 == x && c+6 == y){
						
					}else{
					if(x < 6 && x > 2 && y < 9 && y > 5){
						if(i == this.array[b+3][c+6]){
							solve(i+1);
						}
					
					}
					}
					if(b+6 == x && c == y){
						
					}else{
					if(x < 9 && x > 5 && y < 3){
						if(i == this.array[b+6][c]){
							solve(i+1);
						}
					
					}}
					if(b+6 == x && c+3 == y){
						
					}else{
					if(x < 9 && x > 5 && y < 6 && y > 2){
						if(i == this.array[b+6][c+3]){
							solve(i+1);
						}
					
					}}
					if(b+6 == x && c+6 == y){
						
					}else{
					if(x < 9 && x > 5 && y < 9 && y > 5){
						if(i == this.array[b+6][c+6]){
							solve(i+1);
						}
					
					}
					}
				}
			}
					if(i > 9){
						x = xdavor;
						y = ydavor;
						solve(idavor+1);
					}else{
					this.array[x][y]=i;
					idavor = i;
					return;// <--- PROBLEM!!!!
					}
					
				
			
		
			
		}
```

So mein Problem is jetz dass er nach diesem return nicht wieder zur checken() methode zurückkehrt und dort weitermacht sondern wieder die methode aufruft. Im Debugger springt er dann einfach wieder nach oben und a ist aufeinmal 5!!! Das endet dann alles in einem StackOverflow. Was mach ich falsch? 
Wär nett wenn mir jemand helfen könnte :toll:

mfg Weeeeeeenzeal


----------



## jonius (7. Mrz 2011)

Wenn solve sich selbst immer wieder aufruft, schachteln sich die Aufrufe praktisch. Wenn also beim letzten Aufruf der return-Befehl erreicht wird, springt er zum vorletzten solve() zurück, wenn er dort fertig ist, zum vorvorletzten usw. Das heißt, als letztes kehrt er zum ersten solve-Aufruf zurück, der am Ende nochmal Werte setzt, wenn ich das richtig sehe.
Warum du überhaupt den return-Befehl verwendest, verstehe ich nicht, da du ihn sowieso dort aufrufst, wo die Methode fertig ist und du auch keinen Rückgabewert hast.
Normalerweise arbeitet man bei Rekursion mit Rückgabewerten, die von den nächsthöheren Aufrufen weiterverarbeitet werden.


----------



## Weenzeal (7. Mrz 2011)

ok danke jetz wo dus sagst merk ich auch dass meine rekursion total sinnlos is  werds mal anderst versuchen


----------



## muckelzwerg (8. Mrz 2011)

Überleg Dir erstmal, wie Dein Löser arbeiten soll und entwickel dann Funktionen dafür.
Du willst Feld für Feld nach einer passenden Zahl suchen und dann immer ein Feld weiterspringen? Da wäre ein "Backtracking"-Verfahren.
Du setzt im ersten Feld eine 1 und schaust, ob das legal ist. Wenn nicht, wählst Du die nächste Zahl aus und schaust, ob diese legal ist.
Sobald Du die erste legale Zahl gefunden  hast wechselst Du zum nächsten Feld und versuchst dieses legal zu füllen.
Das setzt Du fort, bis Du das letzte Feld legal füllen kannst, oder keine der zehn Ziffern legal ist. 
Im ersten Fall hast Du eine Lösung gefunden im zweiten Fall eine unlösbare Situation erzeugt.
Im ersten Fall freust Du Dich, im zweiten Fall gehst Du einen Schritt zurück und wählst für das vorherige Feld die nächste legale Zahl aus. Gibt es auch dort keine, gehst Du noch ein Feld zurück ...

Alle Felder sind zu Begin auf 0. Dann schreibst Du die Zahlen aus dem Sudoku rein. Wenn Du ein Array verwendest, könntest Du die Zahlen aus der Aufgabe negativ setzen, damit Du sie nicht auch noch durchprobierst.
Und es wäre vielleicht ganz hilfreich auf ein eindimensionales Array zu wechseln, da macht die Verschachtelungen beim Ablauf etwas simpler. 
Und dann wirst Du da auch recht gut eine rekursive Funktion für finden.



Eine andere Variante wäre eine allgemeine Klasse für Tiefen- bzw. Breitensuche zu entwickeln.
Der nächste zu überprüfende Zustand wird nicht direkt per Rekursion aufgerufen, sondern in eine Liste (Vector ...) eingefügt.
Eine vorwärtsgerichtete Funktion arbeitet dann diese Liste ab. Findet sie eine Lösung beendet sie. Läuft sie die komplette Liste durch, ohne Lösung, gibt es keine.
Ob Breiten- oder Tiefensuche, entscheidet sich dann nur darüber, ob neue zu prüfende Zustände am Anfang oder am Ende der Liste hinzugefügt werden.


----------



## Weenzeal (9. Mrz 2011)

eigentlich wollte ich mein programm auch über die backtracking methode lösen hab es aber falsch umgesetzt. Ich hab vergessen, dass die ganzen schritte dann auch wieder "zurückgeschachtelt" werden. Ich werds jetz nochmal mit dem neuen wissen probieren und danke nochmal für eure tipps.
mfg Weenzeal


----------



## muckelzwerg (9. Mrz 2011)

Ich hab es vorgestern Abend gebastelt. Wenn Du ein Backtracking implementieren willst, folgende (hoffentlich hilfreiche) Anregungen.

- Präsentation des Spielfelds? 
Ich habe "0" für unbesetzt, 1-9 für die Ziffern und für die Ziffern aus der Aufgabenstellung negative Zahlen benutzt.
KEIN zweidimensionales Array. Das macht zwar die Indexierung etwas umständlicher (Modulo und Division anschauen, dann findest Du das schon raus),
dafür is es aber sehr angenehm, das Spielfeld komplett in einem Stück durchlaufen zu können.

- Welche Bedingungen muss ein Sudoku erfüllen? 
Zeilenkorrektheit: Alle Felder einer Zeile besetzt, alle Ziffern 1-9 jeweils einmal vorhanden.
Spaltenkorrektheit: Alle Felder einer Spalte besetzt, alle Ziffern 1-9 jeweils einmal vorhanden.
Blockkorrektheit: Alle Felder eines Blocks besetzt, alle Ziffern 1-9 jeweils einmal vorhanden.
Erfüllt ein 9x9 Feld diese Bedingungen, dann ist es ein Sudoku.
ABER, was passiert beim Füllen der Felder. Da fehlen Dir noch Ziffern. Da wird der Test immer durchrauschen, weil nicht alles voll besetzt ist.
Beim Backtracking willst Du aber bereits testen, wenn Du das nächste Feld setzt und nicht erst am Ende. 
Also überleg Dir da was, für Deine Korrektheitsfunktionen.

- Die Rekursionsfunktion ist gar nicht so umfangreich.
Du wirst irgendwann das Feld voll haben. Das musst Du erkennen und dann den strengen Korrektheitstest anwerfen.
Rückwärtsschritte werden ausgelöst, wenn das vollbesetzte Feld mit der letztmöglichen Belegung des letzten Feldes kein legales Sudoku ist, bzw. zwischendurch wenn für ein Feld keine legale Belegung mehr möglich ist.
(für das letzte Feld ist das gleichwertig)
Vorwärtsschritte werden ausgelöst, sobald eine legale Belegung gefunden wurde.
Was passiert wenn ein Rekursionspfad mit dem Ergebnis "Sackgasse, also so gehts schonmal nicht" zurückkommt?
Dann muss bei der ersten Auswahlmöglichkeit ein anderer Pfad gewählt werden.
Also muss Deine Rekursionsfunktion darauf warten, wie sich der angestoßene Pfad entwickelt und dann entweder eine andere Belegung versuchen, oder selbst nach "oben" zurückgeben, dass es auf diesem Weg nicht lösbar ist.


----------



## Samuel72 (9. Mrz 2011)

Hallo Weenzeal,

ich habe hier schon mal einen Sudoku-Solver eingestellt (Unter Multimedia- und Spieleprogrammierung; ich weiß leider nicht, wie man das verlinkt).
Vielleicht kannst du dort ja Anregungen finden.

Ich hab's rekursiv gemacht - und beim Abbruch wird eine Exception geworfen (so kommt man aus den Rekursionen raus).

Mein einziger Trick: Beim Setzen einer Zahl wird an alle Kästchen im gleichen Quadrat, in der gleichen Reihe und Spalte die Information gesendet, dass diese Zahl dort nicht mehr geht.


----------



## jonius (9. Mrz 2011)

Der Abbruch per Exception ist aber nicht gerade elegant. Die Exceptions sind für Ausnahmefehler gedacht.


----------



## Samuel72 (9. Mrz 2011)

Mir ist halt kein besserer Weg eingefallen, um aus den Rekursionen rauszukommen. Weißt du einen?

Übrigens glaube ich gar nicht, dass ich die Exception zweckentfremde: Sie wird geworfen, wenn es keine / mehr als eine Lösung gibt - ansonsten wird normal beendet.


----------



## Andi_CH (9. Mrz 2011)

Eine Rekursion wird immer dann verlassen wenn einen Antwort gegeben werden kann.

Dass das geschieht muss peinlich daruf geachtet werden, dass bei jdem rekursiven Aufruf die Anfangsbedingungen geändert werden und sich einem Abbruch annähern ...


----------



## muckelzwerg (9. Mrz 2011)

Kopier einfach die Adresszeile 
http://www.java-forum.org/spiele-multimedia-programmierung/114507-vorstellung-sudoku-solver.html

Ich verstehe ehrlich gesagt nicht ganz, wie Dein Löser funktioniert.
Das was Du beschrieben hast, ist naheliegend. Hinter jedem Feld verbirgt sich ein Vektor mit allen erlaubten Zahlen.
Sobald eine Zahl gesetzt wird, wird sie aus den Vektoren in der gleichen Spalte und Zeile und im Block entfernt.
Ist es das?
Damit kannst Du nicht jedes Sudoku lösen, weil es welche gibt, bei denen der nächste Schritt nicht immer eindeutig bestimmt ist.
Es gibt schwere Sudokus, bei denen man einige Zahlen "simulieren" muss und erst nach mehreren Schritten einen Widerspruch bekommt. 
Für solche Sudokus kann das Verfahren nur als "Vorstufe" helfen, weil damit bereits einige fixe Zahlen gefunden werden.
Vielleicht hab ich Dich aber auch nicht ganz richtig verstanden.

Was ich definitiv nicht verstehe ist, wie Du da die Rekursion reingewurschtelt hast. Das Eliminieren der illegalen Lösungen ist eigentlich super für ein iteratives Vorgehen. Man läuft die Felder komplet durch und wirft alles raus, was nicht mehr erlaubt ist.
Solange sich nach einem Durchlauf das Feld verändert hat, stößt man den nächsten an.
Dann gibt es entweder irgendwann einen Durchlauf nachdem alle Felder besetzt sind, oder keine Zahlen mehr eliminiert wurden.
Je nach dem, hat man die Lösung gefunden, bzw. einen Punkt erreicht, wo der nächste Schritt nicht mehr eindeutig ist.
Aber wie das genau bei Dir abläuft, blick ich bisher noch nicht. ^^


----------



## Samuel72 (9. Mrz 2011)

Hallo Muckelzwerg,

jedenfalls funktioniert mein Löser.
Ich hab das ganze nochmal etwas vereinfacht, ohne das vorherige Eliminieren der unerlaubten Lösungen und dafür mit einer Methode canSet.
Die Rekusion bewirkt jedenfalls, dass er sich durch alle Möglichkeiten durchwurstelt.
Sobald eine Lösung gefunden wird, wird diese (im Array l) gespeichert;
bei der zweiten Lösung wird eine Exception geworfen.


```
package sudoku;

import java.awt.BorderLayout;
import java.awt.Color;
import java.awt.Component;
import java.awt.Dimension;
import java.awt.FlowLayout;
import java.awt.GraphicsEnvironment;
import java.awt.Insets;
import java.awt.Rectangle;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Random;

import javax.swing.BorderFactory;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JPanel;
import javax.swing.JTable;
import javax.swing.SwingConstants;
import javax.swing.table.AbstractTableModel;
import javax.swing.table.TableCellRenderer;

@SuppressWarnings("serial")
public class Sudoku2 extends AbstractTableModel {
	class MyRenderer extends JLabel implements TableCellRenderer {
		public Component getTableCellRendererComponent(JTable arg0,
				Object obj, boolean sel, boolean foc, int r, int c) {
			setText(obj.toString());
			setHorizontalAlignment(SwingConstants.CENTER);
			setOpaque(true);			
			setBorder(foc?BorderFactory.createLineBorder(Color.darkGray):null);
			setBackground((r/3+c/3)%2==0?Color.lightGray:Color.white);
			return this;
		}		
	}
	abstract class MyButton extends JButton {
		MyButton(String s) {
			super(s);
			setMargin(new Insets(1,1,1,1));
			addActionListener(new ActionListener() {
				public void actionPerformed(ActionEvent e) {
					act();
				}
			});
		}
		abstract void act();
	}

	int[] z = new int[81];
	int[] l = new int[81];
	int[] p = new int[81];
	boolean solved;
	JLabel status;
	Random rnd = new Random();

	Sudoku2() {
		JTable tab = new JTable(this);
		tab.setDefaultRenderer(String.class, new MyRenderer());
		status = new JLabel(" ");
		status.setForeground(Color.red);
		status.setHorizontalAlignment(SwingConstants.CENTER);
		JFrame f = new JFrame("Sudoku");
		f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
		Rectangle r = GraphicsEnvironment.getLocalGraphicsEnvironment().getMaximumWindowBounds();
		f.setLocation(r.width/2-82,r.height/2-125);
		f.getContentPane().add(tab,BorderLayout.NORTH);
		f.getContentPane().add(status,BorderLayout.CENTER);
		f.getContentPane().add(getButtons(),BorderLayout.SOUTH);
		f.setSize(new Dimension(180,230));
		f.setVisible(true);
	}
	JPanel getButtons() {
		JPanel res = new JPanel(new FlowLayout());
		res.add(new MyButton("Lösen") {
			void act() {
				try {
					solve();	
					copy(l,z);
					fireTableDataChanged();
					status.setText(" ");
				} catch (Exception ex) {
					status.setText(ex.getMessage());
				}
			}
		});
		res.add(new MyButton("Neu") {
			void act() {
				z = new int[81];
				fireTableDataChanged();
				status.setText(" ");
			}
		});
		return res;
	}	
	boolean canSet(int[] p, int pos, int i) {
		for (int k=0; k<9; k++) {
			if (p[pos/9*9+k]==i) return false;
			if (p[pos%9+k*9]==i) return false;
			if (p[pos/27*27+(pos%9)/3*3+k%3+k/3*9]==i) return false;
		}
		return true;
	}
	void copy(int[] a, int[] b) {
		for (int i=0; i<81; i++)
			b[i] = a[i];
	}
	void solve() throws Exception {
		solved = false;
		copy(z,p);
		solve(0);
		if (!solved) 
			throw new Exception("Keine Lösung!");										
	}
	void solve(int n) throws Exception {
		if (n==81) {
			if (!solved) {				
				solved = true;
				copy(p,l);
			} else throw new Exception("Nicht eindeutig!");			
		} else {
			while (n<81 && p[n]!=0) n++;
			if (n==81) 
				solve(81);
			else
				for (int k=1; k<=9 ; k++) if (canSet(p,n,k)) {
					p[n] = k;
					solve(n+1);
					p[n] = 0;
				}
		}		
	}
	public static void main(String[] args) {
		new Sudoku2();
	}
	// Methoden von TableModel

	public int getColumnCount() { 
		return 9;
	}
	public int getRowCount() {
		return 9;
	}	
	public boolean isCellEditable(int r, int c) {
		return true;
	}	
	public Class<?> getColumnClass(int c) {
		return String.class;
	}
	public Object getValueAt(int r, int c) {
		return z[r*9+c]==0?"":String.valueOf(z[r*9+c]);		
	}
	public void setValueAt(Object obj, int r, int c) {
		int zn=0;
		try {
			zn = Integer.parseInt((String)obj);
			if (zn<0 || zn>9)
				zn = 0;
			if (!canSet(z,r*9+c,zn))
				zn = 0;
		} catch (Exception ex) {
			zn = 0;
		}
		z[r*9+c] = zn;				 		
	}
}
```


----------



## muckelzwerg (9. Mrz 2011)

Immerhin ein schöner Beweis, dass Kommentare, Benennung und Formatierung Einfluss auf die Lesbarkeit und Verständlichkeit haben.  
Wie kommst Du denn eigentlich zu Sudokus mit mehreren Lösungen? Setzt Du da nur ganz wenige Ziffern, oder hast Du welche, wo Du es vorher schon weißt?
Ich muss ja zugeben, dass ich immernoch nicht wirklich verstehe, welches Verfahren Du da genau anwendest.
Was ich z.B. sehe, ist dass Dein Program bei "nicht eindeutig" gar keine Lösung liefert. Das müsste der Moment sein wo kein einzelner Schritt mehr garantiert werden kann, wenn Du das Verfahren werwendest, was ich denke.
Das kann man theoretisch verbessern, in dem man nicht nur einzelne Ziffern eliminiert, sondern auch Pärchen, 3-Tupel ...
(macht aber auch nur begrenzt Sinn)
Das bedeutet dann aber auch, dass Du kein Sudoku lösen kannst, dass eine mehrschrittige Stelle beinhaltet.
Ich hab nur leider gerade keins, von dem ich das garantiert weiß. Sonst würde ich es mal testen.

Edit: Ok, hab was gefunden.
Sudoku Rtsel mit Lsung - Nr. 130 sehr schwer 
Wenn ich das bei Dir eingebe, bekomme ich "nicht eindeutig" und keine Lösung.
Eine Lösung gibt es dafür allerdings, die lässt sich mit Backtracking auch finden und steht zur Kontrolle auf der Seite.
Ob es auch eine zweite Lösung gibt, kann ich noch nicht sagen. Vielleicht bau ich das mal um, und probiere nach dem ersten Treffer weiter.
"nicht eindeutig" bedeutet bei Dir aber nicht, dass das Rätsel nicht eindeutig lösbar ist, sondern dass kein nächster Schritt eindeutig bestimmt ist, wenn man versucht mit Tiefe 1 die Zahlen zu eliminieren.
Also es ist lösbar und vielleicht auch eindeutig, aber nicht mit diesem Verfahren.

Edit2: Hab gerade probiert. Das "Rätsel 130" hat nur eine Lösung.


----------



## Samuel72 (9. Mrz 2011)

Hallo muckelzwerg,

wenn ich mal dazukomme, baue ich Kommentare ein...

Ein Sudoku mit mehreren Lösungen ist beispielsweise das leere Blatt.

Rätsel Nr. 130 funktioniert bei mir. 
Es kann sein, dass du nach Eingabe des letzten Wertes die Zelle nicht verlassen hast, dann wird der Wert nicht übernommen (und es gibt mehrere Lösungen).


----------



## muckelzwerg (9. Mrz 2011)

Ja Du hast Recht, daran muss es gelegen haben. Eben hat es funktioniert.

Wer braucht schon Kommentare. Falls Du da irgendwann später wirklich nochmal reinschaust, musst Du halt ein bisschen grübeln. 

Das leere Blatt hat knapp 7 Trilliarden Lösungen, das könnte dann doch etwas dauern.
Das heißt, wenn es mehr als eine Lösung gibt, gibst Du gar keine mehr aus? (bzw. findest auch keine)
Hab grad mal probiert. Wenn ich beim Rätsel 130 die Fünf rechts unten weglasse, bekomme ich 12 Lösungen.


Edit: So, ich hab mich nochmal durchgewühlt. Du verwendest auch ein "ganz normales" Backtracking. Unsere Lösungsschleifen sind ziemlich ähnlich.
Nur gibts bei mir keine Exception, sondern einen booleschen Rückgabewert.  Darüber lässt sich auch gut entscheiden, ob noch mehr Lösungen probiert werden sollen. 
Der größte Unterschied liegt in der Testfunktion. Du hast nur eine und sehr viel kürzere Funktion, weil Du lediglich testen lässt, ob sich eine konkrete Ziffer an einer konkreten Stelle legal einsetzen lässt. 
Die benutzt Du sowohl beim Einfügen der Werte in die Tabelle, als auch beim Lösen. 
Ich prüfe unabhängig von einer neuen Ziffer, ob Zeile, Spalte und Block legal sind, das macht die Testfunktionen deutlich umfangreicher.


----------



## Weenzeal (9. Mrz 2011)

hey danke nochmal für eure hilfe hat mir viel geholfen  ich muss meine denkweise noch irgendwie umstellen is viel zu kompliziert. Wenn ich jetz sehe wie einfach des eig geht mit dem überprüfen und wie kompliziert ich mir das gemacht hab xD Ich hätt vorher nochmal ein einfacheres beispiel zum thema rekursion proggen sollen. Das was ich da am Anfang hatte, hatte mit Rekursion ja relative wenig zu tun. Aber jetz hab ichs geschnallt  ich habe nur noch eine frage warum benutze ich für die "anfangswerte" negative zahlen und wie kann ich diese dann in die kontrolle miteinbeziehen?


----------



## muckelzwerg (9. Mrz 2011)

Die Überprüfung kann sehr stark vereinfacht (vom Programm, nicht vom Aufwand) werden, wenn Du Dich darauf beschränkst, das Einfügen einer konkreten Ziffer an einer bestimmten Stelle zu testen.
Da brauchst Du nur alle Felder der Zeile, Spalte und des Blocks durchgehen und schauen, ob die Ziffer schon vorhanden ist.
Was Du dadurch nicht bekommst ist ein Sudokutester. Du kannst so ohne Weiteres dann nicht entscheiden, ob ein gegebenes 9x9 Feld ein legales Sudoku ist, oder ob eine Zeile/Spalte legal ist.

Wahrscheinlich sieht man da ganz gut, wie unterschiedlich man an die Sache rangehen kann. Ich vermute mal Samuel72 hat seine Testfunktion "einfach so" zwischendurch geschrieben, als er sie brauchte.
Ich hab meine Lösungsfunktion als letztes geschrieben und zuerst Funktionen gebaut, um ein fertiges oder halbfertiges Sudoku zu prüfen.


----------



## Samuel72 (10. Mrz 2011)

Weenzeal hat gesagt.:


> ich habe nur noch eine frage warum benutze ich für die "anfangswerte" negative zahlen und wie kann ich diese dann in die kontrolle miteinbeziehen?


Das mit den negativen Zahlen ist eine elegante Methode, um die Anfangswerte von den später testweise eingesetzten Werten zu unterscheiden, damit du nicht versehentlich erstere veränderst. Du musst dann halt immer die Absolutwerte (Math.abs(x)) vergleichen.
Bei meiner Rekusion springe ich von leerer Zelle zu leerer Zelle und brauche also keine besondere Kennzeichnung der Anfangswerte.


----------



## muckelzwerg (10. Mrz 2011)

Ist auch wieder eine Frage der Entwicklungsphase. Ich hab ohne GUI angefangen und brauchte etwas, um die Felder gut zu codieren.
Außerdem hab ich die Löserfunktion als Letztes geschrieben und deshalb "zur Sicherheit" die vorgegebenen Zahlen von den gefundenen unterschieden.
Inzwischen hab ich das aber wieder geändert. Ich habe gestern Nacht (Sudoku basteln geht wohl nur nachts ^^) eine Visualisierung gebastelt, die das Backtracking einigermaßen gut zeigt.
Da hab ich die negativen Zahlen wieder rausgeschmissen.
Das kann man problemlos machen, weil man beim Rekursionsablauf ja weiß, dass alle Felder, die beim Betreten schon gesetzt sind, von der Aufgabenstellung kommen.
Samuel hat da eine Schleife und springt über solche Felder drüber, ich rufe da die nächste Rekursion auf.

Solange man also nicht zu jedem Zeitpunkt das Originalrätsel noch erkennen will, braucht man da keine Unterscheidung.
Ich hab das inzwischen auch rausgenommen und ein zweites Feld für Markierungen angelegt. Da können dann auch noch mehr Zustände eingetragen werden. Sonst geht es plötzlich los mit "erst negative, dann *10, dann *100 ..." und solchem Quark.
Es ist nett, um die Originalwerte zu codieren, aber mehr auch nicht. In der Lösungsschleife muss man bloß "if != 0 --> next" durch "if < 0 --> next" ersetzen. Und ansonsten macht man bei der Ausgabe, was man will. Die negativen Zahlen fett z.B.

Ohne eine besondere Kennzeichnung der Originalzahlen muss man eine Sache evtl. noch genauer überprüfen.
Wenn man auch bei einer gefunden Lösung "false" zurückgibt, damit nach weiteren Lösungen gesucht wird, löst man ja auch wieder Schleifen auf, die eine Originalzahl übersprungen haben. Da muss man aufpassen, dass sie auf dem "Rückweg" auch richtig reagieren, weil man auf dem Hinweg gerne denkt "ach komm, ein Feld weiter und das wars". 
Aber mit einer sauberen Rekursion ist es auch nur eine Zeile.


----------



## Andi_CH (10. Mrz 2011)

Ein funktionierende Lösung mit verschiedenen Lösungsansätzen ist hier zu finden.

4 Geradeaus-Strategien und der rekursive brute force Ansatz sind implementiert.


----------



## muckelzwerg (10. Mrz 2011)

ja, das ist das gleiche, was wir auch machen. Nur was meinst Du mit "Vier geradeaus Strategien"?
Das sind die normalen Testfunktionen. Bei Dir sind die auch abhängig von einer konkreten Zahl. Es gibt noch die Variante, dass man eine Zeile, Spalte oder Block allgemein auf Legalität prüft, ohne eine konkrete Zahl vorzugeben, die eingesetzt werden soll.
Deine "isValid" ist genau wie meine. Zeilen, Spalten, Blöcke.
Nur teste ich die jeweils etwas anders. Und Du hast ein 2D-Array, Samuel und ich haben es eindimensional aufgebaut.
Deswegen hast Du diese "nextFree(...)" Funktion, um das nächste Feld zu finden und die Originalwerte zu überspringen.
Wir haben da halt ein "c++" oder sowas.

Was heißt "längere Zeit"? Wie lange dauert es denn? Werd das später auch mal testen.



Hat jemand schonmal iterative Tiefensuche für Sudoku gebastelt? Wenn ja, habt ihr die Felder wirklich kopiert, oder was habt ihr da getrickst?


----------



## Andi_CH (10. Mrz 2011)

Schau einfach meine Lösung an!

Es sind Lösungsstrategiene implementiert - Strategeien sind nicht Tests!

Es ist ja wohl logisch , dass die Zahl dann auch plaziert wird, wenn sie eindeutig plaziert werden kann oder ist dieser Gedankensprung wirklich zu schwieirig ???:L :bahnhof:


----------



## muckelzwerg (10. Mrz 2011)

Weiß Du ich HABE mir Deine "Lösung" angesehen. Sonst wäre ich auch nicht so ausführlich darauf eingegangen. Woher kenne ich sonst die Namen Deiner Funktionen?
Ich werd mich da mit Dir nicht weiter drüber unterhalten.  Vielleicht bin ich zu empfindlich, vielleicht würde Dir auch etwas weniger Geltungsbedarf ganz gut tun.
Danke.



Weenzeal, wenn Du Fortschritte gemacht hast, lass auf jeden Fall mal hören.


----------



## Andi_CH (10. Mrz 2011)

Es ist schlicht und ergreifend einfach alles implementiert:

Die rekursive Funktion:

```
public boolean solveRecursive()
```

und die nicht rekursiven (bezeichne ich als geradeaus -> straight forward) Strategieprozeduren:

```
private int placeValueOnRow (final int y)
private int placeValueOnColumn (final int x)
private int placeValueOnSquare(final int x, final int y)
private int placeValueInField()
```
Welche eindeutig setzbare Zahlen einfügen
(Unschön, dass bei 
	
	
	
	





```
placeValueInField()
```
 der loop innerhalb ist - who cares.)

Die alle geben zurück wieviele Zahlen sie setzen konnten.

Die public prozedur

```
public boolean solveWithStrategies()
```
ruft die alle so lange auf, bis nichts mehr verändert werden konnte und gibt zurück ob überhaupt irgend Feld gesetzt werden konnte.

und die Testfunktion

```
public boolean isValid()
```
welche nacheinander testet ob alle Zeilen, Spalten und Quadrate gültig sind.

Was mich gestört hat ist deine Äusserung: "Das sind die normalen Testfunktionen." was ich so interpretiert habe, dass du eben nicht weisst was die Funktionen wirklich machen.


----------



## muckelzwerg (10. Mrz 2011)

Andi_CH hat gesagt.:


> Es ist schlicht und ergreifend einfach alles implementiert


Was auch immer Du damit meinst ...
Diese "Forwärtsstrategien" entsprechen dem Ansatz, Sudoku als Schnittmengenproblem aufzufassen.
Darüber haben wir hier im Thema auch schon gesprochen. Bei Wikipedia gibt es dazu auch einen Abschnitt.
Wie Du selbst schreibst, lösen diese Methoden viele Sudokus NICHT. Das liegt daran, dass sie nur einschrittig eindeutige
Belegungen finden. 
Entweder sinkt die Kandidatenmenge eines Feldes auf 1, weil sämtliche anderen Kandidaten durch die Belegungen in Reihe, Spalte und Block eliminiert werden.
Dazu bildet man die Vereinigungsmenge der Belegungen in Reihe, Spalte und Block, schneidet sie mit der Kandidatenmenge und bildet damit wieder die Komplementärmenge. Wenn da nur noch ein Feld übrigbleibt, kann man das setzen.
Oder man bildet die Komplementärmenge (also alle Belegungen, die für ein Feld NICHT mehr in Frage kommen) in Zeile Spalte und Block vereinigt diese und schneidet sie mit der Kandidatenmenge des zu prüfenden Feldes. Bleibt dort nur ein Element übrig, kann man das setzen.

Mit Deinen doppelten Schleifen bildest Du die Schnitte einzeln. Ob Du dabei beide Varianten abdeckst, weiß ich nicht. 
Man kann diese Verfahren noch erweitern, indem man Zahlentupel betrachtet. Dann kann man auch etwas mehr Sudokus damit lösen. Allerdings rollt man dadurch die Rekursion ab und macht es sich nicht gerade leichter. Bei den gängigen Lösern werden diese Verfahren als Vorstufe verwendet, um weniger Schritte beim Backtracking machen zu müssen. Und es gibt auch noch weitere Constraints die man Einfügen kann, die man meist auch vom Lösen mit der Hand kennt.
Z.B. A Sudoku Solver in C

Wer an der Rekursion weiter rumschrauben mag, kann sich z.B. von Knuth den "Algorithm X" und die "Dancing Links" anschauen. 
Da gibt es auch was für Java.
Dancing Sudoku by Daniel Seiler
Wenn man auf Rekursionen keinen Bock mehr hat, kann man auch mal iterativ vorgehen und Tiefensuche verwenden. Das lässt sich in Java ziemlich gut generisch machen. Und man sieht direkt mal einen Vorteil der Rekursion, weil sie nur einen aktuellen Zustand hat, wogegen man bei der klassischen Suche ohne Basteleien eine ganze Menge Sudokufelder im Speicher hat.


----------



## Samuel72 (10. Mrz 2011)

Jetzt habe ich mich nochmal einige Stunden damit rumgeschlagen, weil ich unbedingt ein Programm schreiben wollte, welches selber zufällige Sudokus erstellt. (Button [Rnd]).
Der Algorithmus ist denkbar einfach:


```
setze eine zufällige Zahl in eine zufällige Zelle
löse
wenn keine Lösung:
    lösche die letzte Zahl
    beginne von vorn
wenn mehrere Lösungen:
    beginne von vorn
wenn eine Lösung:
    fertig!
```
Ich vermute, dass mein Algorithmus immer terminiert; ca. 10 Sekunden sollte man schon warten;
manchmal bekommt man den Eindruck, er habe sich aufgehängt.

Deshalb habe ich das Ganze in einen Thread gepackt, damit man den Ablauf abbrechen kann (Button [Esc]).
Dazu musste ich die Rekusion auflösen (eine furchtbare Arbeit: Rekursionen nehmen einem so wunderbar das Denken ab...)


----------



## Weenzeal (10. Mrz 2011)

soo ich hab jetz nochmal was gebastelt. Gibt jetz schonmal kein stack overflow mehr . Aber dafür ändert er mein sudoku nicht sondern gibt das aus was eingegeben wurde.
Hier ist mein code

```
private int lösung[] = new int[81];
	
		
		public boolean checken(int n, int i){//Hab ich mal übernommen :)
			for(int a=0; a < 9;a++){
			if(lösung[n/9*9+a]==i)return false;
			if(lösung[n%9+a*9]==i)return false;
			if(lösung[n/27*27+(n%9)/3*3+a%3+a/3*9]==i)return false;
			}
			return true;
		}
		
		public void solve(int pos){
			
			
			
			if(lösung[pos] == 0){
				for(int a=1;a <= 9;a++){
					if(checken(pos,a )){
						lösung[pos] = a;
						if(pos != 80)
						solve(pos+1);
					}else{
						return;
					}
					
					
				}
		
			}
			else{
				if(pos != 80)
				solve(pos+1);
			}
			 if(pos == 80 && lösung[pos] != 0){
				int i = 0;
				for(int x =0;x < 9;x++){
					for(int y=0;y < 9;y++){
						 array[x][y] = lösung[i];
						i++;

					}
				}
			}else{
				solve(80);
			}
		}
```
und hier ist der Teil in dem ich die Methode solve aufrufe:

```
int i = 0;
				for(int x =0;x < 9;x++){
					for(int y=0;y < 9;y++){
						lösung[i] = array[x][y];
						i++;

					}
				}
				solve(0);
				
				for(int x =0;x < 9;x++){
					for(int y=0;y < 9;y++){
						System.out.println(array[x][y]);

					}
				}
```
joa und da printet das programm mir eben das gleiche raus was ich eingegen hab. So wie ich das sehe kann das nur daran liegen, dass die methode garnicht dazu kommt das lösungsarray ins zweidimensionale zu kopieren. Aber meiner Meinung nach müsste die Methode aber auch aufjedenfall dorthin kommen. Tut sie aber nicht


----------



## Samuel72 (10. Mrz 2011)

Hallo Wenzeal,
zwei Dinge sind mir aufgefallen:
- In der Rekursion sollte man die Abbruchbedingung immer am Anfang schreiben:[c]if(pos==81)[/c]...
- Wenn du die for-Schleife fertig durchlaufen hast, musst du [c]loesung[pos]=0[/c]setzen.


----------



## muckelzwerg (10. Mrz 2011)

Na wie wärs denn mal mit einer "printSudoku(...)" Funktion, die Du an den interessanten Stellen mal dazwischenklemmst?
Vor dem ersten Aufruf, zu beginn der Solve-Funktion ...
Sonst ist das doch nur Munkeln im Dunkeln. 

Du kannst Dir den Abbruch z.B. leichter machen, wenn Du Feld 81 am Anfang einmal abfängst.
Dann prüfst Du das ganze Sudoku und handelst entsprechend.

Edit: Samuel hat recht. Du musst dort wo die Rekursion "negativ zurückspringt" das Feld wieder freigeben. Sonst wirst Du es beim nächten Versuch übergehen.


----------



## Weenzeal (10. Mrz 2011)

danke für die schnelle antwort ich werd mal alles machen was ihr so gesagt habt


----------



## Weenzeal (10. Mrz 2011)

so habs jetz geändert und des print eingefügt. er springt wirklich nicht in die zielabfrage denn ich habe dort eine ausgabe des sudokus reingemacht es kommt aber keine.
hier is jetz mein neuer code:

```
public void solve(int pos){
			
			 if(pos == 80 && lösung[pos] != 0){
					int i = 0;
					for(int x =0;x < 9;x++){
						for(int y=0;y < 9;y++){
							 array[x][y] = lösung[i];
							i++;

						}
					}
					printSudoku(1);
				}
			
			if(lösung[pos] == 0){
				for(int a=1;a <= 9;a++){
					if(checken(pos,a )){
						lösung[pos] = a;
						if(pos != 80)
						solve(pos+1);
					}else{
						lösung[pos]=0;
						return;
					}
					
					
				}
		
			}
			else{
				if(pos != 80)
				solve(pos+1);
			}
			
		}

		public void printSudoku(int i){
			if(i == 1){
				for(int x=0; x < 81;x++){
					System.out.print(lösung[x]);
				}
			}else if(i==2){
				for(int x=0;x < 9; x++){
					for(int y=0; y <9;y++){
						System.out.print(array[x][y]);
					}
				}
			}
		}
```
und wenn ich jetz solve(0) macht printet er nichts und wenn ich unter solve(0) printSudoku(2) mach printet er das ausgangssudoku was auch völlig logisch ist wenn er das andere nicht printet. Ich frage mich nur warum es das andere nicht printet. Hoffe ihr könnt mir da weiterhelfen.


----------



## muckelzwerg (11. Mrz 2011)

Du hast Samuels Änderung nicht richtig umgesetzt. Schau Dir mal Deine Schleife mit dem Ausprobieren der Belegungen an.
Du gehst da durch, bis Du eine legale Belegung findest. Dann rufst Du "solve(pos+1)" auf.
Und was passiert nun, wenn dort keine passende Belegung mehr gefunden werden kann?
Nehmen wir an, Du hast bei pos+1 alles durchprobiert und nichts gefunden. Dann war "checken(...)" nie erfolgreich, Du hast also
auch nie eine Ziffer an pos+1 gesetzt.
Trotzdem würdest Du dann jedesmal, wenn Du gerade KEINE Ziffer gesetzt hast nochmal eine 0 drüberschreiben. (= null Effekt)
Wenn Du nun an pos einen Wert findest und dann bei pos+1 keine Belegung mehr findest, kommt der Aufruf von pos+1 zurück.
Dann bist Du wieder in der Schleife von pos und dort steht auch immernoch der letzte erfolgreiche Wert. Den musst Du JETZT wegbügeln, weil Du ja im nächsten Schritt (pos+1) nicht mehr erfolgreich weitermachen konntest.
Also anstatt im Else-Zweig eine 0 über eine andere 0 zu schreiben, musst Du direkt nach dem solve(pos+1), das feld wieder zurücksetzen.
Das siehst Du auch bei Samuel in der Solve Funktion.

An der Stelle rächt es sich, dass Du keinen Rückgabewert in Deiner Funktion verwendest. 
Da wärst Du gleich darüber gestolpert, was Du tun musst, wenn ein "false" zurückkommt.
Hier ist meine Löserfunktion. 


```
public boolean solve(int[] field, int pos){
		if( field == null || field.length != 81 || pos < 0 ){
			System.out.println("Wrong parameters to solve() ");
			return false;
		}
		
		// Check for the end of rekursion.
		if( pos > 80 ){
			// Final check at the end of the field. Not really necessary since field[81] wont be called without
			// a solved field.
			boolean result = isSudoku(field, true);
			
			// Should the rekursion stop, or try to find more Solutions?
			if( (result == true) && (findAllSolutions == true) ){
				if( keepSolutions == true )
					solutions.add(field.clone());
				setChanged();
				notifyObservers("Solution found");
				// Return false, to force trying for more solutions.
				return false;
			}
			return result; // actually allways true 
		}
		
		// Observer stuff, for GUI and User-Stepping.
		setChanged();
		notifyObservers("next Step");
		
		// The field ist already filled, so it hast to be some of the challenges values.
		// Call solve on the next pos and return immediately so that this field will get skipped in backtracking too.
		if( field[pos] > 0 )
			return solve( field, pos+1);

		// Now try to find a value for the current field.
		int value = 1;
		boolean success = false;
		while( value < 10 ){
			// Observer stuff, for GUI and User-Stepping.
			setChanged();
			notifyObservers("next Step");
			
			// Set the value and check the sudoku for legality.
			field[pos] = value;
			if( isSudoku(field, false) == true )
				success = solve(field, pos+1); // Value was legal, call solve on next field.
			
			if( success == true ) // Already on the way back, after finding a solution. Return "true" up to the root.
				return true;
			value++;
		}
		// The loop was not left via finding a solution, so this path was wrong and we backtrack.
		// Delete the field so that it can be set again on a different path.
		field[pos] = 0; 
			
		// Didn't return true till here ... return false, take a step back and try again.
		return false;
	}
```

Du siehst direkt als erstes die Abbruchbedingung. Es macht überhaupt nichts, wenn Du solve mit einem zu hohen Index aufrufst. Du darfst dann nur nicht losrechnen.
Dafür sparst Du Dir die zusätzlichen Tests weiter innerhalb.
Erreicht die Funktion das 82ste Feld, macht sie nochmal einen Test, der Vollständigkeit halber. Eigentlich ist der Überflüssig, weil solve(81) nicht aufgerufen wird, wenn field[80] nicht legal belegt wurde.
Standardverhalten ist dann, das Ergebnis des Tests (immer true) zurückzugeben und die Rekursion wieder aufzulösen. Wir wollen ja oben aus der ersten Schleife springen und ein "true" (="Lösung gefunden") zurückgeben.
Der andere Kram ist, um nach weiteren Lösungen zu suchen. Da wird dann trotz gefundener Lösung "false" zurückgegeben, damit das Backtracking fortschreitet.
Das führt dazu, dass alle Lösungen gefunden werden (je nach dem mit viel Zeit) und dass das Sudoku am Ende wieder leer ist.

(Den Observerkram kannst Du ignorieren)

Dann kommt der Test, ob das Feld schon belegt ist. Wenn ja wird das nächste Feld getestet. Wichtig ist, dass man hiernach sofort wieder zurückspringt, damit das Feld gesetzt bleibt. Bei Dir ist das durch die letzten Zeilen der Funktion gegeben.

Dann kommt die Schleife mit dem Ausprobieren der Werte. "isSudoku()"" teste unabhängig von der Eingabe ob das komplette Sudoku legal ist. Der zweite Parameter entscheidet ob "streng" (= Nullen sind Fehler) oder lax (= Nullen werden ignoriert) getestet wird.
Während des Probierens, will ich natürlich die noch unbesetzten Felder ignorieren.
(Der Code hinter "isSudoku()" ist SEHR viel umfangreicher, als Samuels Variante hat die gleiche Anzahl vergleiche und liefert andere Informationen. So wie er es gemacht hat, kann er theoretisch genau die Positionen aller "falschen" Felder bestimmen. 
Ich bekomme stattdessen die falschen Ziffern und ob sie zu viel oder zu wenig sind. Das bietet sich zum Testen von Spielerlösungen an, aber für die Rekursion ist es nicht so toll.)

Kommt das nächste Feld mit "true" zurück, dann wurde ganz am Ende ein korrektes Sudoku gefunden. Also wird weiter nach oben durchgereicht, um die Rekursion zu beenden.
Konnte keine Lösung gefunden werden, muss jetzt wieder das Feld gelöscht werden, damit es beim nächsten Versuch wieder gesetzt werden kann.


----------



## Andi_CH (11. Mrz 2011)

muckelzwerg hat gesagt.:


> Wie Du selbst schreibst, lösen diese Methoden viele Sudokus NICHT.



das habe ich nicht geschrieben - ich hab nur geschrieben, dass man allenfalls am Schluss noch die Rekursive Suche anwenden muss.

Die Suche nach doubletten, tri oder n-bletten (ich nehme an du meinst das finden von Feldern mit gleicher Kandiatenliste und streichen der Kandidaten aus den anderen Feldern) hab ich nicht implementiert weil ich nicht weiss wie ich das anpacken soll (und es bringt zu wenig.)

Beachte das Problem:

Kandidaten
Feld 1 : 1, 2
Feld 2 : 2, 3
Feld 3 : 1, 3 

Die Listen sind nicht identisch aber dennoch können die Werte 1, 2 und 3 in den anderen Feldern nicht mehr vorkommen
Ausserdem ich habe genau ein Sudokufeld im Speicher  (So blond bin ich dann auch wieder nicht)
Das einzige was sich bei der Rekursion ansammelt sind die Kordinaten des zuletzt veränderten Feldes und natürlich das was Java sonst so auf den Stack legen muss.

*Ich biete eine Wette an:*

50 Euro dem, der mir eine Sudoku liefert für das es eine Lösung gibt, das ich mit meinem Programm nicht lösen kann. (Im ganz strengen Sinn ist es übriges nur dann ein Sudoku, wenn es exakt eine Lösung gibt, aber das lassen wir mal weg) - ach ist doch klar - 50 Euro für mich, wenn ich die Lösung doch finde.

Ihr müsst gar nicht suchen  alleine der rekursive Ansatz löst jedes beliebige Sudoku -- die Strategien sind nur dazu da den Prozess zu beschleunigen.


----------



## muckelzwerg (11. Mrz 2011)

Ich weiß nicht, wem Du hier was beweisen willst. Entschuldige, aber ich habe das Gefühl Samuel und ich sind bei dem Thema schon ein ganzes Stück weiter. "Uns" brauchst Du nicht erklären, dass die Rekursion alle Möglichkeiten durchprobiert und alle Lösungen findet.
Denn das haben wir selbst seit einer Weile am Laufe und Weenzeal bastelt auch gerade daran herum. Abgesehen davon ist es weder "neu" noch besonders anspruchsvoll und fällt sowieso nur in die Kategorie "ICH hab jetzt auch mal einen Löser für Sudoku geschrieben".

Ich weiß nicht, wohin Du letztlich willst. Für mich sieht es so aus, als wolltest Du Dir und uns etwas beweisen. Auch wie Du Deine Lösung vorgestellt hast, und jetzt sogar von Wetten redest, gibt mir dieses Gefühl. Auch wenn DU mir jetzt erzählst, dass die "Vorwärtsstrategien zu Reduktion genutzt werden", nachdem ich das vorher selbst geschrieben habe. Du solltest das nicht nötig und wir daran kein Interesse haben.
Sorry, der Platz des schlaueren Bastlers/Programmierers, der den anderen irgendwas erzählen kann wird bei diesem Thema hier nicht vergeben. 

Wenn Du etwas Interessantes mit den Funktionen zum Schnittmengenproblem machen willst, kannst Du ja vielleicht ein bisschen Statistik machen, wieviele Felder im Schnitt gelöst werden, bevor die Rekursion gebraucht wird. Oder welche Sudokus sich ohne Rekursion lösen lassen, oder im Vergleich wie weit die direkten Funktionen bei minimalen Sudokus (17 belegte Felder) kommen.
Oder Du implementierst die anderen Schnittmengenfunktionen eben doch noch. Wie das geht, habe ich eigentlich schon beschrieben. Dafür würden sich in Java generische Klassen für Mengenoperationen anbieten. 

Wenn Du was beweisen willst, dann beweis die 17 Felder Grenze. (oder auch eine Niedrigere).


----------



## Weenzeal (13. Mrz 2011)

ich hab jetz deine vorschläge miteingebracht und hab selber glaub ich noch einen kleinen fehler gefunden.
ich habe ja überprüft ob pos != 80 is damit er nicht auf 81 geht. Hab jetz noch eingefügt wenn es 80 ist das er dann noch mal solve(80) macht damit er in die abbruchbedingung gelangt. Hat aber schon wieder nicht geklappt  

```
public void solve(int pos){
			
			 if(pos == 80 && lösung[pos] != 0){
					int i = 0;
					for(int x =0;x < 9;x++){
						for(int y=0;y < 9;y++){
							 array[x][y] = lösung[i];
							i++;

						}
					}
					printSudoku(1);
				}
			
			if(lösung[pos] == 0){
				for(int a=1;a <= 9;a++){
					if(checken(pos,a )){
						lösung[pos] = a;
						if(pos != 80){
						solve(pos+1);
						lösung[pos] = 0;}
						else{
							solve(80);
						}
					}else{
						
						return;
					}
					
					
				}
		
			}
			else{
				if(pos != 80)
				solve(pos+1);
				else solve(80);
			}
			
		}
```


----------



## muckelzwerg (14. Mrz 2011)

Hm, langsam. Das "Oberste" soll der Abbruch sein? Da fehlt für mich ein "return". Darauf zu pokern, dass er bis in das untere return läuft, wäre mir zu abenteuerlich.
Außerdem ist im zweiten Abschnitt der Test verwurschtelt. Da würde er bei pos=80 das Feld ja trotzdem erst setzen mit
"lösung[pos] = a".
Danach prüft er dann, ob er auf der 80 gelandet ist und nur dort wird das Feld wieder zurückgesetzt, wenn es nicht passt. Schwer zu durchblicken, wie das konkret abläuft. Ich denke nicht, dass es funktionieren kann.

Es ist doch gar kein Problem, wenn Du "solve(81)" ganz normal über die Rekursion aufrufst. Du prüfst das am Anfang und gehst dann einen Schritt zurück. Das ist doch gerade das Schöne an der Rekursion.
Wenn "solve(81)" aufgerufen wird, dann muss "solve(80)" erfolgreich durchgelaufen sein. Also hast Du im letzten Feld (index 80) auch eine legale Ziffer stehen. Damit ist das Sudoku gelöst. 
Hättest Du dort keine legale Belegung gefunden, dann wärst Du auf "solve(79)" zurückgesprungen und hättest "solve(81)" nicht erreicht.
Der zusätzlich Test bei "solve(81)" ist nur "akademisch". 
Sobald die Funktion mit Index 81 aufgerufen wird, weißt Du, dass das Brett voll ist und gehst direkt einen Schritt zurück.
An der Stelle brauchst Du den Rückgabewert.
Du gibst "true" zurück, damit keine weiteren Ziffern ausprobiert werden und die Schleifen nur noch verlassen werden.
Du gibst "false" immer dann zurück, wenn ein Feld nicht belegt werden konnte und weitere Zahlen probiert werden müssen.
Tust Du das nicht, dann musst Du das Ende irgendwie mit einer Exception oder anderen hässlichen Dingen abwürgen.
(Dann kannst Du auch gleich auf die Rekursion verzichten)

Der Reihe nach, solltest Du
a) Index auf 81 prüfen und damit das erfolgreiche Ende der Suche erkennen. Dementsprechend dann mit "true" zurückspringen.

b) Feld[pos] == 0 prüfen und dementsprechend "solve(pos+1)" direkt aufrufen, wenn das Feld schon belegt ist.
(auch hier kann die 81 aufgerufen werden, wenn das letzte Feld schon in der Aufgabenstellung belegt war)

c) Jetzt erst in die Probierschleife gehen. Ziffern durchtesten, bis Du eine Legale findest. Dann wieder "solve(pos+1)" aufrufen.
Kommt dieser Aufruf mit "false" zurück, dann war der Weg falsch. Also suchst Du die nächste legale Zahl. Sind keine mehr übrig, verlässt Du die Probierschleife, setzt das Feld wieder auf "0" und gibst ebenfalls "false" zurück.


----------

