Hanoiko Dorreak

Hanoiko Dorreak hiru hagatxo bertikaldun eta jokoaren konplexutasuna determinatzen duten disko kopuru indeterminatu bat duen joko bat da. Ez daude bi disko berdinik, handitik txikira jartzen dira lehen hagatxoan eta ezin da inoiz disko handi bat txikiago baten gainean jarri. Jokoa disko guztiak lehen hagatxotik hirugarrenera handitik txikira pasatzean datza.^[1]

Izena Hanoi hiritik datorkio.

Kondaira aldatu

Benareseko tenplu batean munduaren zentroa seinalatzen zuen kupula bat zegoen. Bertan diamantezko hiru orratz zituen erretilu bat zegoen. Goiz euritsu batean, erregeak urrezko 64 disko jartzeko agindu zuen, neurriaren arabera ordenatuta, handiena erretiluaren oinarrian eta txikiena gainontzeko disko guztien gainean.

Ondoren, tenpluko apaizek diskoak orratzetan zehar mugitzen saiatu ziren, eman zitzaizkien arauei jarraituz: "Txanda duen apaizak disko bat mugi dezake bakarrik, eta ezin du diametro handiagoa duen disko bat txikiagoa duen beste baten gainean jarri". Beste kondaira baten arabera, Jainkoak sortu zuen jokoa eta apaizek askatzea lortzen dutenean, mundua amaitu egingo da.

Jokoa askatzeko mugimendu kopuru minimoa 2⁶⁴-1 da. Apaizek segundoko mugimendu bat egingo baluke, 64 diskoak 585 milioi urte barru egongo lirateke hirugarrengo hagatxoan.

Hanoiko Dorreen erreza da askatzen, baina egin beharreko pauso kopurua esponentzialki igotzen da diskoen kopuruak gora egiten duen bezala.

Problema hau askotan programazioaren eremuan planteatu ohi izan da, gehienbat errekurtsibitatea azaltzeko.