Problem londonskega stolpa

Problem londonskega stolpa je miselna uganka; dane imamo palice določenih višin, na katerih so razporejene krogle različnih barv. Cilj igre je s čim manj premiki krogel preiti iz začetnega stanja v neko končno (dano) stanje krogel. Ker se londonski stolp pogosto uporablja za psihološka testiranja, v članku ta problem podrobneje preučimo: narišemo lahko graf, pri čemer so stanja krogel vozlišča, veljavne poteze pa povezave. Nato obravnavamo lastnosti tega grafa - najprej za klasični problem londonskega stolpa, kjer imamo 3 palice (višin 1, 2, 3) in 3 krogle različnih barv, nato pa še za splošen primer s i palicami in n kroglami. Izkaže se, da je graf klasičnega problema ravninski in vsebuje Hamiltonovo pot, ni pa Hamiltonov. Pri splošnem primeru dokažemo, da je graf nekega problema londonskega stolpa povezan natanko tedaj, ko lahko krogle razporedimo tako, da najvišja palica ostane prazna. Prav tako ugotovimo, da so ravninski le grafi problemov z dvema kroglama in nekateri grafi problemov s tremi kroglami. V članku obravnavamo tudi poseben primer londonskega stolpa, pri katerem so vse palice enake višine n, imenovan oxfordski stolp. Za tak problem izpeljemo formulo za število vozlišč in povezav za poljubna n in p.

The Tower of London problem

The Tower of London is a problem-solving puzzle, which consists of pegs of various heights that hold different-coloured balls of the same size. The aim of the puzzle is to get from the beginning state of the balls to the given end state with as little moves as possible. The Tower of London is often used in psychological testings, which is our motivation to study this problem in more detail. In order to do that, we use graph theory: a graph of the problem, called the London graph, can be drawn. Here, the vertices of the graph are all possible states and the edges are valid moves between these states. In this article, we take a look at some of the properties of London graphs. First, we analyse the graph of the classical (Shallice’s) version of the problem, which consists of $3$ balls and $3$ pegs (of heights 1, 2, 3, respectively), which turns out to be planar and contains a Hamiltonian path, but is not Hamiltonian. After that, we take a look at the graph of the generalized Tower of London with n balls and p pegs. We prove that such a graph is connected if and only if the balls can be rearranged in a way that the tallest peg remains empty. Furthermore, we find that only the problems with two balls (and some of those with three balls) have planar graphs. In this article, we also take a look at a special case of the Tower of London called the Tower of Oxford, where all the pegs are of the same height n. We prove an explicit formula to calculate the number of vertices and edges of the Oxford graph for all n and p.