9x9 Matrix auf alle möglichen Lösungen prüfen?

wSam

Erfahrenes Mitglied
Hallo zusammen


Wie würdet ihr eine 9x9 Matrix mit Inhalt 1-9 in jedem Feld auf alle möglichen Lösungen prüfen?

Mein Ansatz war: bem letzten Feld anfangen hochzuzählen, wenn 9 erreicht ist, das Feld davor um 1 erhöhen, danach hinten wieder von 1-9 hochzählen. Jedoch crasht das Programmm schon bei der untersten Linie an einem StackOverflowError.

Irgend jemand eine Idee?
 
>Wie würdet ihr eine 9x9 Matrix mit Inhalt 1-9 in jedem Feld auf alle möglichen Lösungen prüfen?

Was für Lösungen

>Mein Ansatz war: bem letzten Feld anfangen hochzuzählen, wenn 9 erreicht ist, das Feld davor um 1 erhöhen, danach hinten wieder von 1-9 hochzählen. Jedoch crasht das Programmm schon bei der untersten Linie an einem StackOverflowError.

Klingt eigentlich nach einer Endlosschleife. :confused:
 
Hallo!

Mit allen "moeglichen Loesungen" meinst du wohl alle moeglichen Kombinationen von Werten.

Sollen sollen die Kombination nur auf eine Zeile beschraenkt oder auf die ganze Matrix bezogen sein?

Wie du eine Permutation erzeugen kannst findest du hier:
Code:
 /**
   * 
   */
  package de.tutorials;
  
  /**
   * @author tom
   * 
   */
  public class PermutationExample {
  
  	/**
  	 * @param args
  	 */
  	public static void main(String[] args) {
  		String str = "123456789";
  		Permutation permutation = new Permutation(str.toCharArray());
  		permutation.calculatePermutation();
  		System.out.println(permutation.getPermutationCount());
  	}
  
  	static public class Permutation {
  
  		long permutationCount;
  
  		char[] chars;
  
  		int endIndex;
  
  		public Permutation(char[] chars) {
  			this.chars = chars;
  			this.endIndex = chars.length - 1;
  		}
  
  		private void swap(char[] array, int i, int j) {
  			char temp = array[i];
  			array[i] = array[j];
  			array[j] = temp;
  		}
  
  		public void calculatePermutation() {
  			permut(this.chars, this.endIndex);
  		}
  
  		private void permut(final char[] chars, final int endIndex) {
  			if (endIndex == 0) {
  				print(chars);
  				permutationCount++;
  			} else {
  				permut(chars, endIndex - 1);
  			    for (int i = 0; i <= endIndex - 1; i++) {
  				    swap(chars, i, endIndex);
 				 permut(chars, endIndex - 1);
  				    swap(chars, i, endIndex);
  				}
  			}
  		}
  
  		private void print(char[] chars) {
  			System.out.println(String.valueOf(chars));
  		}
  
  		public long getPermutationCount() {
  			return permutationCount;
  		}
  	}
  }

Gruss Tom
 
Hi.
wSam hat gesagt.:
Wie würdet ihr eine 9x9 Matrix mit Inhalt 1-9 in jedem Feld auf alle möglichen Lösungen prüfen?
Ich glaub das würd ich einfach lassen. So wie ich dich verstanden habe, hast du ja eine 9x9 Matrix, also 81 "Felder" und diese sollen Werte von 1-9 annehmen, ja?!

Das macht dann also 9 ^ 81 mögliche Matrizenbelegungen, d.h. 196627050475552913618075908526912116283103450944214766927315415537966391196809 mögliche Belegungen.

Wenn du nicht gerade einen Supercomputer zur Verfügung hast, dauert das wirklich ewig.

Gruß
 
Ja genau 9x9 Felder mit 9 Möglichkeiten. Die Kombinationen sollen auf alle Felder ausgeweitet sein. Hmm okay war wohl eine schlechte Idee mit alle durchtesten.

Es soll darum en Sudoku Lösungsprogramm werden...

Und da habe ich auf Wikipedia gelesen dass man das mit einer Brute Force Methode (genauer Backtracking -> weiss nur nicht wie die das meinen) in maximal 1 Minute schaffen kann. -> siehe Link.

Wie würdet Ihr dass denn machen? Es sollte jedoch nicht zu kompliziert werden.

Vielen Dank für die Hilfe
 
Brute Force ist sicherlich ein Ansatz, aber ohne Anpassung sicherlich nicht in einer Minute zu packen.Wenn ich richtig liege (wir habens auf der Uni durchgemacht, ist aber schon eine Weile her ... ) würdest du mittels BruteForce jede einzelne Möglichkeit durchspielen, dann kommst du genau zu der Spanne an Durchläufen die Deep schon aufgezeichnet hat.

Es gibt aber sicher Situationen, ich bin kein Sudokuspieler muss ich zugeben, die einen eindeutigen Hinweis darauf geben, dass weitere Untersuchungen nicht mehr notwendig sind. Wenn z.B. in einer Zeile oder Spalte die Ziffer schon einmal vorgekommen ist, dann brauchst du die restlichen Spalten gar nicht mehr durchsuchen, da die Antwort sowieso schon gegeben ist (die Zahl darf ja nur einmal in jeder Spalte bzw. Zeile vorkommen, wenn ich richtig bin ... :p ).

Bin mir nicht sicher, ob das geholfen hat, aber ist vielleicht ein Anfang ...

Gruß
TOM
 
@TommyMo

Ja, dies habe ich schon befürchtet, dass ich es so lösen muss. Ja, ich werde mal schauen ob dies in einem vertretbaren Aufwand machbar ist. Danke trotzdem.

Aber verkürzt dass die Rechenzeit so extrem? Ich könnte immer überprüfen ob eine Linie, Zeile und Gruppe die Zahl schon hat, wenn nicht, kann ich sie setzten. Jedoch müsste dies zweigleisig sein, denn wenn ich die Zahl, sagen wir 2 in Feld mit Koordinaten 1/1 setzte, wäre ja die Nummer 2 im Feld 1/2 schon nicht mehr möglich.
 
Vielleicht solltest du zu jedem Feld parallel speichern, welche Möglichkeiten überhaupt noch bestehen.. Dadurch wird schon von Anfang an, die Zahl relativ stark eingeschränkt. Zuerst sollte reichen, zu überprüfen ob eine Zahl in einem 9er Quadrat schon vorhanden ist und ob eine Zahl schon in den Quer- bzw. Längsreihen zu einem best. Feld vorh. ist. Jedesmal wenn eine Zahl gefunden wird, wird die Anzahl der Möglichkeiten für alle Felder aktualisiert. Diese Aktualisierung dürfte recht schnell gehen ..
 
Zurück