11
$\begingroup$

Recently, I came across this problem, a variation of towers of hanoi.

Problem statement:

Consider the folowing variation of the well know problem Towers of Hanoi:

We are given $n$ towers and m disks of sizes $1,2,3,\dots,m$ stacked on some towers. Your objective is to transfer all the disks to the $k^{\text{th}}$ tower in as few moves as you can manage, but taking into account the following rules:

  • moving only one disk at a time,
  • never moving a larger disk one onto a smaller one,
  • moving only between towers at distance at most $d$.

(Limits in the original problem: $3 \le n \le 1000$ and $m \le 100$. Number of test cases $\le 1000$. You can assume that all the problems can be solved in not more than $20000$ moves.)

It's an interesting one. The classic towers of hanoi problem has one source, destination and temporary tower that is used to move the disks from source to destination. The problem pitched on that site basically has an initial and final configuration.

How does one approach this problem?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ Would you be able to write the problem out in the question, so that the question stands alone from the link? $\endgroup$
    – Luke Mathieson
    Apr 26, 2013 at 7:29
  • 2
    $\begingroup$ Also, what have you tried? Are you familiar with solutions to the original problems, and have you tried to adapt them? $\endgroup$
    – Raphael ♦
    Apr 26, 2013 at 9:53
  • 3
    $\begingroup$ If you look at how it is scored, it is likely that even the problem poser has likely only come up with heuristics/approximation algorithms, rather than an exact algorithm. And if you look at the best solution, there are scores $\gt 500$ (no more than $1000$ test cases), which implies people did better than the problem poser on at least some of the test cases. $\endgroup$
    – Aryabhata
    Apr 26, 2013 at 15:31
  • $\begingroup$ If you forget the restriction of distance at most d, then this seems to me the same as Reve's puzzle which has the unproven Frame–Stewart algorithm solution all described in this wiki page. Intuitively, adding this restriction makes makes things even more complicated. $\endgroup$
    – Ciro Santilli OurBigBook.com
    Oct 5, 2013 at 21:10

1 Answer 1

Reset to default
2
$\begingroup$

The most succesful approach to deal with the original version of the Towers of Hanoi is using Pattern Databases (PDBs). The current state of the art is described in "Recent Progress in Heuristic Search: A Case Study of the Four-Peg Towers of Hanoi Problem"

Pattern Databases are an automated means for deriving admissible heuristics which are necessary in order to find optimal solutions (as your problem requires). In the particular case of the Towers of Hanoi, some discs are preserved while others are just ignored. This results in a smaller state space which can then be fully traversed with a backward breadt-first search algorithm. It is traversed with a breadth-first search to derive optimal lengths in this abstract state and it is traversed from the goal node $t$ (i.e., backwards), to ensure that the optimal lengths computed are relative to the goal. Since the abstract space is smaller, these distances are admissible estimates in the original state space.

This said, I would highly recommend using PDBs again for solving this particular problem since "moving only between towers at distance at most $d$" is trivial since pegs are not abstracted, only the discs.

I do not see, indeed, any reason to change the typical approach just in view of this particular constraint.

Hope this helps,

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.