Langlaufen - voor mij wel

[spades]

Hallo allemaal! Graag zou ik nog een vraag willen stellen over een hersenkraker, althans een kraker voor mij!

Stel ik heb 36 cellen in een vierkant van 6 bij 6. Ik pik hieruit een willekeurige cel en ga vanuit deze cel horizontaal en/of verticaal naar een volgende cel lopen (dus niet diagonaal). Elke cel die ik passeer, maakt onderdeel uit van een pad dat op deze manier wordt bewandeld. De cel vanwaaruit ik start is cel nummer 1, elke volgende cel krijgt een oplopend nummer, dus 2, 3, 4 etc.

Mijn vragen zijn nu:

1) Stel een pad is minimaal 4 cellen lang en maximaal 8 cellen lang: hoeveel paden zijn er dan in totaal binnen dit vierkant mogelijk?

Dit lijkt me een optelsom van:
- alle mogelijke paden van 4 cellen lang, plus
- alle mogelijke paden van 5 cellen lang, plus
- alle mogelijke paden van 6 cellen lang, plus
- alle mogelijke paden van 7 cellen lang en
- alle mogelijke paden van 8 cellen lang.

Ik weet echter niet hoe ik dit moet berekenen gegeven het feit dat het totaal moet worden berekend vanuit ieder mogelijk vertrekpunt binnen het vierkant: er zijn immers 36 vertrekpunten en niet elk vertrekpunt heeft evenveel mogelijkheden om paden op te bouwen als het andere (denk alleen maar aan de hoekcellen van het vierkant).

Ook is het zo dat een pad vanuit een vertrekpunt dezelfde cellen kan gebruiken om tot een tweede pad met dezelfde lengte te komen. Voorbeeld in het geval van een pad van 4 cellen lang:

3 2
4 1

en

3 4
2 1

Zelfde cellen gebruikt, toch twee paden.

Wie weet wat het antwoord is en nog belangrijker: hoe je dit berekent?

2) Als de formule van vraag 1 bekend is, hoe verandert deze dan als binnen dit vierkant van 36 cellen één cel niet meer beschikbaar is om in een pad gebruikt te kunnen worden: er zijn dan 35 cellen.

3) Zelfde vraag als 2, maar nu als er 2, 6, 10 of een ander aantal cellen niet meer beschikbaar wordt gesteld.

Petje af voor wie dit oplost!

[arie]

Als ik zo snel even kijk zie ik 2 ingangen:

(methode 1)
Maak een matrix M[6][6] die aangeeft hoeveel eindpunten van paden met lengte i er in een punt op het 6x6 vierkant zijn:
Begin met paden met lengte i=1: M[1]=
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
immers: in elke cel eindigt precies 1 pad met lengte 1.
Voor elke volgende padlengte i geldt dat dit aantal per cel de som is van alle aangrenzende Noord, Oost, Zuid en West cellen met padeinden van paden waarvan de lengte = i-1.
Bijvoorbeeld padlengte 2: M[2]=
2 3 3 3 3 2
3 4 4 4 4 3
3 4 4 4 4 3
3 4 4 4 4 3
3 4 4 4 4 3
2 3 3 3 3 2
De som van al deze 6x6 waarden voor padlengte i is dan je gevraagde aantal per padlengte.
Gezien de regelmaat hierin verwacht ik een mooie recursieve (Fibonacci-achtige) functie.

(methode 2)
genereer alle mogelijke paden van lengte i, bijvoorbeeld i=4: WWZ (vanuit begincel eerst west, dan weer west, dan zuid = pad van 4 cellen)
kijk dan hoe breed en hoe hoog dit pad is, bepaal daaruit hoe vaak het in het 6x6 vierkant past.

De 2e methode lijkt me op het eerste gezicht moeilijker, er zijn per padlengte in principe (i-1)^4 mogelijke paden.

Een ander punt waar je op moet letten is dat we er nu vanuit gaan dat je cellen meerdere malen mag doorlopen. Als dat niet zo is, moeten we bovenstaande daarop aanpassen.

Wat betreft de beschikbaarheid van cellen:
Dit geeft nog veel grotere problemen: bekijk bijvoorbeeld 2 cellen die niet beschikbaar zijn: we moeten dan wel weten welke cellen dit zijn om tot een antwoord te komen: als cel [0][1] en cel [1][0] niet beschikbaar zijn, blokkeren ze ook alle toegang tot cel [0][0] en is cel [0][0] effectief ook niet beschikbaar...

Kom je zo verder?

[spades]

Hallo arie,

bedankt voor je reaktie!

"Een ander punt waar je op moet letten is dat we er nu vanuit gaan dat je cellen meerdere malen mag doorlopen. Als dat niet zo is, moeten we bovenstaande daarop aanpassen."

Daar heb je me: dat mag niet, althans niet binnen 1 pad. Had ik moeten vertellen.

Wat ik zoek is een formule waarmee ik dit aantal kan berekenen. In wiskunde ben ik absoluut niet thuis, althans niet op jouw niveau, en ik kwam zelf ook uit op methode 2: dat is eigenlijk niet meer dan puzzelen ) Toch heb ik een formule nodig om met name de vervolgvragen te kunnen berekenen.

Ik heb geen idee wat een mooie recursieve (Fibonacci-achtige) functie is. Blij dat je dit zelf wel als zodanig herkent ) Ik snap wat je beschrijft <-- leuk bedacht trouwens! maar ik vrees dus dat ik zelf hier niet mee verder kom en dat ik wellicht een veel te moeilijk probleem heb beschreven.

Toch bedankt !!

[arie]

Als je van programmeren houdt is hier een min of meer brutekracht zoekprogramma in C.
Ik heb het geschreven op duidelijkheid, het kan zeker allemaal nog veel efficienter, maar dit laat ik verder aan jou over.
Je kan het zo nodig aanpassen aan de taal van jouw voorkeur (wsch werkt het direct in Java).
Volgens mij is alles vrij standaard (geen ingewikkelde/exotische functies).
De tekst achter // is commentaar.
Je moet de functie "main6x6()" aanroepen om alles te starten.

(1)
Dit programma telt alle paden voor elke padlengte, waarbij alle cellen beschikbaar zijn:

Code: Selecteer alles

int P[11][11]; //matrix waarin we het pad maken
int horizontaal[11];
int verticaal[11];
int breedte, hoogte; //breedte en hoogte van het pad
int maxlengte; //padlengte die we zoeken
int richting[4][2]={ //x en y waarde van de 4 richtingen
	{1, 0},		//oost
	{0, 1},		//noord
	{-1, 0},	//west
	{0, -1}};	//zuid
int totaal; //teller voor het aantal paden
FILE *fo66;

void maakpad(int lengte, int x, int y)
{
int r, nx, ny;

if(lengte==maxlengte){
	// DEEL 1: ALLE CELLEN BESCHIKBAAR:
	//tel aantal mogelijkheden:
	totaal=totaal+((7-breedte)*(7-hoogte));
	}
else{
	for(r=0;r<4;r++){
		nx=x+richting[r][0]; //volgende x positie
		ny=y+richting[r][1]; //volgende y positie
		if(nx>=0 && nx<11 && ny>=0 && ny<11){ //als pad binnen P[][] past:
			if(P[ny][nx]==0){ //als deze cel nog niet gebruikt is:
				//update naar nieuwe hoogte en breedte:
				if(horizontaal[nx]==0) //pas zo nodig de breedte aan
					++breedte;
				++horizontaal[nx]; // voeg nieuwe positie toe
				if(verticaal[ny]==0)  //pas zo nodig de hoogte aan
					++hoogte;
				++verticaal[ny];   //voeg nieuwe positie toe
				if(breedte<7 && hoogte<7){ //als het huidige pad in 6x6 blok past:
					P[ny][nx]=1; //bezet de huidige nieuwe plaats
					maakpad(lengte+1,nx,ny); //bepaal volgende stap(pen)
					P[ny][nx]=0; //geef de huidige nieuwe plaats weer vrij
					}
				//herstel vorige hoogte en breedte:
				--verticaal[ny];
				if(verticaal[ny]==0)
					--hoogte;
				--horizontaal[nx];
				if(horizontaal[nx]==0)
					--breedte;
				}
			}
		}
	}
}

void probleem6x6(void)
{
int i,j;

//zet pad matrix P[][] etc in beginstand:
for(i=0;i<11;i++){
	horizontaal[i]=0; //telt per kolom het aantal gebruikte cellen
	verticaal[i]=0;   //telt per rij het aantal gebruikte cellen
	for(j=0;j<11;j++)
		P[i][j]=0;      //0 = locatie niet bezet door huidige pad
	}
P[5][5]=1; //begin met een blok op positie P[5][5], 1 = bezet
horizontaal[5]=1;
verticaal[5]=1;
breedte=1; //breedte van huidige pad = 1
hoogte=1;  //hoogte van huidige pad = 1
//zet teller van aantal paden op nul:
totaal=0;

//maak alle mogelijk paden vanuit deze positie:
maakpad(1, 5, 5);

//schrijf resultaat naar bestand ("at" = voeg tekst toe aan het bestand):
fo66=fopen("out6x6at.txt","at");
fprintf(fo66,"%d\t%d\n",maxlengte,totaal);
fclose(fo66);
}


void main6x6(void)
{
//los het probleem op voor de gewenste padlengte maxlengte:
for(maxlengte=1;maxlengte<38;maxlengte++)
	probleem6x6();
}

resultaat (steeds eerst de padlengte, daarna het aantal mogelijke paden van die lengte):

Code: Selecteer alles

1	36
2	120
3	296
4	752
5	1712
6	4008
7	8752
8	19312
9	39792
10	82032
11	159104
12	309616
13	571168
14	1061008
15	1863024
16	3299808
17	5465248
18	9146816
19	14095984
20	21991248
21	31051040
22	44466720
23	56742912
24	73498576
25	83405456
26	95981888
27	94683168
28	94706032
29	78636320
30	66265784
31	43853696
32	29350680
33	13889632
34	6457528
35	1671808
36	458696
37	0
...

(uiteraard zijn er geen paden van 37 of meer cellen mogelijk)


(2)
Nu hetzelfde, aangevuld met de mogelijkheid om bepaalde cellen niet meer beschikbaar te maken (=af te sluiten)

Code: Selecteer alles

int P[11][11]; //matrix waarin we het pad maken
int horizontaal[11];
int verticaal[11];
int breedte, hoogte; //breedte en hoogte van het pad
int maxlengte; //padlengte die we zoeken
int richting[4][2]={ //x en y waarde van de 4 richtingen
	{1, 0},		//oost
	{0, 1},		//noord
	{-1, 0},	//west
	{0, -1}};	//zuid
int totaal; //teller voor het aantal paden
FILE *fo66;
//deel 2:
int afgesloten[6][6]; //geeft beschikbaarheid vd cellen aan: 0=beschikbaar, 1=afgesloten

//deel 2: tel het aantal paden afhankelijk van beschikbaarheid:
void telBeschikbaar(void)
{
int pad[6][6];
int x0, y0;
int x,y;
bool ok;

//zoek in P[][] de top-links cel (y0,x0) van de minimale rechthoek waarin het pad ligt:
x0=0;
while(horizontaal[x0]==0)
	++x0;
y0=0;
while(verticaal[y0]==0)
	++y0;
//kopieer het pad in P[][] naar pad[][]
for(x=0;x<breedte;x++)
	for(y=0;y<hoogte;y++)
		pad[y][x]=P[y0+y][x0+x];

//schuif nu pad[][] over afgesloten[][] en tel de toegestane paden:
for(x0=0;x0<(7-breedte);x0++){
	for(y0=0;y0<(7-hoogte);y0++){
		ok=true;
		for(x=0; x<breedte && ok; x++)
			for(y=0; y<hoogte && ok; y++)
				if(pad[y][x]==1 && afgesloten[y0+y][x0+x]==1) //pad loopt over afgesloten cel:
					ok=false;
		if(ok) //indien dit pad op deze positie (x0,y0) niet over afgesloten cel loopt:
			++totaal; //totaal = totaal + 1
		}
	}

}

void maakpad(int lengte, int x, int y)
{
int r, nx, ny;

if(lengte==maxlengte){
	// DEEL 2: TEL INDIEN BESCHIKBAARHEID:
	telBeschikbaar();
	}
else{
	for(r=0;r<4;r++){
		nx=x+richting[r][0]; //volgende x positie
		ny=y+richting[r][1]; //volgende y positie
		if(nx>=0 && nx<11 && ny>=0 && ny<11){ //als pad binnen P[][] past:
			if(P[ny][nx]==0){ //als deze cel nog niet gebruikt is:
				//update naar nieuwe hoogte en breedte:
				if(horizontaal[nx]==0) //pas zo nodig de breedte aan
					++breedte;
				++horizontaal[nx]; // voeg nieuwe positie toe
				if(verticaal[ny]==0)  //pas zo nodig de hoogte aan
					++hoogte;
				++verticaal[ny];   //voeg nieuwe positie toe
				if(breedte<7 && hoogte<7){ //als het huidige pad in 6x6 blok past:
					P[ny][nx]=1; //bezet de huidige nieuwe plaats
					maakpad(lengte+1,nx,ny); //bepaal volgende stap(pen)
					P[ny][nx]=0; //geef de huidige nieuwe plaats weer vrij
					}
				//herstel vorige hoogte en breedte:
				--verticaal[ny];
				if(verticaal[ny]==0)
					--hoogte;
				--horizontaal[nx];
				if(horizontaal[nx]==0)
					--breedte;
				}
			}
		}
	}
}

void probleem6x6(void)
{
int i,j;

//zet pad matrix P[][] etc in beginstand:
for(i=0;i<11;i++){
	horizontaal[i]=0; //telt per kolom het aantal gebruikte cellen
	verticaal[i]=0;   //telt per rij het aantal gebruikte cellen
	for(j=0;j<11;j++)
		P[i][j]=0;      //0 = locatie niet bezet door huidige pad
	}
P[5][5]=1; //begin met een blok op positie P[5][5], 1 = bezet
horizontaal[5]=1;
verticaal[5]=1;
breedte=1; //breedte van huidige pad = 1
hoogte=1;  //hoogte van huidige pad = 1
//zet teller van aantal paden op nul:
totaal=0;

//maak alle mogelijk paden vanuit deze positie:
maakpad(1, 5, 5);

//schrijf resultaat naar bestand ("at" = voeg tekst toe aan het bestand):
fo66=fopen("out6x6at2.txt","at");
fprintf(fo66,"%d\t%d\n",maxlengte,totaal);
fclose(fo66);
}

//deel 2: definieer de beschikbaarheid van de cellen:
void bepaalBeschikbaarheid(void)
{
int x,y;

//maak eerst alle cellen beschikbaar:
for(x=0;x<6;x++)
	for(y=0;y<6;y++)
		afgesloten[y][x]=0;  // 0 = beschikbaar
//sluit nu een aantal cellen af:
afgesloten[2][1]=1;      // 1 = afgesloten = niet beschikbaar
afgesloten[4][3]=1;      // 1 = afgesloten = niet beschikbaar
}

void main6x6(void)
{
int x,y;

bepaalBeschikbaarheid();
//schrijf de afgesloten cellen naar het bestand:
fo66=fopen("out6x6at2.txt","at");
fprintf(fo66,"\nafgesloten:\n");
for(x=0;x<6;x++)
	for(y=0;y<6;y++)
		if(afgesloten[y][x]==1)
			fprintf(fo66,"(%d,%d)\n",x,y);
fclose(fo66);
//los het probleem op voor de gewenste padlengte maxlengte:
for(maxlengte=1;maxlengte<9;maxlengte++)
	probleem6x6();
}

En hier een aantal resultaten bij afsluiting van verschillende cellen:

Code: Selecteer alles

alle cellen beschikbaar:
1	36
2	120
3	296
4	752
5	1712
6	4008
7	8752
8	19312

afgesloten:
(0,0)
1	35
2	116
3	286
4	724
5	1642
6	3820
7	8284
8	18104

afgesloten:
(0,1)
1	35
2	114
3	278
4	698
5	1574
6	3634
7	7810
8	16898

afgesloten:
(0,2)
1	35
2	114
3	276
4	688
5	1534
6	3518
7	7520
8	16178

afgesloten:
(1,1)
1	35
2	112
3	264
4	648
5	1434
6	3248
7	6834
8	14448

afgesloten:
(2,2)
1	35
2	112
3	260
4	612
5	1264
6	2684
7	5302
8	10696

afgesloten:
(0,0)
(0,1)
1	34
2	112
3	274
4	690
5	1552
6	3582
7	7676
8	16586

afgesloten:
(0,1)
(1,0)
1	34
2	108
3	264
4	660
5	1476
6	3372
7	7156
8	15276

afgesloten:
(0,0)
(0,1)
(1,0)
1	33
2	108
3	264
4	660
5	1476
6	3372
7	7156
8	15276

afgesloten:
(1,2)
(3,4)
1	34
2	104
3	228
4	508
5	1012
6	2068
7	3952
8	7628

Je ziet dat het sterk uitmaakt welke cellen we afsluiten.
Bij een klein aantal is het nog wel te doen alles te bekijken, maar bij bijvoorbeeld 4 afgesloten cellen hebben we al 36C4 = 58905 mogelijke combinaties (symmetrieen even verwaarloosd).

PS: leuk probleem! heb je het zelf bedacht?

[spades]

Wwwow arie, petje af hoor, geweldig!

Ik ga dit eens even mooi bestuderen, ik kan het lezen dus komt goed. Geweldig dat je zoveel tijd hierin hebt gestoken, waardeer het zeer !!!!

>>PS: leuk probleem! heb je het zelf bedacht?
Dat kun je wel stellen ja. Ben bezig met een matrix waarin paden moeten worden onderkend. Ik heb nu een vlak van 6 bij 6 genomen, maar ook dat fluctueert qua grootte. Hoofdzaak is dat het maximum aantal mogelijke paden wordt onderkend, met name om zo onder meer de lengte van arrays te onderkennen, het aftikken van optimale paden etc. etc. En dan ben ik er nog lang niet, maar het gaat helemaal goedkomen! Nogmaals bedankt!!