Povijesna dubina: Vitezova tura je matematički niz u kojem vitez posjeti svaku jedinu ćeliju na šahovnici točno jednom. To je istovremeno strateški izazov i klasičan problem rekreacijske matematike.
Porijeklo:
Ovaj problem je daleko od modernog otkrića. Najranija poznata rješenja datiraju iz 9. stoljeća, a dali su ih majstori iz Bagdada poput Al-Adlija i As-Sulija. Štoviše, u indijskoj književnosti iz 9. stoljeća kašmirski pjesnik Rudrata pokazao je ovu matematičku estetiku u svom djelu Kavyalankara, gdje je sastavio pjesmu koja je slijedila niz viteškog hoda.
Zapadna književnost:
U 13. stoljeću kralj Alfonso X. od Kastilje u svom poznatom Libro de los Juegos (Knjiga igara) prikazao je složene manevre temeljene na kretanju viteza. Međutim, moderno matematičko utemeljenje problema postavio je 1759. Leonhard Euler, čija se analiza danas smatra jednim od kamenova temeljaca teorije grafova.
Karakteristike:
Zatvoreni (ponovno ulazeći) obilazak: Ako vitez završi na polju koje je točno jedan potez viteza udaljeno od početnog polja, omogućujući mu da odmah ponovno započne turu.
Otvoreni obilazak:
Ako vitez posjeti svaku ćeliju, ali završi na ćeliji s koje ne može dosegnuti početnu ćeliju jednim potezom.
Postavio ga je Max Bezzel 1848. godine i privukao pažnju genija poput Carla Friedricha Gaussa, a ovaj je problem 1970-ih pretvoren u “manifest programiranja” od strane jednog od očeva moderne računalne znanosti, Edsgera W. Dijkstre.
U svom temeljnom djelu, Bilješke o strukturiranom programiranju (1972), Dijkstra je iskoristio problem osam kraljica kako bi pokazao kako se algoritam može sustavno konstruirati kroz proces koji je nazvao “postupno usavršavanje”.”
Moć povratnog traženja:
Prema Dijkstri, ovaj pristup predstavlja prvi veliki korak u usavršavanju procesa “pokušaja i pogreške” u besprijekornu logičku sekvencu koju a
Legenda i podrijetlo:
Prema priči, kada je izumitelj šaha, Sissa bin Dahir, predstavio igru indijskom kralju, kralj ga je upitao kakvu nagradu želi. Sissa je postavio naizgled skroman zahtjev: “Želim jedno zrno pšenice za prvi kvadrat šahovnice, dva za drugi, četiri za treći i za svaki sljedeći kvadrat dvostruko više od prethodnog.” Kralj je u početku odbacio taj zahtjev, misleći da je riječ samo o “šaku pšenice”; no kad je započelo izračunavanje, postalo je jasno da ni riznica ni cjelokupne svjetske zalihe pšenice ne bi bile dovoljne za ispunjenje tog zahtjeva.
Povijesni zapis: Ibn Halikan (1256)
Prvi poznati pisani zapis ove čuvene priče dokumentirao je 1256. godine ugledni biograf i povjesničar Ibn Halikan. Ibn Halikan je taj događaj u svoje djelo ugradio ne samo kao priču, nego i kao dokaz kako matematika pomiče granice mašte.
Matematikalna stvarnost:
Ovaj zahtjev za 64 kvadrata na šahovnici najčišći je primjer geometrijske progresije (eksponencijalnog rasta). Iznos na svakom kvadratu izračunava se pomoću formule 2n-1 . Jednadžba koja daje ukupnu količinu pšenice je sljedeća:
63
∑
i=0
2i = 264 − 1
Masivna brojka koja proizlazi iz ovog izračuna je:
18,446,744,073,709,551,615
Zašto je to tako važno?
Strateška lekcija: Ovaj problem je drevna lekcija mudrosti koja podučava vođe i stratege kako male promjene (“dvostruko povećanje”) s vremenom mogu prerasiti u nekontrolirane sile.
