Skakačev obhod

Iz Wikipedije, proste enciklopedije

64 17 8 29 20 15 6 13
9 30 19 16 7 12 25 22
18 63 28 11 24 21 14 5
31 10 33 62 41 26 23 54
34 61 40 27 50 55 4 45
39 32 37 42 3 46 53 56
60 35 2 49 58 51 44 47
1 28 59 36 43 48 57 52
Primer rešitve

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.

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 s to taktiko.

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.

[uredi] Program v paskalu

[uredi] Glej tudi


[uredi] Zunanje povezave