Hallo allerseits,
1)
Ein magisches Quadrat ist eine nxn Matrix, die aus lauter _verschiedenen_ , ganzen Zahlen 1, 2, .., n
besteht und deren Reihensummen (d.h. Zeilen, Spalten,. Diagonalen) gleich sind.
Beispiel (n=3):
2 7 6
9 5 1
4 3 8
2)
Ich habe dazu ein Programm rekursives geschrieben (siehe unten)
Es funktioniert auch.
Nur braucht es (für n=3) auf meinem ca. 10 Jahr alten Rechner
(AMD 1,80 Ghz, 768 MB RAM) ca. 5 Minuten.
Deswegen getraue ich mich nicht, es auf n=4 zu erweitern.
3)
Ich will keine weiteren - die man mathematisch beweisen kann - Informationen benutzen
[z.B. könnte man eine Formel für die Reihensumme benutzen: ich glaube (n*(n*n+1))/2)],
um das Problem zu vereinfachen.
4)
Fragen:
a) Warum ist das Laufzeitverhalten so schlecht (liegt es am Rechner oder an meinem Algorithmus)?
b) Wie kann man es optimieren?
nfg
Ernst
1)
Ein magisches Quadrat ist eine nxn Matrix, die aus lauter _verschiedenen_ , ganzen Zahlen 1, 2, .., n
besteht und deren Reihensummen (d.h. Zeilen, Spalten,. Diagonalen) gleich sind.
Beispiel (n=3):
2 7 6
9 5 1
4 3 8
2)
Ich habe dazu ein Programm rekursives geschrieben (siehe unten)
Es funktioniert auch.
Nur braucht es (für n=3) auf meinem ca. 10 Jahr alten Rechner
(AMD 1,80 Ghz, 768 MB RAM) ca. 5 Minuten.
Deswegen getraue ich mich nicht, es auf n=4 zu erweitern.
3)
Ich will keine weiteren - die man mathematisch beweisen kann - Informationen benutzen
[z.B. könnte man eine Formel für die Reihensumme benutzen: ich glaube (n*(n*n+1))/2)],
um das Problem zu vereinfachen.
4)
Fragen:
a) Warum ist das Laufzeitverhalten so schlecht (liegt es am Rechner oder an meinem Algorithmus)?
b) Wie kann man es optimieren?
nfg
Ernst
Java:
package magischesquadrat2;
import java.util.*;
import java.util.Date;
public class MainMagischesQuadrat2 {
public static void main(String[] args) {
int b;
Feld feld=new Feld();
Feld ergebnisFeld=new Feld();
long start, stop, dauer;
// Wert in Millisekunden
start = new Date().getTime();
b=feld.N(ergebnisFeld);
ergebnisFeld.printFeld();
// Wert in Millisekunden
stop = new Date().getTime();
// Wert in Sekunden
dauer = (stop -start)/1000;
System.out.println("Laufzeit des Programms="+dauer+" Sekunden");
}
}
class Feld {
public int feld[];
public Feld() {
feld = new int[9];
}
public void set(int stelle, int wert) {
feld[stelle] = wert;
}
public int get(int stelle) {
return feld[stelle];
}
public void kopieren(Feld pFeld){
for(int i=0;i<9;i++){
this.set(i,pFeld.get(i));
}
}
public void kopieren(int z){
for(int i=0;i<9;i++){
feld[i]=z;
}
}
/*
prueft, ob jede Zelle des Feldes mit einer ganzen Zahl zwischen
0 und 9 belegt ist.
*/
public boolean istVollbelegt(){
int zaehler=0;
int i;
boolean back;
for (i = 0; i < 9; i++) {
if (feld[i] != 0) {
zaehler++;
}
}
if(zaehler==9){
back=true;
}
else{
back=false;
}
return back;
}
/**
prueft nach, ob ein Feld magisch ist, d.h. voll belegt
und alle Zeilen, Spalten und Diagonalensummen gleich sind.
*/
public boolean istMagisch(){
int zaehler=0;
int i;
boolean back;
boolean b;
b=istSummenKorrekt();
if(b==true){
for (i = 0; i < 9; i++) {
if (feld[i]!= 0) {
zaehler++;
}
}
}
if(zaehler==9){
back=true;
}
else{
back=false;
}
return back;
}
/*
prueft, ob die Zeilen, Spalten und Diagonalensummen aller
Reihen, die keine unbelegten Zellen enthalten, gleich sind.
*/
public boolean istSummenKorrekt(){
int i;
int[] temp = new int[9];
int len=0;
boolean korrekt = true;
if(feld[0]!=0 && feld[1]!=0 && feld[2]!=0){
temp[len]=feld[0]+feld[1]+feld[2];
len++;
}
if(feld[3]!=0 && feld[4]!=0 && feld[5]!=0){
temp[len]=feld[3]+feld[4]+feld[5];
len++;
}
if(feld[6]!=0 && feld[7]!=0 && feld[8]!=0){
temp[len]=feld[6]+feld[7]+feld[8];
len++;
}
if(feld[0]!=0 && feld[3]!=0 && feld[6]!=0){
temp[len]=feld[0]+feld[3]+feld[6];
len++;
}
if(feld[1]!=0 && feld[4]!=0 && feld[7]!=0){
temp[len]=feld[1]+feld[4]+feld[7];
len++;
}
if(feld[2]!=0 && feld[5]!=0 && feld[8]!=0){
temp[len]=feld[2]+feld[5]+feld[8];
len++;
}
if(feld[0]!=0 && feld[4]!=0 && feld[8]!=0){
temp[len]=feld[0]+feld[4]+feld[8];
len++;
}
if(feld[2]!=0 && feld[4]!=0 && feld[6]!=0){
temp[len]=feld[2]+feld[4]+feld[6];
len++;
}
// Testen ob alle Summen gleich sind
if(len==0){
korrekt=true;
}
else{
for(i=0;i<len;i++){
if(temp[0]!=temp[i]){
korrekt=false;
break;
}
}
}
return korrekt;
}
/**
prueft, ob ein Feld vollbelegt ist, oder mindestens zwei Reihen
(d.h. Zeilen, Spalten, Diagonalen) drin sind, deren Reihensumme
verschieden ist.
*/
public boolean istEndfeld(){
boolean back=false;
if(this.istVollbelegt()){
back=true;
}
else{
if(this.istSummenKorrekt()==false)
back=true;
}
return back;
}
/*
Die Berechnung des Erloeses bei einem Endfeld, d.h. ob es magisch ist
*/
public int S(){
int back=1;
if(this.istEndfeld()){
if(this.istMagisch()){
back=1;
}
else{
back=-1;
}
}
else{
if(this.istSummenKorrekt()==false)
back=-1;
}
return back;
}
/*
Belegt ein vorhandenes Feld an einer bestimmten Stelle mit
einer Zahl
*/
public Feld berechneNext(int pStelle, int pZahl) {
Feld feldneu = new Feld();
// altes Feld in das neue kopieren
for(int i=0;i<9;i++)
feldneu.set(i, this.get(i));
feldneu.set(pStelle, pZahl);
return feldneu;
}
/**
prueft, ob ein Feld (das z.B. aus lauter Nullen besteht)
magisch ergänzt werden kann.
Beispiele:
1)
0 0 0
0 0 0
0 0 0
dieses Feld kann magisch ergaenzt werden z.B. zu:
2 7 6
9 5 1
4 3 8
2)
1 2 3
4 5 0
6 0 0
dieses Feld kann nicht magisch ergaenzt werden,
da zwei Reihensummen schon verschieden sind.
Es ist ein Endfeld.
*/
public int N(Feld ergebnisFeld){
int pos;
int value;
boolean erg;
int b;
int back=-1;
Feld feldneu = new Feld();
Feld temp = new Feld();
// Feld ist vollbelegt
if(this.istEndfeld()){
back = this.S();
if(this.istMagisch()){
ergebnisFeld.kopieren(this);
}
else{ // ist vollbelegt aber nicht magisch
ergebnisFeld.kopieren(-1);
}
}
// Feld hat Nachfolger
else{
for(pos=0; pos<9; pos++){
for(value=1; value<10; value++){
erg=sindZahlenkorrekt(pos, value);
// Neuer Nachfolger
if(erg==true){
feldneu=berechneNext(pos, value);
b=feldneu.N(temp);
if(b==1){
back=1;
ergebnisFeld.kopieren(temp);
// Vorgänger ist magisch ergänzbar
return back;
}
}
}
}
ergebnisFeld.kopieren(-1);
back=-1;
}
return(back);
}
/*
prueft, ob das Feld am Feldindex pos mit der Wert value
belegt werden kann. Dies geht z.B. nicht, wenn dort schon eine
ganze Zahl zwischen 1 und 9 steht, oder dadurch das Feld
2 gleiche Zahlen hat.
*/
boolean sindZahlenkorrekt(int pos, int value){
boolean back=true;
int i;
if(feld[pos]!=0){
back=false;
}
else{
for(i=0;i<9;i++){
if(feld[i]==value){
back=false;
break;
}
}
}
return back;
}
// Ausgabe auf Bildschirm
public void printFeld(){
for(int k=0;k<9;k++){
if(k%3==0)
System.out.println();
System.out.print(" "+feld[k]);
}
System.out.println();
}
}
