Schachbrett König von A1 bis H8, anz. Möglichkeiten

Screen

Bekanntes Mitglied
Hey, Ich überlege schon seit einer Ewigkeit wie man das Prolem lösen könnte.
Könnte ich eien Tipp haben ?



Aufgabe:
Gegeben sei ein Schachbrett mit einem König aufdem Feld A1. Nun ist die Frage, wieviele Möglichkeiten es gibt,
mit genau k Zügen den König auf das Feld H8 zu bewegen (naturlich nur mit korrekten Zügen).
Schreiben Sie ein Programm, um die Anzahl der Möglichkeiten zu berechnen.
Geben Sie die genaue Zahl für k = 10 sowie k = 13 an. Für k = 2^50 geben Sie die Lösung modulo 2^30 an.
Hinweis: Betrachten Sie die Adjazenzmatrix des Graphen, der durch die Zugmöglichkeiten des Königs de niert
wird.

Meine Fragen:
Wie ist das mit der Adjazenzmatrix gemeint?
Und wie könnte das System ausehen?

Ansätze:
Jedes überlegte System war gescheitert.
 
F

Firephoenix

Gast
Der König kann von einem Feld nur auf erlaubte Felder, das sind die Nachbarfelder (wenn ich mich mit Schach nicht toal irre ist das gerade und diagonal mit abstand = 1).

Du erstellst also eine Matrix trägst dort alle Felder eines Schachbretts aufeinander auf und trägst dort dann die Nachbarschaften ein:
Repräsentation von Graphen im Computer ? Wikipedia

und dann fängst du an dir darüber Gedanken zu machen wieviele Möglichkeiten es gibt in x zügen an einen bestimmten Ort zu kommen :)

Mit den Ansätzen kann man dann hier weitermachen.

Gruß
 

Marco13

Top Contributor
Das Schachbrett mit seinen Nachbarschaften an sich als Graphen darstellen dürfte ziemlich langweilig sein. Was da rauskommt ist nämlich ... ... *tadaaa* ein Schachbrett :D

Ich mußte bei der Aufgabenstellung an http://www.acsa-admin.org/2005/papers/87.pdf denken. Kannst's ja mal überfliegen und dich inspirieren lassen.

Ich wußte schon, dass du das sofort ausklappst :D

Die Adjazenzmatrix würde man nicht für das Schachbrett an sich aufstellen, sondern für die Erreichbarkeit von Feldern. Bei einem Schachbrett der Größe 3x3
Code:
  A B C
1 
2
3
Würde man eine Matrix aufstellen wie diese:
Code:
   A1 A2 A3 B1 B2 B3 C1 C2 C3
A1 
A2  1
A3  
B1  1
B2  1
B3
C1
C2
C3

Die erste Spalte ist schon ausgefüllt: Die besagt, VON welchem Feld (Spalte) man ZU welchem Feld (Zeile) ziehen kann: Von A1 kann man nach A2, B1 und B2. So kann man die übrigen Spalten auch noch füllen.

Wenn du dir das oben verlinkte Paper durchgelesen hast, weißt du, was du damit anfangen kannst.



Ich wußte schon, dass du das sofort ausklappst :D

Wenn du dir das oben verlinkte Paper durchgelesen (oder schonmal anderweitig drüber nachgedacht) hast, weißt du, dass man durch Multiplizieren zweier Adjazenzmatrizen Wege beschreiben kann. Wenn man so eine Matrix A hat, die besagt, welche Felder man mit einem Schritt erreichen kann, dann beschreibt die Matrix A*A eben, welche Felder man mit zwei Schritten erreichen kann. Und die Matrix A^n besagt, welche Felder man mit n Schritten erreichen kann. Praktischerweise sind die Einträge dieser Matrizen gleichzeitig die Anzahl der Wege, die es zwischen den jeweiligen Feldern gibt.


Java:
class Matrix
{
    private int n;
    private long a[][];
    
    public Matrix(int n)
    {
        this.n = n;
        a = new long[n][n];
    }
    
    public long get(int r, int c)
    {
        return a[r][c];
    }

    public void set(int r, int c, long v)
    {
        a[r][c] = v;
    }
    
    public Matrix mult(Matrix other)
    {
        Matrix result = new Matrix(n);
        for(int i = 0; i < n; i++) 
        {
            for(int j = 0; j < n; j++) 
            {
                for(int k = 0; k < n; k++)
                {
                    result.a[i][j] += a[i][k] * other.a[k][j];
                }
            }  
        }
        return result;
    }
    
    public String createString()
    {
        StringBuilder sb = new StringBuilder();
        for (int r=0; r<n; r++)
        {
            for (int c=0; c<n; c++)
            {
                sb.append(String.format("%12s", a[r][c]));
            }
            sb.append("\n");
        }
        return sb.toString();
    }
    
    
    
}

public class KingMoveCounter
{
    public static void main(String[] args)
    {
        int n = 8;
        
        Matrix m = new Matrix(n*n);
        
        for (int r0=0; r0<n; r0++)
        {
            for (int c0=0; c0<n; c0++)
            {
                for (int dr=-1; dr<=1; dr++)
                {
                    for (int dc=-1; dc<=1; dc++)
                    {
                        if (dr != 0 || dc != 0)
                        {
                            int r1 = r0+dr;
                            int c1 = c0+dc;
                            if (r1 >= 0 && r1 < n && c1 >= 0 && c1 < n)
                            {
                                int i0 = c0+r0*n;
                                int i1 = c1+r1*n;
                                m.set(i0, i1, 1);
                            }
                        }
                    }
                }
            }
        }
        
        int k=13;
        Matrix c = m;
        for (int i=1; i<=k; i++)
        {
            System.out.println("With "+i+" steps there are "+c.get(n*n-1, 0)+" paths");
            //System.out.println(c.createString());
            c = c.mult(m);
        }
    }
}


Und wenn man die ausgegebene Zahlenfolge mal in die The On-Line Encyclopedia of Integer Sequences eingibt, sieht man auch, dass das stimmt.

Für die Sache mit dem 2^50 muss man entweder laaange rechnen :D oder sich was geschicktes überlegen. Irgendwie läßt sich das modulo vielleicht mit der Matrix-Multiplikation verwursten, so dass da das meiste wegfällt .... andernfalls muss man mal schauen, ob man was mit BigInteger#modPow machen kann.
 

XHelp

Top Contributor
Für die Sache mit dem 2^50 muss man entweder laaange rechnen :D oder sich was geschicktes überlegen. Irgendwie läßt sich das modulo vielleicht mit der Matrix-Multiplikation verwursten, so dass da das meiste wegfällt
Jo, da könnte man ja sowas wie
Java:
for (int k = 0; k < n; k++) {
  result.a[i][j] += ((a[i][k] * other.a[k][j]) % mod);
}
result.a[i][j] = result.a[i][j] % mod;
machen, dann bleiben die Zahlen immer in dem gewünschten Bereich. Müsste eigentlich mathematisch stimmen.
Darüber hinaus muss man ja nicht immer *A rechnen. Wenn man z.B. A*A=B gerechnet hat, d.h. Ergebnis für 2 Züge, dann kann man direkt mit B*B=C Ergebnis für 4 Züge, C*C für 8 usw. Und in der Aufgabenstellung sind schon praktischer Weise 2er-Potenz angegeben, so dass man nach 50 Rechenoperationen das Ergebnis bekommt. Sowas wie:
Java:
Matrix c = m;
for (int i = 1; i <= 50; i++) {
  c = c.mult(c);
  System.out.println("With 2^" + i + " steps there are " + c.get(n * n - 1, 0) + " paths");
}
 

Marco13

Top Contributor
Jo, da könnte man ja sowas wie
Java:
for (int k = 0; k < n; k++) {
  result.a[i][j] += ((a[i][k] * other.a[k][j]) % mod);
}
result.a[i][j] = result.a[i][j] % mod;
machen, dann bleiben die Zahlen immer in dem gewünschten Bereich. Müsste eigentlich mathematisch stimmen.
Darüber hinaus muss man ja nicht immer *A rechnen. Wenn man z.B. A*A=B gerechnet hat, d.h. Ergebnis für 2 Züge, dann kann man direkt mit B*B=C Ergebnis für 4 Züge, C*C für 8 usw. Und in der Aufgabenstellung sind schon praktischer Weise 2er-Potenz angegeben, so dass man nach 50 Rechenoperationen das Ergebnis bekommt. Sowas wie:
Java:
Matrix c = m;
for (int i = 1; i <= 50; i++) {
  c = c.mult(c);
  System.out.println("With 2^" + i + " steps there are " + c.get(n * n - 1, 0) + " paths");
}


Ja, sicher würde man Exponentiation by squaring - Wikipedia, the free encyclopedia verwenden, aber BigInteger bräuchte man da dann trotzdem noch. Ob deine vorgeschlagene Verwendung von % stimmt, habe ich nicht nachvollzogen, aber sowas in der Art meinte ich, und es sieht plausibel aus (und dann würde es natürlich ohne BigInteger gehen)
 

Neue Themen


Oben