I'm trying to solve the Hanoi problem using an iterative method. I try to do this by using two for nested loops, so as to repeat n - 1 steps in each loop, where n is the number of moves. I think I have well posed the problem by using two for, but I don't understand how to change the order of the towers at each pass. Can anyone help me with this task?
inizio is start, fine is end and supp is support
#include <stdlib.h>
#include <stdio.h>
void tower_Organizer(int *inizio, int *fine, int *supp);
void hanoi_Iter(int n, int inizio, int fine, int supp);
int main(void){
int n;
printf("%s\n" ,"inserisci un nuero positivo");
scanf("%d", &n);
hanoi_Iter(n, 1, 2, 3);
return 0;
}
void hanoi_Iter(int n, int inizio, int fine, int supp){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= i - 1 ; j++){
printf("%d -> %d\n", inizio, fine);
tower_Organizer(&inizio, &fine, &supp);
}
printf("%d -> %d\n", inizio, fine);
tower_Organizer(&inizio, &fine, &supp);
}
}
void tower_Organizer(int *inizio, int *fine, int *supp){
static int count = 1;
int c = count % 6;
switch( c ){
case 0:
*inizio = 1;
*fine = 2;
*supp = 3;
break;
case 1:
*inizio = 1;
*fine = 3;
*supp = 2;
break;
case 2:
*inizio = 2;
*fine = 3;
*supp = 1;
break;
case 3:
*inizio = 1;
*fine = 2;
*supp = 3;
break;
case 4:
*inizio = 3;
*fine = 1;
*supp = 2;
break;
case 5:
*inizio = 3;
*fine = 2;
*supp = 1;
break;
}
count++;
}
The number of moves is 2𝑛−1, so the nested loop you have cannot achieve that, as it will only produce 𝑛(𝑛+1)/2 moves.
The logic for which disc to move is also not as simple as a cycle of 6 distinct moves.
There are several ways to implement an iterative solution, some of which are explained on Wikipedia. However, the ones that are listed there, require that you maintain the state of each peg (pile), so you can perform checks on what constitutes a valid move.
You can also look at the bit-pattern of the move's sequence number and derive from that which is the correct move.
Here is an implementation of that latter idea:
void hanoi(int n, int start, int end, int helper) {
// Create a converter for a pile index (0, 1 or 2) to the identifiers
// that are given as arguments:
int map[] = {start, end, helper};
// Perform as many iterations as there are moves to perform:
for (int last = 1<<n, i = 1; i < last; i++) {
// Use bit pattern of i to determine the source peg.
// First remove and count the trailing 0 bits in i:
int j = i;
int zeroCount = 0;
while (j % 2 == 0) {
j >>= 1;
zeroCount++;
}
// Derive the source pile from that zero-stripped number
int source = (j >> 1) % 3;
// Get next pile as destination
int target = (source + 1) % 3;
// Depending on parity, the source/target pile should be mirrored
if ((n + zeroCount) % 2 == 0) {
source = (3 - source) % 3;
target = (3 - target) % 3;
}
printf("Move from %d to %d\n", map[source], map[target]);
}
}
int main(void) {
int n;
printf("%s\n" ,"Enter a positive number (of discs)");
scanf("%d", &n);
hanoi(n, 1, 2, 3);
return 0;
}