![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/8/86/Knight%2527s_tour.svg/langsl-640px-Knight%2527s_tour.svg.png&w=640&q=50)
Skakačev obhod
kombinatorični problem iskanja poti za skakača na prazni šahovnici, po kateri obišče vsako polje natanko enkrat / From Wikipedia, the free encyclopedia
Skakačev obhod je matematični problem s skakačem na standardni šahovnici (8×8). Skakača postavimo na poljubno začetno polje in z njim obiščemo vsa ostala polja na deski.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/8/86/Knight%27s_tour.svg/320px-Knight%27s_tour.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Turk-knights-tour.svg/320px-Turk-knights-tour.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f8/Knightstour2.gif/220px-Knightstour2.gif)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/6/64/Knight%27s_graph_showing_number_of_possible_moves.svg/640px-Knight%27s_graph_showing_number_of_possible_moves.svg.png)
Obstaja več milijard rešitev. V okoli 122.000.000 rešitvah se skakač vrne na isto polje, od koder je začel.
Problem, ki so ga proučevali mnogi matematiki, tudi Euler, lahko posplošimo v več smeri:
- iščemo zaključene obhode (po zadnji potezi skakač skoči na začetno polje),
- uporabimo različne velikosti (in oblike) šahovnice,
- uporabimo drugačne šahovske figure,
- uporabimo drugačno topologijo šahovnice.
Obstajajo tudi igre za enega ali več igralcev na to temo.
Skakačev obhod je primer bolj splošnega iskanja Hamiltonove poti v teoriji grafov, ki je NP-poln. Zaključen skakačev obhod pa je primer Hamiltonovega cikla.