magisches Quadrat - Rekursion - Backtracking

dubidu

Mitglied
Hi - vielleicht kann mir wer helfen:
ich habe folgende aufgabe bekommen:

Ein magisches Quadrat ist eine n × n-Matrix, n  1, deren Felder
mit den natürlichen Zahlen 1, . . . , n2 gefüllt sind, sodass die Summe der Zahlen in jeder
Zeile, Spalte und Diagonale den gleichen Wert besitzen. Jede Zahl i, 1  i  n2, muss
genau einmal vorkommen.

Beispiel für n = 3:
4 9 2
3 5 7
8 1 6

Beispiel für n = 5:
3 16 9 22 15
20 8 21 14 2
7 25 13 1 19
24 12 5 18 6
11 4 17 10 23

In der Vorlesung und der Übung wurden Backtracking-Algorithmen (8-Damen-Problem,
Sudoku-Rätsel) als Beispiele für rekursive Verfahren detailliert behandelt.
Ihre Aufgabe ist es, einen Backtracking-Algorithmus zu implementieren, der als Parameter
eine Zahl n erhält und ein magisches Quadrat der Größe n × n erzeugt
und auf dem Bildschirm ausgibt. Der Dialog soll folgendermaßen ablaufen:
Bitte geben Sie eine Zahl ein: 5
3 16 9 22 15
20 8 21 14 2
7 25 13 1 19
24 12 5 18 6
11 4 17 10 23
Testen Sie Ihr Programm mit Werten n < 4



Meine Lösung wäre folgende - für n=3 funktioniert das auch wunderbar aber ab 4 dauert es ewig
darf das sein?

ist das programm überhaupt rekursiv usw?

wäre echt nett wenn sich das jemand anschauen und verbessern bzwmir verbesserungsvorschläge geben kann

Java:
import java.util.Scanner;
 
public class MagicSquare {
// Anfang Attribute
private int[][] square;
private int n;
 
 
// Ende Attribute
/**
* Konstruktor für ein magisches Quadrat der Groesse n
* @param n Groesse des magischen Quadrats
*/
public MagicSquare(int n) {
this.n = n;
square = new int[n][n];
createMagicSquare(1);
}
/**
* Gibt das Quadrat auf der Console aus.
*/
public void print() {
for (int y = 0; y < n; y++) {
for (int x = 0; x < n; x++) {
System.out.print(""+square[x][y]+"\t");
}
System.out.println("");
}
System.exit();
}
/**
* Prueft, ob das Quadrat magisch gefuellt ist.
* @return true falls das Quadrat magisch gefuellt ist, andernfalls false
*/
public boolean isMagicSquare() {
int x,y;
int sollwert, summe;
boolean result= true;
sollwert= (n * (n*n+1)) / 2; // Summe, die jede Zeile erhalten muss
for (x= 0; x < n; x++){
// Spalten testen
summe= 0;
for (y= 0; y < n; y++) summe= summe + square[x][y];
result= result && (summe == sollwert);
}
for (y= 0; y < n; y++){
// Zeilen testen
summe= 0;
for (x= 0; x < n; x++) summe= summe + square[x][y];
result= result && (summe == sollwert);
}
summe= 0;
// Abwärts-Diagonale testen
for (x= 0; x < n; x++) summe= summe + square[x][x];
result= result && (summe == sollwert);
summe= 0;
// Aufwärts-Diagonale testen
for (x= 0; x < n; x++) summe= summe + square[x][n-x-1];
result= result && (summe == sollwert);
return result;
}
/**
* Fuellt das Quadrat magisch
* @param digit gibt an, welche Zahl gerade eingetragen wird.
*/
public void createMagicSquare(int digit) {
int x,y;
if ((digit > n*n) && isMagicSquare())
print();
else {
for (x = 0; x < n; x++) {
for (y = 0; y < n; y++) {
if (square[x][y] == 0) {
square[x][y] = digit;
createMagicSquare(digit + 1);
square[x][y] = 0;
}
}
}
}
}
 
 
 
  public static void main (String[] args) {
  Scanner sc = new Scanner(System.in);
 
        
System.out.println("Bitte gib eine Zahl n ein:");
int n = sc.nextInt();
 
MagicSquare mag = new MagicSquare(n); 
mag.print();
 
}
}
 
J

JenJen

Gast
ich hab dein programm mal getest und festgestellt, dass nicht nur eine nxn matrix ausgegeben wird sondern alle möglichkeiten mit denen man aus 3 zahlen von 1-9 eine summe 15 erreicht, was dann auch erklären würde warum das bei der 4 so lange dauert. Ob das rekursiv ist oder nicht, kann ich dir leider nicht sagen...
Ich weiß nicht ob dir das jetzt noch hilft, zumal ich mal davon ausgehe, dass du das heute um 00 uhr abgeben musst, wenn auch ander TU studierst, aber du müsstest in das programm noch eine permutation einfügen um alle zahlen nur einmal zu benutzen, dann müssten da eig auch nur 3 zeilen bei rauskommen, zumindest in meiner theorie..
die permutation die ich genommen hätte wäre:

private static boolean isPermutationBlock(int[][] square, int bottom, int top, int left, int right) {
int numElements = (top-bottom)*(right-left),
index = 0;
int[] temp = new int[numElements];
for (int r = bottom; r < top; r++)
for (int c = left; c < right; c++)
temp[index++] = square[r][c];
return isPermutation(temp);
}

von dem sudoku beispiel, allerdings funktioniert das bei mir noch nicht so wie es eig sollte...
naja hoffe es hat dir trotzdem weiter geholfen ;D
 

Neue Themen


Oben