Is het mogelijk om met een paard op een 4x4 schaakbord een Hamiltoncircuit te maken ??? Ik kom er maar niet uit !!!Mathijs van Duurling
9-3-2003
Tja, wat lezen wij op onderstaande website:
"In general, the problem of finding a Hamiltonian circuit is NP-complete (Garey and Johnson 1983), so the only known way to determine whether a given general graph has a Hamiltonian circuit is to undertake an exhaustive search."Dat is vervelend, want hoe weet je nu zeker dat het niet kan? Als je alle mogelijkheden geprobeerd hebt en er geen oplossing bij bleek te zitten. Dus... systematisch zoeken!
Zie ook Knight's Tour, daar staat:
The number of possible tours on a 4xk board for k = 3, 4, ... are 8, 0, 82, 744, 6378, 31088, 189688, 1213112, ... (Sloane's A079137; Kraitchik 1942, p. 263).
..dus dan weet je wel hoe laat het is...
Zie Hamiltonian Circuit [http://mathworld.wolfram.com/HamiltonianCircuit.html]
WvR
10-3-2003
#8326 - Grafen - Leerling bovenbouw havo-vwo