Beperken we ons even tot de linkerbenedenhoek van ons welbekende schaakbord (a1-a4-d4-d1). Er staat een toren op a1, die in 16 zetten naar elk vakje wil gaan en op de 16de zet terug op a1 wil belanden. Deze toren heeft echter een vreemde eigenschap: Hij kan alleen sprongen van 2 of 3 zetten maken. Kan jij hem helpen?

Ikzelf heb er wel even op gezwoegd, en blind tijdens het wandelen is het me niet gelukt.

•  De oplossing is toch wel wat verrassend: 
• a1-a3-c3-c1-c4-c2-a2-a4-d4-d2-b2-b4-b1-b3-d3-d1-a1! Dus eerst de a en c-lijnen, dan b en d, ik was het verder aan het zoeken.  

Toen ik dit gevonden had ben ik ermee gestopt, maar misschien zijn er nevenoplossingen...

Ik heb een kleine collectie van dergelijke puzzels, maar deze was me onbekend.

Mijn eerste oplossing begint wel op dezelfde manier maar verlaat halfweg het systematisch patroon

•  namelijk: 
• a1-a3-c3-c1-c4-c2-a2-d2-b2-b4-b1-b3-d3-d1-d4-a4-a1  

Het mag duidelijk zijn dat er ettelijke meerdere fundamenteel verschillende oplossingen bestaan; maar wie kan hun aantal beredeneren (en dus niet met brute-force technieken bepalen) ?

Leuke puzzel Stijn! Ik heb hem met plezier opgelost.

Luc, ik zou er niet zo zeker van zijn dat er vele fundamenteel verschillende oplossingen zijn. Enig denkwerk leidt me tot 3 verschillende routes. Ze kunnen natuurlijk ook gespiegeld, achteruit, en gespiegeld en achteruit worden afgelegd wat het totaal aantal oplossingen op 12 zou brengen.

Edited omdat ik niet kan tellen.

Dat zou dan betekenen dat ik quasi meteen de op één na laatste andere oplossing vond?

Je zal geniaal zijn zeker.

Het zou natuurlijk ook kunnen dat mijn redenering niet volledig waterdicht dicht is. Ik heb me niet aan een rigoureus wiskundig bewijs gewaagd.

Ik heb geprobeerd manueel de ganse beslissingsboom op te stellen, en dat gaat een beetje moeizaam en is uiteraard foutgevoelig; ik kreeg wel het gevoel dat er meerdere oplossingen gingen uitkomen, maar betrouwde het niet meer toen mijn tweede A4'tje volgekribbeld was.

Dus heb ik ook maar een programmaatje geschreven, en dat geeft 12 oplossingen in het totaal; de helft ervan begint vertikaal, de andere helft begint horizontaal en is er gewoon een spiegeling van langsheen a1-d4, dus nog zes kandidaat onafhankelijke oplossingen:

1. a1-a3-c3-c1-c4-c2-a2-d2-b2-b4-b1-b3-d3-d1-d4-a4-a1
2. a1-a3-c3-c1-c4-c2-a2-a4-d4-d2-b2-b4-b1-b3-d3-d1-a1
3. a1-a4-c4-c2-a2-d2-b2-b4-d4-d1-b1-b3-d3-a3-c3-c1-a1
4. a1-a4-d4-b4-b2-d2-a2-c2-c4-c1-c3-a3-d3-b3-b1-d1-a1
5. a1-a4-d4-d1-d3-b3-b1-b4-b2-d2-a2-c2-c4-c1-c3-a3-a1 vervalt
6. a1-a4-a2-c2-c4-c1-c3-a3-d3-b3-b1-b4-b2-d2-d4-d1-a1

Hierbij valt nog op te merken:

• (5) is de achteruit-versie van (1) en vervalt
• (1) en (2) starten met kleine en eindigen op grote stap, (3) doet het omgekeerd, deze zijn alle verschillend
• (4) en (6) starten en eindigen met grote stap, en zijn niet elkaars achteruit-versie

Dus zijn er vijf onafhankelijke oplossingen, waarvan (1) al eerder door mezelf en (2) door Stijn gevonden waren. (3), (4) en (6) zijn bijkomende oplossingen.

Je oplossingen (2) en (3) zijn niet onafhankelijk. (4) en (6) ook niet.

OK, ze zijn elkaars achteruitse spiegelbeeld; we besluiten dat er drie echte oplossingen zijn.

En nu moogt ge het oplossen voor een bord van M*N velden, in de eerste plaats met M=N=even, daarna in het algemeen.

Hier alvast een mogelijke oplossing voor 6x6.

21:13

Ik heb mijn oplossingsmethode nog verder veralgemeend. Voor m even en n even (niet noodzakelijk m = n) kan ik zo verschillende oplossingen construeren.

Ik neem aan dat een oplossing vinden voor grotere M en/of N relatief gemakkelijk is, en dat een aantal oplossingen voor toenemende M en/of N recursief kunnen gevonden worden, t.t.z. dat er "concepten" bestaan die werken voor een hele reeks situaties. Maar wat gebeurt er met het aantal oplossingen (totaal of onafhankelijk), dat lijkt me het echte probleem.

Natuurlijk zijn er concepten die steeds terugkeren. Mijn oplossingsmethode (ha!) is trouwens nogal barbaars. Door het aantal mogelijkheden drastisch te beperken en het bord te transformeren decimeer ik het aantal mogelijke routes. Het gereduceerde probleem is dan eenvoudig visueel op te lossen. De truc is uiteraard een goede transformatie te vinden.

Deze methode werkt voor M even en N willekeurig en beiden > 4. Ik ben er vrij zeker van dat het onoplosbaar is als M en N beiden oneven zijn. Hé, ik realiseer me net dat ik 4xN nog moet oplossen! Update: Wel, dat liep met een sisser af. Ik kan op dezelfde manier te werk gaan. Ik heb wel ingezien dat ik nog veel meer transformaties kan verzinnen voor de andere gevallen.

Het aantal unieke oplossingen lijkt me een evenredig te zijn met het aantal Hamiltoncircuits. Elke transformatie van een willekeurig Hamiltoncircuit geeft volgens mij een unieke oplossing.