Algorithmus um Schachbrett zu füllen
Hallo Ihr,
ich habe gestern folgende Aufgabe gefunden und komme nicht weiter. Vielleicht hat ja jemand von euch eine Idee. Es geht um die Folgende Aufgabe:
[Link nur für registrierte und freigeschaltete Mitglieder sichtbar. Jetzt registrieren...]
Mit einem Schachbrett der Größe 2 Funktioniert mein Algorithmus bereits. Bei einem Schachbrett der Größe 3 habe ich das Problem, dass ich zuwenig Möglichkeiten berechne (Da die Abstände zwischen den Figuren auch größer 1 sein können).
Folgendes ist mein bisheriger Quelltext (in c#). Vielleicht habt ihr ja noch einige Ideen:
Code:
class Program
{
static List<string> uniqueSignatures = new List<string>();
static void Main(string[] args)
{
int n = 2;
int spielfelder = n * n;
for (int i = 0; i < spielfelder; i++)
{
// für jedes Spielfeld alle möglichkeiten berechnen
int row = i / n;
int feld = i % n;
calculateMoeglichkeiten(row, feld, n);
}
}
private static void calculateMoeglichkeiten(int row, int feld, int n)
{
int[,] spielfeld = new int[n, n];
spielfeld[row, feld] = 1;
if (!uniqueSignatures.Contains(createSignature(spielfeld, n)))
{
uniqueSignatures.Add(createSignature(spielfeld, n));
for (int y = 0; y < n; y++)
{
for (int x = 0; x < n; x++)
{
Console.Write(spielfeld[y, x]);
}
Console.Write("\r\n");
}
Console.WriteLine("------");
}
for (int r = row; r < n; r++)
{
for (int f = feld; f < n; f++)
{
if (f - 1 >= 0 && spielfeld[r, f - 1] != 1) // feld größer 0 und links davon ist nicht besetzt?
{
if (r > 0 && spielfeld[r - 1, f] != 1) // reihe > 0 und feld darunter ist nich besetzt
{
spielfeld[r, f] = 1;
if (!uniqueSignatures.Contains(createSignature(spielfeld, n)))
{
uniqueSignatures.Add(createSignature(spielfeld, n));
for (int y = 0; y < n; y++)
{
for (int x = 0; x < n; x++)
{
Console.Write(spielfeld[y, x]);
}
Console.Write("\r\n");
}
Console.WriteLine("------");
}
// feld besetzten
}
else if (r == 0) // reihe = 0 und feld links davon ist nicht besetzt
{
// feld besetzten
spielfeld[r, f] = 1;
if (!uniqueSignatures.Contains(createSignature(spielfeld, n)))
{
uniqueSignatures.Add(createSignature(spielfeld, n));
for (int y = 0; y < n; y++)
{
for (int x = 0; x < n; x++)
{
Console.Write(spielfeld[y, x]);
}
Console.Write("\r\n");
}
Console.WriteLine("------");
}
}
}
else if (r > 0 && f == 0 && spielfeld[r - 1, 0] != 1) // erstes feld der reihe r und darunter ist nicht besetzt
{
// feld besetzten
spielfeld[r, f] = 1;
if (!uniqueSignatures.Contains(createSignature(spielfeld, n)))
{
uniqueSignatures.Add(createSignature(spielfeld, n));
for (int y = 0; y < n; y++)
{
for (int x = 0; x < n; x++)
{
Console.Write(spielfeld[y, x]);
}
Console.Write("\r\n");
}
Console.WriteLine("------");
}
}
}
feld = 0;
}
if (!uniqueSignatures.Contains(createSignature(spielfeld, n)))
{
uniqueSignatures.Add(createSignature(spielfeld, n));
for (int y = 0; y < n; y++)
{
for (int x = 0; x < n; x++)
{
Console.Write(spielfeld[y, x]);
}
Console.Write("\r\n");
}
Console.WriteLine("------");
}
}
private static string createSignature(int[,] array, int n)
{
string signature = "";
for (int x = 0; x < n; x++)
{
for (int y = 0; y < n; y++)
{
signature += array[x, y].ToString();
}
}
return signature;
}
}
Edit:
Habe das Problem gelöst, mein Ansatz der Berechnung für die Möglichkeiten war der Falsche. |
