Combinatoria ricorsiva - scacchiera

[nlm_23457]

Buonasera a tutti,
è da un po' che provo a risolvere questo problema di combinatoria ma proprio non riesco a venirne a capo...
In pratica abbiamo una scacchiera 3x3 e viene richiesto di calcolare i possibili percorsi di 6 mosse che un re (del gioco degli scacchi), posizionato al centro di essa, può fare per ritornare al punto di partenza.
E' uno degli esercizi presenti in un corso di combinatoria ricorsiva. Mi sono venute alcune idee ma non sono mai riuscito a trovare la soluzione definitiva...
Ringrazio in anticipo chi mi aiuterà!


Scrivo anche la soluzione se dovesse servire:

3200

[ghira1]

"nlm_23457":
In pratica abbiamo una scacchiera 3x3 e viene richiesto di calcolare i possibili percorsi di 6 mosse che un re (del gioco degli scacchi), posizionato al centro di essa, può fare per ritornare al punto di partenza.

Potresti cominciare contando i modi per farlo in 2 mosse o 3 mosse, in quanto alcuni percorsi da 6 mosse sono 3 percorsi da 2 uno dopo l'altro o 2 percorsi da 3. O 2 poi 4 o 4 poi 2, dove i percorsi da 4 non sono del tipo "2 poi 2".

Ma visto che il corso era di combinatoria ricorsiva magari dovresti farlo ricorsivamente. Da ogni casella, in quanti modi puoi arrivare al centro in 0 mosse? 1 mossa? ecc.

[ghira1]

c per centro, a per angolo, l per lato

$ more recur-re.p

#!/usr/bin/perl

sub c {
        my $n=shift;
        if ($n==0) {
                return 1;
                } else {
                return 4*a($n-1)+4*l($n-1);
                }
        }

sub a {
        my $n=shift;
        if ($n==0) {
                return 0;
                } else {
                return 2*l($n-1)+c($n-1)
                }
        }

sub l {
        my $n=shift;
        if ($n==0) {
                return 0;
                } else {
                return 2*l($n-1)+2*a($n-1)+c($n-1);
                }
                }

print c(6)."\n";

$ perl recur-re.p
3200

[Bokonon]

@nlm_23457
L'ho risolto ma senza usare la ricorsività. Ci sono $13+29+8=50$ distinti tipi di percorsi che possono essere sviluppati in $4^3$ modi. $50*4^3=3200$.
Posso postare il ragionamento oppure darti un paio di indizi e ci arrivi da te. Fammi sapere!

[nlm_23457]

@Bokon
Se vuoi prova a darmi un suggerimento così provo a risolverlo. Grazie!

[Bokonon]

"nlm_23457":@Bokonon
Se vuoi prova a darmi un suggerimento così provo a risolverlo. Grazie!

Mi sa che dovrò darti la soluzione completa...capirai il perchè leggendola.

Prima di tutto stabiliamo una notazione semplice per i percorsi e come contarli...per poi passare a considerare 5 percorsi fondamentali.

Come sappiamo, il movimento del Re ci porta a considerare tre tipologie di case: quella centrale $C$, i 4 angoli $A$ e infine le 4 case "mediane" $M$.
Pertanto i salti possibili sono del tipo:
1) $C->A=C->M=4$
2) $A->C=M->C=1$
3) $A->M=M->A=M->M=2$
(Corollario: la regola 3) ci dice che non si può andare da $A->A$

Consideriamo uno specifico percorso possibile $MCAMMC$ e chiediamoci quanti sono i percorsi di questo tipo (giusto per imparare a contarli). $MCAMMC=C->M->C->A->M->M->C=4xx1xx4xx2xx2xx1=4^3$
Dato che tutti i percorsi finiscono con $C$, a livello di conteggio e di ragionamento possiamo semplificarli nella prima cinquina, pertanto d'ora in poi $MCAMMC=MCAMM$ (per la proprietà 2) )
Mentre (considerando solo i percorsi possibili) per la proprietà 3) , possiamo semplificare in $I=A=M$

Adesso che tutto è stato definito, il resto è davvero semplice: chiediamoci dove possono stare le $C$ in queste cinquine!
Per esempio uno dei percorsi generici è $ICIII$ (che è la generalizzazione del percorso precedente).
Sappiamo già che $ICIII=4xx1xx4xx2xx2xx1=4^3$
Un altro percorso generico è $IIIII=4xx2xx2xx2xx2xx1=4^3$
Gli altri 3 sono ovviamente $ICICI=4^3$, $IICII=4^3$ e infine $IIICI=4^3$
Riassumendo, ci sono 5 percorsi generici fondamentali che hanno la medesima molteplicità $4^3$
Questo è vero per ogni singolo percorso possibile a partire da un generico.
Quindi rimane la parte tediosa del metodo, ovvero, partendo da ogni percorso generico, calcolarne i percorsi possibili (per via del corollario).

Per esempio $ICICI$ è immediato: ci sono $2^3=8$ percorsi possibili perchè $I$ può assumere sempre 2 possibilità.
$IICII$ è altrettanto facile dato che vi sono tre possibili coppie $II$ (perchè non si può sostituire $A A$), quindi vi sono $3xx1xx3=9$ percorsi possibili.
$ICIII$ e $IIICI$ richiedono un pelo di calcolo in più ma basta calcolarne una (che è pari a 10) perchè sono simmetriche.
$IIIII$ al contrario è davvero tedioso e ce ne sono 13.

Alla fine se ne contano 50 in totale, quindi $50xx4^3=3200$

[ghira1]

Si potrebbe calcolare la sesta potenza della https://it.wikipedia.org/wiki/Matrice_delle_adiacenze

Probabilmente è quello che ho già fatto. Ma dovendolo fare per numeri molto maggiori di 6, facendo così possiamo elevare la matrice al quadrato ripetutamente, ecc.

[Bokonon]

@ghira
Se parti dal processo che ho illustrato (fondamentalmente io sono partito direttamente dalle sequenze generalizzate perchè le C "spaccano" la sequenza in sequenze più piccole), allora è possibile creare matrici di adiacenze specifiche per i percorsi $I$, $II$ e $III$. Per il percorso $IIIII$ invece si possono combinare i percorsi $III$ e $II$ (oppure direttamente una matrice di adiacence semplificata perchè il percorso non deve tenere conto della casa centrale). Contati i percorsi, basta moltiplicarli per $4^3$

[ghira1]

"Bokonon":@ghira
Se parti dal processo che ho illustrato (fondamentalmente io sono partito direttamente dalle sequenze generalizzate perchè le C "spaccano" la sequenza in sequenze più piccole), allora è possibile creare matrici di adiacenze specifiche per i percorsi $I$, $II$ e $III$. Per il percorso $IIIII$ invece si possono combinare i percorsi $III$ e $II$ (oppure direttamente una matrice di adiacence semplificata perchè il percorso non deve tenere conto della casa centrale). Contati i percorsi, basta moltiplicarli per $4^3$

Ma se dovessimo rispondere alla stessa domanda per percorsi di lunghezza 1000 o 1000000 come faremmo? Per percorsi di lunghezza 6 la matrice non mi convince ma per 1000000 forse sì.