\require{AMSmath}

Schaakprobleem

Is het mogelijk om met een paard op een 4x4 schaakbord een Hamiltoncircuit te maken ??? Ik kom er maar niet uit !!!

Mathij
Leerling bovenbouw havo-vwo - zondag 9 maart 2003

Antwoord

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

WvR
maandag 10 maart 2003

Re: Schaakprobleem

©2001-2024 WisFaq