Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Tower of Hanoi problem with n disks and p towers
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<limits.h>
//int **table is the table which is storing the no. of moves for dynamic programming
//int **table1 is the table which is storing the best splits for printing the moves
//For calculating the values for the tables, no. of moves table is more useful
//For printing the moves, the best split table is more useful
int n,p,count = 0,**table, **table1, best_split = 1, n_main, p_main, free1 = 0, free2 = 0, free_pegs;
//When only 3 pegs are used, p_equals_3() function will we used(Total moves = 2^n - 1)
void p_equals_3(int source, int destination,int via, int num) {
int i;
//Base condition
if(num == 1)
printf("%d. Move disk from %d to %d\n",++count, source, destination);
//Recursion
else {
p_equals_3(source, via, destination, num - 1);
printf("%d. Move disk from %d to %d\n",++count, source, destination);
p_equals_3(via, destination, source, num - 1);
}
}
//When n < p, n_lessthan_p will be used(Total moves = 2*n - 1)
//No recursion is needed in this function
void n_lessthan_p(int n, int p, int from, int to) {
int i,j = n - 1;
if(from != 1) {
for(i = 1;i <= j;i++) {
if(i != to && i != from && (i < free1 || i > free2))
printf("%d. Move disk from %d to %d\n", ++count, from, i);
else
j++;
}
printf("%d. Move disk from %d to %d\n", ++count, from, to);
i--;
for(;i >= 1;i--)
if(i != to && i != from && (i < free1 || i > free2))
printf("%d. Move disk from %d to %d\n", ++count, i, to);
}
else {
for(i = 2;i <= j + 1;i++) {
if(i != to && (i < free1 || i > free2))
printf("%d. Move disk from %d to %d\n", ++count, from, i);
else
j++;
}
printf("%d. Move disk from %d to %d\n", ++count, from, to);
i--;
for(;i >= 2;i--)
if(i != to && (i < free1 || i > free2))
printf("%d. Move disk from %d to %d\n", ++count, i, to);
}
}
//When n == p, n_equals_p will be used(Total moves = 2*n + 1)
//No recursion is needed in this function
void n_equals_p(int n, int p, int from, int to) {
int i, x = 2;
free2++;
p_equals_3(from, free2, p_main, 2);
n_lessthan_p(n - 2, p - 1, from, to);
p_equals_3(free2, to, from, 2);
free2--;
}
//This function is printing the moves
void moves(int n, int p, int from, int to) {
int free1_aux = free1;
int free2_aux = free2;
//Base condition 1
if(p == 3)
p_equals_3(from, to, to - 1, n);
//Base condition 2
else if(p == n && p > 3)
n_equals_p(n, p, from, to);
//Base condition 3
else if(p > n)
n_lessthan_p(n, p, from, to);
//Printing process when n > p
else if(n > p) {
int i,x = 0,y = 0,min = INT_MAX;
int p_rec = p;
int* robin = (int*)malloc(sizeof(int) * p_rec); //robin[] is storing what best splits we need
//Filling robin
for(i = p_rec - 3;i >= 1;i--) {
x = table1[n - 1][p - 3];
robin[i] = x;
n = n - x;
p--;
}
robin[0] = n;
//Value of n and p have been changed from original value, we cannot use them now
//But for p, we have p_rec which we still can use
//Doing process from from
free2 = p_rec - 2;
free1 = p_rec - 2;
for(i = p_rec - 2;i > 1;i--) {
moves(robin[i - 1], i + 2, from, i);
if(i < free1)
free1 = i;
}
//Assigning the correct value for free1 and free2
for(i = 1;i <= free2;i++,free1++) {
free_pegs = p_rec - (free2 - free1 + 1);
moves(robin[i - 1], free_pegs, i, to);
}
free1 = free1_aux;
free2 = free2_aux;
free(robin);
}
}
int peg_master(int n, int p) {
if((n - p) > (n_main - p_main))
return 0;
//Base condition 1
if(n == 0)
return 0;
//Base condition 2
else if(p == n && p >= 3)
return 2 * n + 1;
//Base condition 3
else if(p > n)
return 2 * n - 1;
//Base condition 4
else if(p == 3)
return (pow(2, n) - 1);
//Recursion happenning here
else if(p > 3) {
int i,x = 0,y = 0,min = INT_MAX;
for(i = 1;i < n;i++) {
if(table[i - 1][p - 3] == INT_MAX) {
x = peg_master(i, p);
table[i - 1][p - 3] = x;
}
if(table[n - i - 1][p - 4] == INT_MAX) {
y = peg_master(n - i, p - 1);
table[n - i - 1][p - 4] = y;
}
y = 2 * table[i - 1][p - 3] + table[n - i - 1][p - 4];
if(y < min) {
min = y;
table[n - 1][p - 3] = y;
table1[n - 1][p - 3] = i;
if(n == n_main && p == p_main)
best_split = i;
}
}
//printf("min = %d\n",min);
return min;
}
}
//This is the driver function
int main() {
int i, j, x, from = 1, to;
//Scanning stuff
printf("Enter n(>= 0) and p(>= 3) : ");
scanf("%d %d",&n,&p);
n_main = n;
p_main = p;
to = p_main;
free_pegs = p_main;
if(p == 3)
best_split = n - 1;
else
best_split = 1;
//Creating table1 array
table = (int**)malloc(sizeof(int*) * n_main);
for(i = 0;i < n_main;i++)
table[i] = (int*)malloc(sizeof(int) * (p_main - 2));
//Creating table2 array
table1 = (int**)malloc(sizeof(int*) * n_main);
for(i = 0;i < n_main;i++)
table1[i] = (int*)malloc(sizeof(int) * (p_main - 2));
//Filling table array with max value
for(i = 0;i < n_main;i++) {
for(j = 0;j < p_main - 2;j++) {
table[i][j] = INT_MAX;
}
}
//Filling table array with max value
for(i = 0;i < n_main;i++) {
for(j = 0;j < p_main - 2;j++) {
if(j != 0)
table1[i][j] = 1;
else
table1[i][j] = i;
}
}
//Calling recursive function
int move = peg_master(n_main, p_main);
//Printing result
printf("Total moves = %d\n", move);
/*
if(n_main >= 0 && p_main >= 3) {
printf("\nMin moves : %d, best split = %d\n\nDynamic Table showing moves for x discs and y pegs(x,y) : \n", move, best_split);
printf("(x, y)->0 means that it is not necessary to fill the table for (x, y).\n");
for(i = 0;i < n_main;i++) {
for(j = 0;j < p_main - 2;j++) {
if(table[i][j] != INT_MAX)
printf("(%d,%d)->%d\t", i + 1, j + 3, table[i][j]);
else
printf("(%d,%d)->0\t",i + 1, j + 3);
}
printf("\n");
}
printf("This table is only made to print the moves, as it is more helpful using this table.");
printf("\n\nDynamic Table showing best splits for x discs and y pegs(x,y) : \n");
for(i = 0;i < n_main;i++) {
for(j = 0;j < p_main - 2;j++) {
if(table1[i][j] != INT_MAX)
printf("(%d,%d)->%d\t", i + 1, j + 3, table1[i][j]);
else
printf("(%d,%d)->0\t",i + 1, j + 3);
}
printf("\n");
}
}
else {
printf("Either n < 0 or p < 3. Please check the value.\n");
return 0;
}
*/
printf("\n\nMOVES : \n");
moves(n_main, p_main, from, to);
printf("Count = %d\n", count);
free(table);
free(table1);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment