New problem idea - Hanoi Depths
Back to General discussions forum
Hanoi Depths
Hey everyone!
I think I have invented an interesting complication to the well-known Tower of Hanoi problem.
As you all may know, this game consists of three rods and a number of disks of different diameters, which are initially stacked on first rod. The goal is to rearrange these disks to third rod, using second rod for intermediate moves.
What I suggest is to replace rods with holes. This will lead to interesting complications because now we need to account hole diameters instead of disk diameters.
For example, lets consider the following position:
______________
-+| |+-+ +-+ +-
|+______________+| | | | |
+--+| |+--+ +--+ +--+ +--+ +--+
|+________+| | | | |
+--+| |+--+ +--+ +--+ +--+ +--+
|+__+| | | | |
+----+ +----+ +----+
Here we have a position which is solved much like standard game, i.e. with sequence:
- 1 -> 3
- 1 -> 2
- 3 -> 2
- 1 -> 3
- 2 -> 1
- 2 -> 3
- 1 -> 3
Which is 7 moves.
However, with the holes like...
______________
-+| |+-+ +-+ +-
|+______________+| | | | |
| | | | | | | |
| +________+ | | | | |
| | | | | | | |
| +__+ | | | | |
+----------------+ +----------------+ +----------------+
...the problem can be solved in just 3 moves:
- 1 -> 3
- 1 -> 3
- 1 -> 3
...and the position:
______________
-+| |+------+ +------+ +-
|+______________+| | | | |
+--+| |+--+ +--+ +--+ +--+ +--+
|+________+| | | | |
+--+| |+--+ +--+ +--+ +--+ +--+
|+__+| | | | |
+----+ +--+ +--+ +----+
| |
+----------+
...have no solution, because the hole in middle is just too small. Only the smallest disk can fit into this hole, but it is not enough to rearrange the disks.
What do you think? I think this may make up an interesting problem.
Also, I suggest the following format of data:
- First line contains two space-separated integers N and H - number of disks and holes respectively.
- Second line contains N values separated by space - the diameters of disks, starting with deepest one and following to the ones which are closer to the surface. The last value is a diameter of disk which is just below the surface.
- Next H lines contains several space-separated values. The first value in each line is D - the depth of hole. It followed with D values which describe the diameters of hole sections. These values are in order from deepest section of hole to the section which is just below the surface.
So, the examples above can be described with following inputs:
3 3
1 2 3
3 1 2 3
3 1 2 3
3 1 2 3
.
3 3
1 2 3
3 3 3 3
3 3 3 3
3 3 3 3
.
3 3
1 2 3
3 1 2 3
4 2 3 2 1
3 1 2 3
Answers should be either number of moves to rearrange the disks, or 0, if it not possible to rearrange the disks.
The answers for examples above are: 7, 3, 0.
Qwerty, Hi!
I'm sorry for being bit out of sync - was changing job again and then on micro-vacations due to wedding anniversary etc, etc.
Thanks for your very detailed explanations - I'll try to ingest this and return with my questions and thoughts!
Sorry that I didn't spot this one earlier. The Tower of Hanoi is a really elegant puzzle and I think it is an excellent idea to consider interesting variations of the original format.
The idea of having holes to hold the discs, together with removal of the restiction of placing discs strictly according to decreasing size, makes a very interesting variation. I would make one suggestion on the shape of the holes. I think that each downwards step into a hole should be either the same width as the step above it or smaller than the step above it. I can see no point in having a hole get wider as you go deeper into it. For holes (other than the leftmost hole) a widening of the hole lower down is clearly unusable. For the leftmost hole such a widening can be used to trap some of the discs. However, this makes the problem trivially impossible without the need to consider any moves; so I don't think it adds anything to the problem.
I notice that you have allowed for the possibility of central holes having different depths from the first and last hole. This is a nice touch. I also note that you have allowed for the possibility of having more than 3 holes. This also increases the scope of the problem but it significantly decreases the minimum number of moves needed to solve the problem. Even with three holes your problems are likely to require significantly fewer moves than the standard Tower of Hanoi problem. It is quite possible that it will become much harder to generate good puzzles than it is to solve them. You may also need to include a large number of discs to achieve a reasonable level of difficulty.
Another possibility that you might like to consider is having several disks of the same size. In conventional Tower of Hanoi this would not require any change to the rules but would mean that discs could be placed on top of discs having the same size or larger. A starting position of 1,2,2,2,2,3,4,4,4,5 represents 10 discs of which there are 4 of size 2 and 3 of size 4. The minimum number of moves is now considerably smaller than 2^10 -1. The problem could be made more interesting by specifying the final order for the discs. For example a, b, c etc. can be used to distinguish discs of equal size. A problem might require the initial stack of 1,2a,2b,2c,2d,3,4a,4b,4c,5 to be transformed into 1,2b,2d,2c,2a,3,4c,4b,4a,5.
Some of these ideas can be incorporated into the problem with holes. You can certainly consider using some discs of equal size and could either fully or partially specify a finishing position in the right-most stack. I still think that creating good puzzles is likely to be harder than solving them (but that isn't necessarily a bad thing).
Friends, Hi!
I'm back again - and I'd say that really this variation is curious one - I wonder how you come to it!
Both the initial idea and considerations by CSFPython make interesting puzzles combined :)
Also the thing seems pretty doable, though creating input datasets looks a bit tricky.
I believe input data should contain more than one "game" - so there will be both solvable and unsolvable variants.
Now the question is only how to generate inputs. The two main approaches are - either there is quick enough generating algorithm (so that you can explain it to me and I will struggle to write it in php) - or alternatively data could be pregenerated offline (with program in any language) - say, a hundred datasets - which then I embed in the checker's code along with expected answer, so that checker just randomly chooses few of them and gives to user.
At the moment I don't have clear idea of input generation, besides making 3 "pits" of random sizes (though the 3rd should be similar to 1st - could be bit wider at some levels - and notion of "non-increasing" width probably should be taken into account) - and then running solving algorithm and recording answer. Are there any better ideas?
P.S. I think we can even add small javascript demo-game to the problem page when it is created :)