Towers of Hanoi
Adapted from NCURSES Programming HOWTO, by Pradeep Padala. The program comes from the HOWTO’s example archive,
JustForFun/hanoi.c, maintained by Thomas E. Dickey.
The famous Towers of Hanoi solver. The aim is to move the discs on the first peg to the last peg, using the middle peg as a temporary stop, without ever placing a larger disc on a smaller one.
The program asks how many discs to solve, then shows each move. Press F1 to stop it.
Example: Towers of Hanoi
#include <stdlib.h>#include <string.h>#include <curses.h>
#define POSX 10#define POSY 5#define DISC_CHAR '*'#define PEG_CHAR '#'#define TIME_OUT 300
#define NUM_PEGS 3
typedef struct _peg_struct { int n_discs; /* Number of discs at present */ int bottomx, bottomy; /* bottom x, bottom y co-ord */ int *sizes; /* The disc sizes array */} peg;
int store_n_discs;const char *welcome_string = "Enter the number of discs you want to be solved: ";
static voidfree_pegs(peg *p_my_pegs){ int i;
for (i = 0; i < NUM_PEGS; ++i) free(p_my_pegs[i].sizes);}
static voidmove_disc(peg *p_my_pegs, int n_discs, int src, int dst){ int temp, index;
--p_my_pegs[src].n_discs; index = 0; while (p_my_pegs[src].sizes[index] == 0 && index != n_discs) ++index; temp = p_my_pegs[src].sizes[index]; p_my_pegs[src].sizes[index] = 0;
index = 0; while (p_my_pegs[dst].sizes[index] == 0 && index != n_discs) ++index; if (--index >= 0) { p_my_pegs[dst].sizes[index] = temp; ++p_my_pegs[dst].n_discs; }}
static voidcheck_usr_response(peg *p_my_pegs){ int ch;
return; else if (ch == KEY_F(1)) { free_pegs(p_my_pegs); exit(EXIT_SUCCESS); }}
static voidinit_pegs(peg *p_my_pegs, int n_discs){ int size, temp, i;
p_my_pegs[0].n_discs = n_discs;
/* Allocate memory for size array * at most the number of discs on a peg can be n_discs */ for (i = 0; i < NUM_PEGS; ++i) { p_my_pegs[i].sizes = (int *) calloc((size_t) n_discs + 1, sizeof(int)); if (p_my_pegs[i].sizes == NULL) { perror("init_pegs"); exit(EXIT_FAILURE); } } size = 3; for (i = 0; i < n_discs; ++i, size += 2) p_my_pegs[0].sizes[i] = size;
temp = (p_my_pegs[0].sizes[n_discs - 1] / 2); p_my_pegs[0].bottomx = POSX + 1 + temp; p_my_pegs[0].bottomy = POSY + 2 + n_discs;
p_my_pegs[1].bottomx = p_my_pegs[0].bottomx + 2 + 2 * temp; p_my_pegs[1].bottomy = POSY + 2 + n_discs;
p_my_pegs[2].bottomx = p_my_pegs[1].bottomx + 2 + 2 * temp; p_my_pegs[2].bottomy = POSY + 2 + n_discs;}
static void{ int i, j, k, x, y, size;
for (i = 0; i < NUM_PEGS; ++i) p_my_pegs[i].bottomx, "%c", PEG_CHAR); y = p_my_pegs[0].bottomy - n_discs; for (i = 0; i < NUM_PEGS; ++i) /* For each peg */ { for (j = 0; j < n_discs; ++j) /* For each row */ { if (p_my_pegs[i].sizes[j] != 0) { size = p_my_pegs[i].sizes[j]; x = p_my_pegs[i].bottomx - (size / 2); for (k = 0; k < size; ++k) } else ++y; } y = p_my_pegs[0].bottomy - n_discs; }}
static voidsolve_hanoi(peg *p_my_pegs, int n_discs, int src, int aux, int dst){ if (n_discs == 0) return; solve_hanoi(p_my_pegs, n_discs - 1, src, dst, aux); move_disc(p_my_pegs, store_n_discs, src, dst); check_usr_response(p_my_pegs); solve_hanoi(p_my_pegs, n_discs - 1, aux, src, dst);}
/* -------------------------------------------------------------* * startx = 0 means at present x * * starty = 0 means at present y * * win = NULL means take stdscr * * -------------------------------------------------------------*/
static voidprint_in_middle(int startx, int starty, int width, const char *string,{ int length, x, y; float temp;
if (win == NULL) if (startx != 0) x = startx; if (starty != 0) y = starty; if (width == 0) width = 80;
length = (int) strlen(string); temp = (float) (width - length) / 2; x = startx + (int) temp;}
intmain(void){ int n_discs; peg my_pegs[NUM_PEGS];
* editing control characters */
store_n_discs = n_discs;
init_pegs(my_pegs, n_discs); solve_hanoi(my_pegs, n_discs, 0, 1, 2);
free_pegs(my_pegs); return EXIT_SUCCESS;}