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



## Screen (6. Jun 2012)

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.


----------



## Firephoenix (6. Jun 2012)

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 (6. Jun 2012)

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

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.



Spoiler: Ein Tipp zu der Sache mit der Adjazenzmatrix



Ich wußte schon, dass du das sofort ausklappst 

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 

```
A B C
1 
2
3
```
Würde man eine Matrix aufstellen wie diese:

```
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.





Spoiler: Keinen Bock das Paper zu lesen. Komm' zur Sache!



Ich wußte schon, dass du das sofort ausklappst 

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.




Spoiler: Ein Programm, das die Lösung ausrechnet (deine Hausaufgabe ... überleg's dir)





```
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  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 (7. Jun 2012)

Spoiler: Zitat gespoilert






Marco13 hat gesagt.:


> Für die Sache mit dem 2^50 muss man entweder laaange rechnen  oder sich was geschicktes überlegen. Irgendwie läßt sich das modulo vielleicht mit der Matrix-Multiplikation verwursten, so dass da das meiste wegfällt








Spoiler: Und hier die Antwort



Jo, da könnte man ja sowas wie

```
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:

```
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");
}
```


----------



## Jango (7. Jun 2012)

Firephoenix hat gesagt.:


> (wenn ich mich mit Schach nicht toal irre ist das gerade und diagonal mit abstand = 1)



Abstand ein Feld, aber nur zum König des Gegners.


----------



## Marco13 (7. Jun 2012)

XHelp hat gesagt.:


> Spoiler: Und hier die Antwort
> 
> 
> 
> ...




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)


----------

