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
- Hamiltonov problem
- Povezave na spletne strani skakačevega obhoda (v angleščini)
- Skakačev obhod(v angleščini)
- Skakačev obhod(v angleščini)
