#Arbitrary Tower of Hanoi configuration always solvable proof?

32 messages · Page 1 of 1 (latest)

tranquil lynx
#

how would one prove or disprove that an initial, arbitrary configuration for the towers of hanoi is always/not always solvable?
I mean obviously you can find an example that can't be solved and then run a search algorithm that explores every possible decision and none of the nodes are the solution.
but what if the first impossible configuraton contains 2^5928623 disks and you simply havn't computed it yet and probably won't for the next 6 years?
And how would one go about proving that it is always possible? Usually this kind of stuff works by proof by contradiction, assuming that there is at least one configuration that can't be solved, then do some fancy pancy math nonsense that nobody understands and suddenly you get 42 = sqrt(-16), which is obviously false.

ionic rivetBOT
tranquil lynx
#

One could try to purposefully construct an unsolvable state from intuiton. but that's not very rigorous and if someone asked you how you got there, you can't just say that you pulled it out of your rear end.
Just thinking about it yields to me ordering them upside down and every time you place a disk down you pick the next peg, like that

4 5 6
1 2 3
A B C

but it seems you always have options that are yet unexplored.
you can stack 5 on 6, 4 on 5 and then 2 on 4 and 1 on 2. then you can go back to the recursive algorithm to move 6,5,4 onto B, then 2,1 onto A, then 3 onto the 4 on B. and from there you can solve it as normal.

cosmic lichen
tranquil lynx
#

the only induction i know is induction heating, and induction road sensors... which are actually the same

cosmic lichen
#

It is necessary for the proof

#

If you are not familiar with it, then I'm a little curious on who is asking you to solve this problem

tranquil lynx
#

I'm asking me to solve this problem. I'm a programmer and I thought I'd solve the towers, without recursion. just to toy around with some new c++ 23 features. and then i got bored and thought about it more and then I landed here because I can't figure it out.

#

I see. so for proof by induction we prove that something is true for a case such as if there are n = 4 disks, this is always provable because (simple, foolproof logic here). and for n > 4 we can do (step here that works every time) and it becomes a problem of n - 1. then prove that that step works every time somehow.
still sound like magic and abstract. particularly the last 2 steps.

cosmic lichen
cosmic lichen
tranquil lynx
#

i hate recursion. it's needlessly complicated, slow, blows up the stack for any problem that is non trivial to begin with, ugly to read and hard to debug.

cosmic lichen
#

Wait until you take functional programming KEK

tranquil lynx
#

that's the funny part. I don't ~

cosmic lichen
#

I think it's not so much complicated as it is a different way to think about a problem

#

Some problems have profound solutions when you think of them recursively

tranquil lynx
#

there is no problem that can't be solved iteratively with the correct datastructure.

cosmic lichen
#

False

#

Unless the data structure is a stack

tranquil lynx
#

well a stack is a data strucuture. :P

cosmic lichen
#

Yeah but then you're just doing recursion with your own stack

#

Graph and tree traversal would be ridiculous with iteration

tranquil lynx
#

could use a list for the hanoi problem, too, a stack is not required.
my brain doesn't work that way. I don't mind writing functions of course. but I like building my blocks and sticking them together.
I also still believe that it's ridiculous to use functional programming for general purpose programming tasks like building a website, making a game or writing a program to calculate how many floorboards you need to tile a room, including a nice UI.
It's all math, no utility.
I've written A* with iteration, no problem. in fact, if you use recursion you quickly blow up your stack... again, and also kill your performance.

Anyhow, regardless of how you solve the problem, how does one prove that any tower starting position is solvable, or not?

n=0 makes no sense. n=1 is trivial, it's either solved already or you can solve it with 1 move. How can you prove that n=2 can always be broken down to n=1. well you can of course by moving the larger disk to peg C if it isn't already on the bottom there, maybe you need to move the smaller disk out of the way first, which is also trivial.
and how can we prove that such a reduction from n to n-1 is always possible?

no clue.

cosmic lichen
#

I wrote a compression algorithm a few years ago, and guess what? It used recursion

tranquil lynx
#

I know how to use a hammer. and I know my hammer is turing complete.

cosmic lichen
#

Anyway, I wish you luck. My advice is recursion. If that's not acceptable, then I'll be of no help going forward

tranquil lynx
#

I never asked for a programming solution though. even if I made one, I couldn't be sure if it will find a solution, and if it doesn't if it wouldn't find a solution in 3 years.

#

i might have something...
if there is always a larger disk or empty peg available, then any move you do will be a step towards sorting.
and any number of disks can be moved with the standard hanoi algorithm as long as they are in order.

if i can prove the first point, then any arbitrary starting condition will be solvable.

#

but then again, there being a slot available doesn't mean it's always better sorted than before. you could simply move a disk back and forth endlessly and never get anything done.