pith. sign in

arxiv: 2208.06705 · v1 · submitted 2022-08-13 · 💻 cs.DM

The weighted Tower of Hanoi

El-Mehdi Mehiri , Hac\`ene Belbachir This is my paper

Pith reviewed 2026-05-24 11:50 UTC · model grok-4.3

classification 💻 cs.DM
keywords weighted Tower of Hanoidynamic programmingminimum costoptimal substructuremove restrictionsTower of Hanoi variants
0
0 comments X

The pith

The weighted Tower of Hanoi admits an optimal dynamic programming algorithm that finds the minimum-total-cost sequence of moves under arbitrary positive weights on each peg pair.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper generalizes the classic Tower of Hanoi by attaching a positive real weight w_ij to every move of any disc from peg i to peg j, replacing the goal of fewest moves with the goal of lowest total cost. It shows that the resulting problem possesses an optimal substructure, so the minimum cost for moving n discs can be assembled from minimum costs for smaller subproblems. The same framework recovers known results for move-restricted variants by suitable choice of the weights. A reader would care because the construction supplies a practical computational method for any instance in which different transfers carry different costs.

Core claim

The weighted Tower of Hanoi, in which each move between pegs i and j carries a fixed positive real cost w_ij, possesses an optimal substructure that permits a dynamic programming algorithm to compute the exact minimum-cost solution; the same algorithm also establishes relations to Tower of Hanoi problems defined by move restrictions.

What carries the argument

The dynamic programming recurrence that builds the minimum-cost solution for n discs from the minimum-cost solutions of strictly smaller subproblems on the same weighted peg graph.

If this is right

  • The minimum cost for transferring n discs is obtained by combining optimal sub-solutions for fewer discs or for subsets of the pegs.
  • Any move-restricted Tower of Hanoi variant arises as a special case by setting the forbidden moves to infinite weight.
  • The algorithm returns both the minimum cost value and at least one sequence that achieves it.
  • The same recurrence works for any positive real weights, including asymmetric and zero weights.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The weighted model supplies a uniform way to compare the difficulty of different move-restriction rules by measuring how much each restriction increases the minimum cost.
  • Because the weights are arbitrary, the same code can be reused for scheduling problems whose transfer costs depend on distance or energy.
  • If the weights satisfy the triangle inequality, the optimal solution may never move a disc directly between non-adjacent pegs; this is a testable structural prediction.
  • The recurrence depth is linear in the number of discs, so the method remains practical for moderate n even when the number of pegs grows.

Load-bearing premise

The weighted problem admits an optimal substructure that lets the global minimum cost be assembled from the minima of smaller subproblems.

What would settle it

For any small fixed instance (three discs, three pegs, concrete numerical weights), run the dynamic algorithm, then enumerate every legal sequence of moves by exhaustive search and check whether any sequence has strictly lower total cost.

Figures

Figures reproduced from arXiv: 2208.06705 by El-Mehdi Mehiri, Hac\`ene Belbachir.

Figure 1
Figure 1. Figure 1: The weighted movement digraph It is easy to see that the optimal solution is not necessarily unique, for example, if we take the costs as follows w13 = w12 + w23 then the problem of transferring a tower of a single disc n = 1 located on peg 1 towards peg 3, have two optimal solutions with the same cost w13 = w12 + w23, but they differ by the 2 [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The structure of the search tree. it suffices to notice that any solution of this problem must have a number of moves between the number of moves of these two solutions, which are 2 n − 1 and 3 n − 1 respectively. Let vn denote the number of sub-problems needed to be solved by algorithm WTHD to solve the weighted Tower of Hanoi of n discs with two arbitrary source and destination pegs. According to relatio… view at source ↗
Figure 3
Figure 3. Figure 3: Strongly connected digraphs on three vertices [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
read the original abstract

The weighted Tower of Hanoi is a new generalization of the classical Tower of Hanoi problem, where a move of a disc between two pegs $i$ and $j$ is weighted by a positive real $w_{ij}\geq 0$. This new problem generalizes the concept of finding the minimum number of moves to solve the Tower of Hanoi, to find a sequence of moves with the minimum total cost. We present an optimal dynamic algorithm to solve the weighted Tower of Hanoi problem, we also establish some properties of this problem, as well as its relation with the Tower of Hanoi variants that are based on move restriction.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces the weighted Tower of Hanoi problem in which each move of a disk from peg i to peg j incurs a positive real cost w_ij. The goal is to compute a minimum-total-cost sequence transferring n disks from a source peg to a target peg. The central claim is that an optimal dynamic-programming algorithm exists for this problem; the paper also derives some structural properties and relates the weighted variant to move-restriction versions of the Tower of Hanoi.

Significance. A correctly proven optimal DP algorithm would supply the first polynomial-time solution for a natural cost-generalization of the classic problem and could serve as a template for other weighted puzzle problems. The connections drawn to move-restriction variants are potentially useful for cross-fertilization between the two literatures. No machine-checked proofs, reproducible code, or parameter-free closed-form results are reported.

major comments (2)
  1. [§3] §3 (Dynamic Programming Algorithm): the optimality claim rests on the assertion that the weighted problem possesses optimal substructure, yet no recurrence relation, state-space definition, or inductive argument is supplied showing that an optimal solution for n disks is assembled exclusively from optimal solutions of strictly smaller subproblems for arbitrary w_ij > 0. The standard Bellman decomposition used for unit-cost ToH can fail when cheap edges allow globally optimal sequences that employ locally suboptimal placements.
  2. [Theorem 4.1] Theorem 4.1 (or the main optimality theorem): the proof sketch only verifies correctness on the classical unit-weight instance and on a small set of hand-crafted weight matrices; it does not address the general case in which an optimal path may exploit non-monotonic disk movements or temporary placements that violate the usual “move smallest disk only when necessary” rule.
minor comments (2)
  1. [Abstract] The abstract states “we present an optimal dynamic algorithm” without indicating the time complexity or the precise state space; this information should appear in the abstract or the first paragraph of §3.
  2. [§2] Notation for the weight matrix w_ij is introduced without an explicit statement that w_ii = ∞ or that the matrix is symmetric; both conventions should be fixed in §2.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and the detailed comments. Below we respond point by point to the two major concerns. We will revise the manuscript to strengthen the presentation of the dynamic-programming formulation and its proof of optimality.

read point-by-point responses

  1. Referee: [§3] §3 (Dynamic Programming Algorithm): the optimality claim rests on the assertion that the weighted problem possesses optimal substructure, yet no recurrence relation, state-space definition, or inductive argument is supplied showing that an optimal solution for n disks is assembled exclusively from optimal solutions of strictly smaller subproblems for arbitrary w_ij > 0. The standard Bellman decomposition used for unit-cost ToH can fail when cheap edges allow globally optimal sequences that employ locally suboptimal placements.

    Authors: We agree that §3 would benefit from an explicit recurrence, a precise state-space definition, and an inductive argument that holds for arbitrary positive weights. The manuscript already defines states by the positions of the n disks and computes minimum-cost tables bottom-up, but the current text does not spell out the recurrence or prove that every optimal solution is assembled from optimal sub-solutions. We will add the missing recurrence (minimum cost to move the top k disks from configuration A to configuration B) together with a short induction on k that accounts for all possible placements of the largest disk among the three pegs. This will also address the possibility that cheap edges produce non-standard sequences. revision: yes

  2. Referee: [Theorem 4.1] Theorem 4.1 (or the main optimality theorem): the proof sketch only verifies correctness on the classical unit-weight instance and on a small set of hand-crafted weight matrices; it does not address the general case in which an optimal path may exploit non-monotonic disk movements or temporary placements that violate the usual “move smallest disk only when necessary” rule.

    Authors: The existing proof sketch of Theorem 4.1 proceeds by induction on the number of disks and enumerates the possible moves of the largest disk, but it is indeed written at a high level and relies on verification for the unit-cost case plus a few example matrices. We will expand the proof to cover arbitrary positive weights explicitly, showing that the dynamic program considers every feasible sequence of moves of the largest disk (including those that produce non-monotonic or temporarily “suboptimal” placements of smaller disks) and that the subproblem costs are themselves optimal by the induction hypothesis. No assumption of monotonicity is required. revision: yes

Circularity Check

0 steps flagged

No circularity detected; derivation self-contained

full rationale

The paper presents a dynamic programming algorithm for the weighted Tower of Hanoi problem, asserting optimality via optimal substructure and relations to move-restriction variants. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citation chains appear in the abstract or described claims. The result does not reduce to its inputs by construction; it applies standard DP to a generalized problem with the substructure property taken as given rather than derived circularly from the algorithm itself. This is a normal non-finding for an algorithmic paper without visible self-referential reductions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters or invented entities are introduced; the work relies on the standard Tower of Hanoi rules and the assumption that the state space possesses optimal substructure for dynamic programming.

axioms (1)
  • domain assumption Standard Tower of Hanoi rules: single disk moved at a time and no larger disk on smaller one.
    The weighted problem is defined as a direct extension of the classical rules.

pith-pipeline@v0.9.0 · 5622 in / 1011 out tokens · 23520 ms · 2026-05-24T11:50:19.315177+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    The application o f hanoi towers game in logistics manage- ment

    José Alberto Hernández Aguilar, Augusto Renato Pérez Ma yo, Santiago Yip Ortuño, Alberto Ochoa- Zezzatti, and Julio César Ponce Gallegos. The application o f hanoi towers game in logistics manage- ment. In Handbook of Research on Military, Aeronautical, and Mariti me Logistics and Operations , pages 422–433. IGI Global, 2016

    work page 2016

  2. [2]

    Tracing problem solving in real time: fmri analysis of the subject-paced tower of hanoi

    John R Anderson, Mark V Albert, and Jon M Fincham. Tracing problem solving in real time: fmri analysis of the subject-paced tower of hanoi. Journal of cognitive neuroscience , 17(8):1261–1274, 2005

    work page 2005

  3. [3]

    The cyclic towers of hanoi

    MD Atkinson. The cyclic towers of hanoi. Information Processing Letters, 13(3):118–119, 1981. 9

    work page 1981

  4. [4]

    The Canterbury Puzzles

    Henry Ernest Dudeney. The Canterbury Puzzles . Courier Corporation, 2002

    work page 2002

  5. [5]

    The eff ect of mode of presentation on tower of hanoi problem solving

    Madison Fansher, Priti Shah, and Sébastien Hélie. The eff ect of mode of presentation on tower of hanoi problem solving. Cognition, 224:105041, 2022

    work page 2022

  6. [6]

    Solution to advanced problem 39 18

    James Sutherland Frame. Solution to advanced problem 39 18. Amer. Math. Monthly , 48:216–217, 1941

    work page 1941

  7. [7]

    Pil e problems and their mathematical treatment

    Lorenz Hempel, Roland Schmiedel, and Lutz Kämmerer. Pil e problems and their mathematical treatment. In Perspectives on Operations Research, pages 257–276. Springer, 2006

    work page 2006

  8. [8]

    The tower of hanoi myths and maths, 2018

    Andreas M Hinz, Sandi Klavar, and Ciril Petr. The tower of hanoi myths and maths, 2018

    work page 2018

  9. [9]

    A mathematical model and a computer tool for the tower of hanoi and tower of lo ndon puzzles

    Andreas M Hinz, Anton Kostov, Fabian Kneißl, Fatma Sürer , and Adrian Danek. A mathematical model and a computer tool for the tower of hanoi and tower of lo ndon puzzles. Information Sciences, 179(17):2934–2947, 2009

    work page 2009

  10. [10]

    Récréations mathématiques , volume 2

    Édouard Lucas. Récréations mathématiques , volume 2. Gauthier-Villars et fils, 1883

    work page

  11. [11]

    The tower of hanoi with forbidden moves

    Amir Sapir. The tower of hanoi with forbidden moves. The Computer Journal , 47(1):20–24, 2004

    work page 2004

  12. [12]

    Variations on the four-post tower of hanoi puzzle

    Paul K Stockmeyer. Variations on the four-post tower of hanoi puzzle. In Congress. Numer., volume 102, pages 3–12, 1994

    work page 1994

  13. [13]

    The towers of Brahma and Hanoi revisited

    Derick Wood. The towers of Brahma and Hanoi revisited . Unit for computer Science, McMaster University, 1980. 10

    work page 1980