Instantly share code, notes, and snippets.

# Abhishek-dev2/toh_ndisks_ppegs.c Created Nov 18, 2016

Tower of Hanoi problem with n disks and p towers
 #include #include #include #include //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; }