#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

int groesse=0;
int** quadrat;
int aktuell[2]={0,0};
int maxbreite=0;
bool zwischen=false;

bool springe_rechts_oben();
bool springe_unten();
void print_quadrat();

void print_quadrat()
{
	if(maxbreite==0)
	{
		// Einmalig Maximale anzeigebreite berechnen:
		for(int i=1; i< 8;i++)
		{
			if(pow(groesse,2) < pow(10,i))
			{
				maxbreite = i;
				break;
			}
		}
	}
	
	for(int i=0;i< groesse;i++)
	{
		cout << "| ";
		for(int j=0;j < groesse;j++)
		{
			cout << setw(maxbreite) << quadrat[i][j] << " | ";
		}
		cout << endl;
	}
}


bool springe_rechts_oben()
{
	int neus=0, neuz=0;
	if(aktuell[0] == 0)
	{
		neuz = groesse-1;
	}
	else
	{
		neuz = aktuell[0] - 1;
	}
	
	if(aktuell[1] + 1 == groesse)
	{
		neus = 0;
	}
	else
	{
		neus = aktuell[1] + 1;
	}
	if(quadrat[neuz][neus] == 0)
	{
		aktuell[0] = neuz;
		aktuell[1] = neus;
		return(true);
	}
	else
	{
		return(false);
	}
}

bool springe_unten()
{
	int neuz=0;
	if(aktuell[0] +1 ==  groesse)
	{
		neuz = 0;
	}
	else
	{
		neuz = aktuell[0] + 1;
	}
	if(quadrat[neuz][aktuell[1]] == 0)
	{
		aktuell[0] = neuz;
		return(true);
	}
	else
	{
		return(false);
	}
}

int main()
{
	
	// Header
	cout << "Aufgabe 17: magische Quadrate\n";
	cout << "Bitte geben Sie die (ungerade) Anzahl der Zeilen / Spalten an: ";
	
	// Einlesen und verifizieren der Groesse
	cin >> groesse;
	if(!(groesse > 0) || groesse%2 != 1)
	{
		cerr << "Es wurde keine gueltige Groesse eingegeben!\n";
		return(1);
	}
	
	// Initialisieren des Feldes:
	quadrat = new int*[groesse];
	for(int i=0;i < groesse;i++) 
	{
		quadrat[i] = new int[groesse];
		for(int j=0;j< groesse;j++)
			quadrat[i][j] = 0;
	}
	
	// Eigentliches Erstellen des magischen Quadrats
	
	aktuell[1] = (groesse / 2);
	quadrat[aktuell[0]][aktuell[1]] = 1;
	
	if(zwischen)
	{
		cout << "Das aktuelle Zwischenergebnis im Schritt 1:\n";
		print_quadrat();
	}
	
	for(int i=2; i<= pow(groesse,2);i++)
	{
		if(springe_rechts_oben())
		{
			quadrat[aktuell[0]][aktuell[1]] = i;
		}
		else
		{
			if(springe_unten())
			{
				quadrat[aktuell[0]][aktuell[1]] = i;
			}
			else
			{
				cerr << "Ein Fehler ist beim Durchlauf aufgetreten!\n";
				exit(1);
			}
		}
		if(zwischen)
		{
			cout << "Das aktuelle Zwischenergebnis im Schritt "<< i <<":\n";
			print_quadrat();
		}
	}
	cout << "Das Ergebnis:\n";
	print_quadrat();
	return(0);
}