Kortaste vägen för springaren

Som jag nämnde i din andra tråd är detta ett klassiskt grafproblem. 

Breadth-First-Search (BFS) är nog det bästa metoden att lösa dessa typer av problem. Du kommer förmodligen hitta BFS associerat med programmering, men det går att tillämpa på en vanlig graf för hand. Det är inte omständigt heller om grafen är relativt liten, vilket din blir. Är grafen enorm, exempelvis alla städer i Sverige, så är det lite tidskrävande att göra det utan programmering.

For example, in a chess endgame, a chess engine may build the game tree from the current position by applying all possible moves and use breadth-first search to find a win position for White. Implicit trees (such as game trees or other problem-solving trees) may be of infinite size; breadth-first search is guaranteed to find a solution node[1] if one exists.

Hur man ska lösa detta matematiskt utan grafer vet jag faktiskt inte. Någon annan kanske har bättre koll på detta. Lycka till! :)

Jag skulle börja med ett tomt bräde. Rutan jag vill hoppa till markerar jag med 0. Sedan markerar jag alla rutor som en springare kan hoppa till från 0-rutan med 1. Sedan markerar jag alla rutor som man kan hoppa till från en 1-ruta med 2, utom dem som redan har en markering. Så håller jag på tills brädet är fullt, fast det räcker när jag har markerat rutan som jag vill hoppa från.

Frågor: vilket är det största antal N₈ som behövs på ett vanligt schackbräde? Vilken är den minsta storlek på ett kvadratiskt bräde så att det behövs N₈ + 1 hopp?

Om brädet är oändligt stort så kan man fortfarande göra som ovan, men jag är rätt säker på att det finns ett mönster som upprepar sig som man kan använda. Det borde bli bra om man hoppar i ungefär rätt riktning ganska länge. Men det kanske inte är så enkelt.

Tack för ditt svar! Med hjälp av det upptäckte jag en detalj som jag tror kan hjälpa en hel del. Jag är inte helt säker ännu, men det verkar som att den önskade rutan alltid delar sina sidor med rutor det krävs 2 drag ifrån, samt sina hörn med rutor det krävs 3 drag ifrån. 

Frågor: vilket är det största antal N₈ som behövs på ett vanligt schackbräde? Vilken är den minsta storlek på ett kvadratiskt bräde så att det behövs N₈ + 1 hopp?

Vad menar du med beteckningen N₈ och behövs för vad?

8 är antalet rutor på kanten av ett vanligt schackbräde. Behövs = antal hopp som behövs för att en springare ska ta sig från en viss utpekad ruta till en annan.

Ett intressant mönster som jag upptäckte - utöver det där med att målrutan alltid tangeras i hörnen av en "tvåa" och i sidorna av en "trea" - är att det verkar finnas två typer av diagonaler på brädet, oavsett vilken ruta 0 man väljer: diagonaler där varje siffra är delbar med två, och diagonaler där varje term+1 är delbar med två. I alla fall förutom de där springaren vill till en av hörnrutorna verkar dessa diagonaler följa ligga så här:

Det betyder att om springarens koordinater är någon av dessa rutor vet man garanterat att det kommer ta antingen 4 eller 2 drag att nå målet; i princip har man halverat antalet fall man behöver titta på. Nu förutsätter detta att diagonelerna beter sig så här för alla rutor där man kan sätta 0 (förutom a1, a8, h1 & h8). Samma sak gäller då såklart åt andra hållet också; om springaren börjar på en av de andra diagonalerna vet man att det kommer ta antingen 5, 3 eller 1 drag. Låter detta rimligt? Hittills har jag endast testat tre fall men på grund av brädets symmetri verkar det rimligt.

Med andra ord: de svarta diagonalerna verkar vara udda, medan de vita verkar vara jämna.

En utveckling av ovanstående observation (efter lite tänkande):

Om summan $\displaystyle\frac{x+y}{2}=q, q\epsilon\mathbb{Z}$, kommer varje ruta på samma färgkomplex också att dela den egenskapen. Dessutom gäller att om en ruta har fått en jämn siffra tilldelad, kommer alla andra rutor som delar samma färg också vara jämna.

Med det sagt vet man alltså att om koordinaterna på ursprungsrutan ger en jämn summa och koordinaterna på den önskade rutan ger en jämn summa, är antalet drag som krävs alltid jämnt. Annars blir det udda.

Antag att du har en springare på en koordinat $P$, antalet steg $N$ för att ta sig till en koordinat $Q$ är som värst 6, dvs:

$0 \leq N \leq 6$. 

En tanke, beroende på vilket koordinat $P$ du startar på, så tar det $N$ steg att ta sig ditt. Du skulle kunna i Python kunna formulera följande tabeller (om du inte vill göra det för hand):

[0,3,2,3,2,3,4,5]
[3,4,1,2,3,4,3,4]
[2,1,4,3,2,3,4,5]
[3,2,3,2,3,4,3,4]
[2,3,2,3,4,3,4,5]
[3,4,3,4,3,4,5,4]
[4,3,4,3,4,5,4,5]
[5,4,5,4,5,4,5,6], max = 6

[3,2,1,2,3,4,3,4]
[0,3,2,3,2,3,4,5]
[3,2,1,2,3,4,3,4]
[2,1,4,3,2,3,4,5]
[3,2,3,2,3,4,3,4]
[2,3,2,3,4,3,4,5]
[3,4,3,4,3,4,5,4]
[4,3,4,3,4,5,4,5], max = 5

Dock vet jag inte hur man hade redovisat detta då det finns 64 olika matriser.

Det är nog möjligt att bevisa att N är som värst 6 med lite logik, ingen matematik eller programmering.

Detta kanske kan vara intressant att läsa (se nedan). 

https://en.wikipedia.org/wiki/Knight%27s_graph 

https://en.wikipedia.org/wiki/Distance_(graph_theory)

Notera att matten kan kännas lite tungt om det är första gången du ser det. Om inget annat kan det vara användbart i ditt potentiella gymnasiearbete. 

Tack för länkarna! Jag hade faktiskt tänkt på liknande saker angående specifikt avstånd. Jag har kommit fram till några saker hittills men jag är osäker på hur jag ska fortsätta. Jag kommer även förklara vad jag har provat:

Upptäckter

• Om $\displaystyle (x+y)\mod{n}=(x_{N}+y_{N})\mod{n}=0$ medför detta att antalet drag $N$ är jämnt. Är summorna inte kongruenta med varandra medför detta att antalet drag N är udda. Detta går att visa ganska enkelt. En ruta kommer alltid dela sina hörn med rutor av samma färg. Koordinatsumman när man rör sig mellan rutor som delar hörn kan förändras på följande vis: +2, +0, -2. Det betyder att pariteten hos rutor som delar färg alltid är samma. 
• Det maximala antalet drag mellan två rutor är 6.

Försök

• Bestämma det absoluta avståndet $d$ mellan två rutor och försöka upprätta ett samband med regression mellan antalet drag $N$ och vilka möjliga avstånd $d$ springaren kan röra sig. Det verkar inte finnas något samband, men om det finns det skulle det nog krävas väldigt många fler datapunkter än vad jag testade (testade alla avstånd till och med $N=3$. För hand (vilket är det jag vill göra) skulle det ta åratal att samla tillräckligt många datapunker. Men för små värden på $N$ kan detta kanske vara användbart ändå. Om man vet att $\displaystyle d=2\sqrt{5}$ kan man direkt säga att $N=2$.  Omvänt vet man också att om $\displaystyle d\neq2\sqrt{5}$, är $N\neq2$.
• Jag har testat att dela in brädet i fyra kvadranter för att se om man kan hitta en formel för antalet drag som krävs mellan två rutor inom en kvadrant. Detta tänkte jag att man skulle kunna applicera sedan på ett större bräde, men även här lyckades jag inte komma fram till något (men jag tror ändå att denna idé skulle kunna fungera).

Jag är nyfiken på vad ni tänker om det här. Har ni något spontant förslag på någonting jag kan testa eller undersöka? Jag är öppen för alla förslag. 

Jag löste för övrigt en enkel BFS-algoritm i Python så det är skönt. Nu har jag ett snabbt sätt att dubbelkolla svar. Kanske kan jag modifiera det jag skrev för att ta fram ett samband mellan N och d? 

Koden är ganska ful också just nu men den får fixas imorgon... 😅

Update:

Jag lyckades modifiera min kod från igår kväll så att den i princip brute-forcar alla möjliga kombinationer av startrutor och slutrutor och printar det värsta möjliga scenariot. Som redan bekant blev värdet 6. Men nu har jag i alla fall ett bra sätt att motivera det. Problemet är dock att detta bara funkar på mindre bräden, typ 8x8 och kanske upp till 10x10. Om jag utvidgar brädet ytterliggare exploderar min dator om jag kör koden.

Ja, och här är lite problemet med Python! Det är väldigt segt. Visserligen är jag säker på att du hade kunnat optimera din kod rätt mycket men generellt sätt är Python ett väldigt segt språk. Det stora problemet är GIL här, som kommer stoppa dig från att kunna köra beräkningen i parallell (iaf om du vill använda 100% av din CPU). Jag har några förslag.

1. Läs på hur du kan göra Python multithreaded (en vanlig thread är inte samma sak).
2. Optimera din kod.
3. Byt språk till C/C++ som är många gånger snabbare per default.
4. Andvänd Caching
5. Använd Google Colab för att låta den utföra beräkningarna för större dimensioner.

Det intressanta med Caching är att du skulle kunna cacha resultatet för exempelvis 9x9 fallet, och helt plötsligt är 10x10 fallet inte så stort. Samma sak gäller 11x11 och man har 10x10 i cache. Notera dock att ingenting är gratis, du betalar på något sätt oavsett vad för optimering du väljer.

Visserligen är jag säker på att du hade kunnat optimera din kod rätt mycket

Japp, det hade jag kunnat! När jag skrev koden pallade jag inte riktigt tänka på vad jag gjorde (var sent på kvällen) så det blev så att jag nestade fyra loopar i varandra 😂. Det är nog skrivet på det minst optimala sättet möjligt.

Men tack för tippsen! Jag ska kolla på det!

Jag vet inte exakt hur du gör, men det borde väl räcka med två for loopar om du ska brute-force:a.

Om du har en funktion BFS(start, end), som returnerar en matris, så behöver du bara spara undan den matrisen. 

För att iterera över MxN fältet har du ju (inte riktig kod!)

for row in ...

     for column in ....

          BFS(row, column) 

Jag bumpar tråden nu, för jag sitter verkligen helt fast. Har riktigt ordentlig idétorka. Alla förslag på vad jag eventuellt skulle kunna testa uppskattas. Hittills har jag skrivit lite kod som tar fram ett antal datapunkter där den mappar springarens möjliga sträckor mot antalet drag det tar att förflytta sig den sträckan. Det verkar inte riktigt leda någonstans. 

Jag missförstår säkert vad ditt mål är, men om jag vill ta reda på hur många springardrag som krävs för att hoppa från en vissa ruta A till en ruta B så gör jag en tabell som motsvarar schackbrädet och skriver talet 0 i rutan A. Sedan skriver jag 1 i alla rutor man kan hoppa till från A. Sedan tar jag alla rutor det står 1 i och skriver 2 i alla rutor man kan hoppa till från dem, utom dem det redan står något i.

När jag når B är jag klar, men jag kan göra klart hela brädet så kan jag svara på alla sådana frågor när startpunkten är A.

Jag förstår vad du menar, och det är en bra strategi när start- och slutrutan redan är kända man har en del tid. Men jag söker någon typ av sluten formel som beräknar antalet springardrag mellan vilka rutor som helst. Och jag vill dessutom utvidga det här till ett oändligt bräde senare.

På ett oändligt bräde kan jag tänka mig en sluten formel, eller i alla fall en enkel snabb algoritm. På ett ändligt bräde tror jag inte att det finns något bättre än en tabell.

Jag tror också att en "brute force"-approach ör lämplig här; ett schackbräde är inte speciellt stort så det borde inte vara några problem med att det tar för lång tid och jag vet heller inte om det är så att det skulle finnas en sluten formel. Åtminstone ingen enkel formel som inte är uppdelat i fall, typ, 0 drag om B är samma som A, 1 drag om B ligger på diagonalen från A (sorry men jag är ej schackspelare så terminologin är improviserad), 2 om ..... osv.