For $N$ disks the state-space consists of $\frac{(N+2)!}{2!}$ vertices.
These are the results from exhaustive search:
| Disks |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| Diameter |
1 |
4 |
7 |
10 |
13 |
16 |
19 |
22 |
26 |
29 |
This disproves the assumption of Diameter: $3N-2$
Examples of states which would require more steps to solve:
N=9, Steps=26, State: 3rd peg: 0 7 8 5 6 3 4 1 2
N=10, Steps=29, State: 3rd peg: 0 8 7 9 5 6 3 4 1 2
(In this representation, the desired end-state is: 1st peg: 0 1 2 ...)
The results were produced by the following code. It walks through the state-space in a Breadth-First Search manner, from the desired state, thus computes the minimal number of steps required to reach the desired state from all other states:
#include <deque>
#include <array>
#include <iostream>
#include <set>
#include <string>
#include <sstream>
#include <utility>
#ifndef DISKS
#define DISKS 1
#endif
const int Size = DISKS;
const int ArraySize = Size + 2;
typedef std::array<char, ArraySize> Hanoi;
// representation:
// 0. peg starts at: array[2]
// 1. peg starts at: array[array[0]]
// 2. peg starts at: array[array[1]]
Hanoi init() {
Hanoi result;
result[0] = ArraySize;
result[1] = ArraySize;
for (int i = 0; i < Size; i++) {
result[2+i] = i;
}
return result;
}
Hanoi move_0_1(const Hanoi& h) {
Hanoi result;
int idx = 2;
result[0] = h[0]-1;
result[1] = h[1];
for (int i = 2; i < h[0]-1; i++) {
result[idx++] = h[i];
}
for (int i = h[0]; i < h[1]; i++) {
result[idx++] = h[i];
}
result[idx++] = h[h[0]-1];
for (int i = h[1]; i < ArraySize; i++) {
result[idx++] = h[i];
}
return result;
}
Hanoi move_0_2(const Hanoi& h) {
Hanoi result;
int idx = 2;
result[0] = h[0]-1;
result[1] = h[1]-1;
for (int i = 2; i < h[0]-1; i++) {
result[idx++] = h[i];
}
for (int i = h[0]; i < h[1]; i++) {
result[idx++] = h[i];
}
for (int i = h[1]; i < ArraySize; i++) {
result[idx++] = h[i];
}
result[idx++] = h[h[0]-1];
return result;
}
Hanoi move_1_0(const Hanoi& h) {
Hanoi result;
int idx = 2;
result[0] = h[0]+1;
result[1] = h[1];
for (int i = 2; i < h[0]; i++) {
result[idx++] = h[i];
}
result[idx++] = h[h[1]-1];
for (int i = h[0]; i < h[1]-1; i++) {
result[idx++] = h[i];
}
for (int i = h[1]; i < ArraySize; i++) {
result[idx++] = h[i];
}
return result;
}
Hanoi move_1_2(const Hanoi& h) {
Hanoi result;
int idx = 2;
result[0] = h[0];
result[1] = h[1]-1;
for (int i = 2; i < h[0]; i++) {
result[idx++] = h[i];
}
for (int i = h[0]; i < h[1]-1; i++) {
result[idx++] = h[i];
}
for (int i = h[1]; i < ArraySize; i++) {
result[idx++] = h[i];
}
result[idx++] = h[h[1]-1];
return result;
}
Hanoi move_2_0(const Hanoi& h) {
Hanoi result;
int idx = 2;
result[0] = h[0]+1;
result[1] = h[1]+1;
for (int i = 2; i < h[0]; i++) {
result[idx++] = h[i];
}
result[idx++] = h[ArraySize-1];
for (int i = h[0]; i < h[1]; i++) {
result[idx++] = h[i];
}
for (int i = h[1]; i < ArraySize-1; i++) {
result[idx++] = h[i];
}
return result;
}
Hanoi move_2_1(const Hanoi& h) {
Hanoi result;
int idx = 2;
result[0] = h[0];
result[1] = h[1]+1;
for (int i = 2; i < h[0]; i++) {
result[idx++] = h[i];
}
for (int i = h[0]; i < h[1]; i++) {
result[idx++] = h[i];
}
result[idx++] = h[ArraySize-1];
for (int i = h[1]; i < ArraySize-1; i++) {
result[idx++] = h[i];
}
return result;
}
std::pair<Hanoi, int> bfs_path() {
std::pair<Hanoi, int> result = std::make_pair(init(), 0);
std::set<Hanoi> states;
std::deque<std::pair<Hanoi, int>> queue;
queue.push_back(std::make_pair(init(), 0));
while (!queue.empty()) {
auto current = queue.front().first;
auto path_len = queue.front().second;
if (path_len > result.second) {
result = queue.front();
}
queue.pop_front();
Hanoi state;
if (current[0] > 2) {
state = move_0_1(current);
if (states.insert(state).second) {
queue.push_back(std::make_pair(state, path_len+1));
}
state = move_0_2(current);
if (states.insert(state).second) {
queue.push_back(std::make_pair(state, path_len+1));
}
}
if (current[1] > current[0]) {
state = move_1_0(current);
if (states.insert(state).second) {
queue.push_back(std::make_pair(state, path_len+1));
}
state = move_1_2(current);
if (states.insert(state).second) {
queue.push_back(std::make_pair(state, path_len+1));
}
}
if (ArraySize > current[1]) {
state = move_2_0(current);
if (states.insert(state).second) {
queue.push_back(std::make_pair(state, path_len+1));
}
state = move_2_1(current);
if (states.insert(state).second) {
queue.push_back(std::make_pair(state, path_len+1));
}
}
}
std::cout << "Visited states: " << states.size() << std::endl;
return result;
}
std::string to_string(const Hanoi& h) {
std::stringstream ss;
for (int i = 2; i < h[0]; i++) {
ss << (int)h[i] << " ";
}
ss << "| ";
for (int i = h[0]; i < h[1]; i++) {
ss << (int)h[i] << " ";
}
ss << "| ";
for (int i = h[1]; i < ArraySize; i++) {
ss << (int)h[i] << " ";
}
return ss.str();
}
int main() {
auto result = bfs_path();
std::cout << "Max steps needed: " << result.second << " For State: " << to_string(result.first) << std::endl;
}
It is recommended to compile it with the best optimization, e.g.:
g++ hanoi.cpp -D DISKS=8 -std=c++11 -O3 -o hanoi && ./hanoi
No, it is not necessarily possible.
Suppose there is an odd face $F$, such that each adjacent face is a square, so you cannot subdivide edges of $F$. Then you are asking to add inside $F$ an arbitrary planar graph $H$, such that $F + H$ is bipartite. In $F + H$, the outer face is odd, while any inner face is even. Thus its dual graph has exactly one odd-degree vertex, which is impossible.
Best Answer
I will address your first question, but not the one for larger number of rods; as far as I know, it's still generally wide open what the optimal strategy might be even for $4$ rods and a smallish number of disks.
To show the optimal strategy for $n$ disks in $3$ rods is the "usual" one, you can do it by induction (which yields a recursive solution). I'm sure there are other ways of proving it, perhaps with Lucas numbers as you suggest.
Clearly, the optimal strategy with $n=1$ is to simply move the disk directly.
Assume you already have the optimal strategy for moving $k$ disks. To move $k+1$ disks, you need to move the largest disk from the initial rod to the terminal rod, but that is the only time it needs to move (it cannot help you with the other disks, since it must lie at the bottom at any given time, so any other moves only require further moves in the end); to move the bottom ($k+1$)st disk from the initial rod $I$ to the terminal rod $T$, you must first move the top $k$ disks out of the way; this requires moving the $k$ disks from the initial rod $I$ to the auxiliary rod $A$, and the optimal way of doing this is the optimal strategy you know for $k$ disks. Then you move the $k+1$st disk, and then you want to move the remaining $k$ disks from the auxiliary rod to the terminal one in as few moves as possible (the optimal way). So the optimal strategy for $k+1$ disks is to move the top $k$ using the optimal strategy for $k$ from $I$ to $A$, then move the largest disk from $I$ to $T$, then move the top $k$ disks using the optimal strategy for $k$ from $A$ to $T$.
By keeping track of the actual number of moves needed at each step, you can give the number. For $n=1$, the number is $1=2^1-1$. Assume that moving $k$ disks requires $2^k-1$ moves in the optimal strategy. The optimal strategy for $k+1$ described above takes $(2^k-1) + 1 + (2^k-1) = 2^k+2^k - 1 = 2^{k+1}-1$ steps; thus, the optimal solution for $n$ disks and $3$ rods requires $2^n-1$ moves.
(This does not generalize easily to more than $3$ rods for presumably obvious reasons).
A bit more interesting is trying to prove that the non-recursive solution gives an optimal solution; this solution only requires you to remember the last disk you moved at any given time (the recursive solution is more memory intensive, of course). Number the rods $0$, $1$, and $2$. We have three rules:
With these rules, the non-recursive algorithm has two simple steps:
This process will solve the puzzle with $3$ rods in the minimum number of moves.