de.hska.info1.klausur.ss07
Class MagischesQuadrat

java.lang.Object
  de.hska.info1.klausur.ss07.MagischesQuadrat

public class MagischesQuadrat
extends java.lang.Object

Lösungen für die Klausuraufgabe zum Magischen Quadrat.

Author:

pape

Constructor Summary

MagischesQuadrat(int[][] quadrat)

Method Summary

boolean	erzeugeMagischesQuadrat(int zelle) Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat.
boolean	erzeugeMagischesQuadrat1(int zelle) Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat.
boolean	erzeugeMagischesQuadrat2(int zelle) Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat.
boolean	erzeugeMagischesQuadratKlausur(int zelle) Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat.
boolean	isMagischesQuadrat() Gibt genau dann true zurück, wenn quadrat ein Magisches Quadrat ist.
void	print() Gibt dieses Magisches Quadrat formatiert auf der Console aus.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MagischesQuadrat

public MagischesQuadrat(int[][] quadrat)

Method Detail

isMagischesQuadrat

public boolean isMagischesQuadrat()

Gibt genau dann true zurück, wenn quadrat ein Magisches Quadrat ist.

erzeugeMagischesQuadratKlausur

public boolean erzeugeMagischesQuadratKlausur(int zelle)

Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat. Dies wäre die einfachste Lösung für die Klausur. Allerdings auch sehr langsam. Dauert bei n = 3 ein paar Sekunden. Dies liegt an zwei Dingen:

• isMagischesQuadrat() wird immer wieder berechnet mit O(n²) Aufwand im schlimmsten Fall
• Es werden Zahlen in eine Zelle gesetzt, obwohl sie schon im Quadrat vorhanden sind.

erzeugeMagischesQuadrat

public boolean erzeugeMagischesQuadrat(int zelle)

Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat. Anders als bei der vorangehenden Version, wird isMagischesQuadrat() nur noch berechnet, wenn wir alle Zellen "voll" haben, aber beim Schritt wird nicht überprüft, ob die Zahl schon mal verwendet wurde. Sie ist nur für 3 x 3 Quadrate praktikabel. Es dauert spürbar Sekundenbruchteile, ist aber ca. 5-10 schneller als obige Variante.

erzeugeMagischesQuadrat1

public boolean erzeugeMagischesQuadrat1(int zelle)

Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat. Es ist eine optimierte Version, die bei jedem Schritt prüft, ob die Zahl bereits verwendet wurde. Sie ist trotz dieser Optimierung nur für 3 x 3 Quadrate praktikabel, allerdings im geringen Millisekundenbereich.

erzeugeMagischesQuadrat2

public boolean erzeugeMagischesQuadrat2(int zelle)

Erzeugt mit einem Backtracking-Algorithmus ein neues Magisches Quadrat. Es ist eine optimierte Version, bei der:

• in jedem Schritt geprüft wird, ob die Zahl bereits verwendet wurde und
• ob die Summe einer neu erzeugten Zeile eine Mindestgrösse hat

Da der grösste Wert n * n - 1 auftreten muss und die nächst kleineren 1, 2, ... n - 1 sind, muss die Summe einer Spalte und Zeile mindestens 1 + 2 + ... + n - 1 + n*n - 1 = (n-1)n / 2 + n*n - 1 sein. Bei n = 3: 1 + 2 + 9 = 12. Bei n = 4: 1 + 2 + 3 + 16 = 22. Aber auch dies reicht nicht aus. Man kann allerdings zeigen, dass die Summe eines n x n Magischen Quadrats für n > 2 immer (n³ + n) / 2 sein muss. Dann funktioniert es auch mit n = 4. Bei grösseren n dauert es aber wieder zu lang. Backtracking ist zur Erzeugung Magischer Quadrate also eher ungeeignet.

print

public void print()

Gibt dieses Magisches Quadrat formatiert auf der Console aus.