Hey Leute,
ich habe folgendes 'Progrämmchen' erstellt, das mir im Backtracking-Verfahren ein Magisches Quadrat der Größe n*n liefert. Es gibt mir auch für n=3 die magischen Quadrate aus, bei n=4 kommt jedoch auch nach ca. 12 Stunden Laufzeit keine Ausgabe zustande. Wisst ihr vielleicht weiter und könnt mir sagen woran es evtl. liegen kann? Hier das Programm:
Hoffe ihr könnt mir da weiterhelfen.
Danke im vorraus..
Gruß,
shock
ich habe folgendes 'Progrämmchen' erstellt, das mir im Backtracking-Verfahren ein Magisches Quadrat der Größe n*n liefert. Es gibt mir auch für n=3 die magischen Quadrate aus, bei n=4 kommt jedoch auch nach ca. 12 Stunden Laufzeit keine Ausgabe zustande. Wisst ihr vielleicht weiter und könnt mir sagen woran es evtl. liegen kann? Hier das Programm:
Java:
/**
*
* Das Programm berechnet eine 2-Dimensionale Matrix der Groesse n*n unter Beachtung, dass es sich um ein magisches Quadrat handelt
*
*/
import java.util.Scanner;
public class Quadrat {
int n;
int hoechsteZahl=n*n;
Quadrat(int n, int hoechsteZahl) {
this.n=n;
this.hoechsteZahl=n*n;
}
/**
* Guckt ob das Quadrat magisch ist
* @param magischZahl,
* berechnet die Magische Zahl eines Quadrats
* @param diag_links,
* beschreibt die Summe aller Zahlen der linken Diagonale im Quadrat [Start: Feld 1, Ende: Feld n*n]
* @param diag_rechts,
* beschreibt die Summe aller Zahlen der rechten Diagonale im Quadrat [Start: Feld n, Ende: Feld (n*2+1 | bei n=3) ; Feld (n*3+1) | bei n=4) ...
* @param zeile,
* beschreit die Summe aller Zahlen der jeweils betrachteten Zeile
* @param spalte,
* beschreibt die Summe aller Zahlen der jeweils betrachteten Spalte
* @return true | false
*/
public boolean istMagisch(int quad[][]) {
int magischZahl=(((n*n*n)+n)/2);
int diag_links=0;
int diag_rechts=0;
for (int i=0; i<quad.length; i++) {
int zeile=0;
int spalte=0;
for (int j=0; j<quad[i].length; j++) {
if (quad[i][j]==0) {
return false;
}
zeile += quad[i][j];
spalte += quad[j][i];
}
if (zeile!=magischZahl || spalte!=magischZahl)
return false;
diag_links += quad[i][i];
diag_rechts += quad[(n-1)-i][i];
}
if (diag_links!=magischZahl || diag_rechts!=magischZahl)
return false;
return true; // keine Fehler gefunden -> true wird ausgegeben -> Magisches Quadrat
}
/**
* Dient dem Fuellen eines bestimmten Feldes mit einem passenden Wert, sodass das Quadrat magisch ist
*
* @param: nummer,
* zaehlt alle Felder von Links nach Rechts und von Oben nach Unten
*/
public void setzen(int nummer, int feld, int quad[][]) {
quad[feld/quad.length][feld%quad.length]=nummer;
}
/**
* Dient dem Entfernen des jeweiligen Feldes, falls es noetig ist, es zu loeschen, falls es sich um KEIN magisches Quadraft handelt
*
* quad an der Stelle quad[][] wird gleich 0 gesetzt -> also geloescht
*
*
*/
public void entfernen(int feld, int quad[][]) {
quad[feld/quad.length][feld%quad.length]=0;
}
/**
* Dient der Ausgabe der gefuellten 2-Dimensionalen Matrix
*
* @param i,
* dient der Ausgabe der Zeilen
* @param j,
* dient der Ausgabe der Spalten
*/
public void ausgabe(int quad[][]) {
for (int i=0; i<quad.length; i++) {
for (int j=0; j<quad[i].length; j++) {
System.out.print(quad[i][j]+" ");
}
System.out.println();
}
System.out.println();
}
/**
* Erstellt ein Array mit allen Zahlen, die noch nicht in das Quadrat eingesetzt wurden
*
* @param hoechsteZahl,
* beschreibt die hoechste, moegliche Zahl mit der die 2-Dimensionale Matrix gefuellt werden kann (n*n)
*
* @param erstesLeeresFeld,
* sucht das erste leere Feld in der erzeugten 2-Dimensionalen Matrix, welches noch nicht befuellt wurde, also keinen Wert enthaelt
*/
public int[] unbenutzt(int quad[][]) {
boolean[] gefuellt = new boolean[hoechsteZahl+1];
int erstesLeeresFeld = hoechsteZahl;
for (int i=0; i<quad.length; i++) {
for (int j=0; j<quad[i].length; j++) {
if (quad[i][j]!=0) {
gefuellt[ quad[i][j] ]=true;
erstesLeeresFeld--;
}
}
}
/**
* Erstellt ein Array mit den Zahlen, die
*
* @param result_i,
* wenn gefüllt nicht true ist, wird i der Wert der Zahl
* ahl an der Stelle result_i++ aus dem Array result zugewiesen
* @param result,
* erstellt ein Array mit den Zahlen von 1-erstesLeeresFeld
* @return result (Array)
*/
int[] result=new int[erstesLeeresFeld];
int result_i=0;
for (int i=1; i<gefuellt.length; i++) {
if (!gefuellt[i])
result[ result_i++ ]=i;
}
return result;
}
/**
* Fuellt die 2-Dimensionale Matrix magquad mit den Werten von 1 - n*n
* -- Zusaetzlich wird die Methode berechnen() aufgerufen um zu gucken ob es sich um ein magisches Quadrat handelt, damit es ausgegeben werden kann
*/
public void berechnen() {
int[][] magquad=new int[this.n][this.n];
pruefen(0, magquad);
}
/**
* Besitzt das erste leere Feld im Quadrat den Wert der hoechsten, moeglichen Zahl (n*n), wird geguckt ob es sich um ein Magisches Quadrat handelt
* -> Falls die IF-Abfrage erfolgreich ist, dann wird das jeweilige magische Quadrat ausgegeben
*/
public void pruefen(int erstesLeeresFeld, int magquad[][]) {
if (erstesLeeresFeld==hoechsteZahl) {
if (istMagisch(magquad)) {
System.out.println("Magisches Quadrat der Größe "+n+"*"+n+": ");
ausgabe(magquad);
}
} else {
int[] nummern =unbenutzt(magquad);
for (int i=0; i<nummern.length; i++) {
setzen(nummern[i], erstesLeeresFeld, magquad);
pruefen(erstesLeeresFeld+1, magquad);
entfernen(erstesLeeresFeld, magquad);
}
}
}
/**
* Main-Methode: Eingabe von n, Aufruf: magisches Quadrat der Groesse n*n zu berechnen
*
* @param n,
* wird durch den Benutzer eingegeben, beschreibt Groesse des Quadrats (n*n)
*/
public static void main(String args[]) {
System.out.print("Bitte geben Sie die Größe des Quadrats an: ");
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
Quadrat quad = new Quadrat(n);
quad.berechnen();
}
}Hoffe ihr könnt mir da weiterhelfen.
Danke im vorraus..
Gruß,
shock
Zuletzt bearbeitet:
