# Ein magisches Quadrat mit einfache C++Befehlen errechen. Wie?



## The-Flu (21. Juli 2006)

Moin, Moin,

bei meinen C++-ProgramierVersuchen kam mir die Idee doch ein Programm zu ausrechenen des magischen Quadrats zu schreiben. 

Also ein Array (A B C
		       D E F
		       G H I) bei dem überalle addiert 15 rauskommt.

Dabei habe ich drei Grundproblemstellungen:

1.) Die Bedingunsprüfung. 
Ich Dachte, dass man das gut mir einer IF-Abfrage machen könnte.
Also: IF (A+B+C = 15 AND D+E+F = 15 AND G+H+I = 15 A+D+G = 15 AND B+E+H = 15 AND C+F+I = 15 )
      THEN...
Ich denke das sollte so funktionieren.


2.) Die Änderung der Werte der Variablen.
Es müssen für alle Variablen (A,B,C,D,E,F,G,H,I) die Werte 1-9 durchprobiert werden. Ich dachte dabei an eine FOR-Schleife 

die jede Variable 9 Mal durchläuft. 
Als Beispiel müsste das dann so aussehen 

A B C = |1|1|1 |2|1|1 |1|2|1 |1|1|2 |2|2|1 |2|1|2 |1|2|2 |2|2|2...

Bloß wie soll ich die die Schleifen verschachteln das so ein Durcchprobiersysthem entsteht?


3.) Die Sinnvolle Ausgabe in ein Array.
Am ende muss das ganze noch vernünftig ausgegeben werden.

Wie gesagt habe ich noch nicht so vie Erfahrung in C++ und vielleicht gibt es ja noch eine Methode die für solche Logikrätsel 

besser geignet ist

Ich bin für alle Kritik und Verbesserungen offen.
Danke


----------



## Conducted (21. Juli 2006)

Also ich hab mit mit dem magischen Quadrat noch nicht beschäftigt, geb aber trotzdem mal meinen Senf dazu   

Wie du schon richtig erkannt hast, kann man das Durchlaufen aller Möglichkeiten durch 9 ineinandergeschachtelte for-Schleifen lösen. Würde dann ungefär so aussehen:



> for(a=1;a<=9;a++) {
> array[0] = a;
> for(b=1;b<=9;b++) {
> array[1] = b;
> ...




In der innersten Schleife würde ich dann die IF-Abfrage hinsetzen.
Das ganze ließe sich allerdings auch durch eine Rekursion lösen!

 Da ich jetzt nich weiß in welcher Sprache du vorher programmiert hast, noch ein paar Hinweise zu c++:

Array-Indizes in c++ beginnen bei 0, d.h. ein 4-Elementiges Array hat die Indizes 0,1,2,3.
Der Vergleichsoperator in C++ ist das "==" also z.B.

if (i == 3)
  printf("");

Ein THEN gibts in c++ nicht. 
Und a++ bedeutet nichts anderes a = a + 1.


----------



## The-Flu (21. Juli 2006)

> for(a=1;a<=9;a++) {
> array[0] = a;
> for(b=1;b<=9;b++) {
> array[1] = b;
> ...


----------



## struy (21. Juli 2006)

Siehe Wikipedia: Backtracking sollte deiner Idee entsprechen.


----------



## thehero (7. August 2006)

The-Flu am 21.07.2006 15:39 schrieb:
			
		

> Moin, Moin,
> 
> bei meinen C++-ProgramierVersuchen kam mir die Idee doch ein Programm zu ausrechenen des magischen Quadrats zu schreiben.
> 
> ...




Hi,

letzendlich besteht das Problem doch darin, alle möglichen Kombinationen von 1...9 in ein 3x3 Felder-Quadrat abzubilden. Um alle Kombinationen einer passenden Datenstruktur zu ermitteln, gibts in der STL entsprechende Funktionen. Ich würde es so machen:


#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

typedef vector<int> CIntVec;

static bool CheckMagic(
const CIntVec& v, 
const bool bCheckDiag, 
const int nMagic
)
{
	//assert(0 == v.size());

	if (v.size() != 9)
		return false;

	return v[0] + v[1] + v[2] == nMagic
		&& v[3] + v[4] + v[5] == nMagic
		&& v[6] + v[7] + v[8] == nMagic
		&& v[0] + v[3] + v[6] == nMagic
		&& v[1] + v[4] + v[7] == nMagic
		&& v[2] + v[5] + v[8] == nMagic
		&& (!bCheckDiag || (v[0] + v[4] + v[8] == nMagic
		&& v[2] + v[4] + v[6] == nMagic));
}

static void PrintMagic(const CIntVec& v)
{
	// 3 x 3
	if (9 == v.size()) {
		for (int nRow = 0; nRow < 3; ++nRow) {
			for (int nCol = 0; nCol < 3; ++nCol) {
				cout << v[nRow * 3 + nCol] << "  ";
				}
			cout << endl;	
			}
		cout << endl;
		}
}

int main(int argc, char* argv[])
{
	// Struktur für's Ergebnis
	vector<CIntVec> vResults;

	// 1...9 vorbelegen
	CIntVec vBase;
	for (int i = 1; i <= 9; ++i)
		vBase.push_back(i);

	bool bCheckDiagonale = true;

	// alle Kombinationen durchlaufen..
	do {
		// .. die "magischen" merken
		if (CheckMagic(vBase, bCheckDiagonale,                      15))		vResults.push_back(vBase);
		} while (next_permutation(vBase.begin(), vBase.end()));

	// Ergbnis(se) ausgeben
	cout << "Es wurden " << vResults.size() << " Möglichkeiten ermittelt:" << endl << endl;
	vector<CIntVec>::const_iterator it;
	for (it = vResults.begin(); it != vResults.end(); ++it)
		PrintMagic(*it);

	return 0;
}

Natürlich gehts noch eleganter und auch flexibler, z.B. hinsichtlich der Anzahl der Felder... 


Kann man den eigentlich noch ein bissl schön formatieren? Der Code sieht ja so recht gruslig aus...


----------

