#include <iostream>
#include <stdlib.h>

using namespace std;

int ROWS = 0;
int COLS = 3;

//function prototypes
void towers(int, int*[3], int, int, int);
void print(int*[3]); 

int main()
{
   //initialize variables
   int disks = 0;
   int **board;

   //ask how many disks the user wants
   cout << "How many disks would you like to have?: ";
   cin >> disks;

   ROWS = disks;

   board = new int* [disks];

   //initialize board
   for(int k = 0; k < disks; k++)
   {
      board[k] = new int [3];
   }

   //create initial board
   for(int i = 0; i < ROWS; i++)
   {
      for(int j = 0; j < COLS; j++)
      {
	 if(j == 0)
	 {
	    board[i][j] = i + 1;
	 }
	 else
	 {
	    board[i][j] = 0;
	 }
      }
   }

   //print out the initial board
   print(board);

   //call towers function
   towers(disks, board, 0, 1, 2);

   return 0;
}

void towers(int n, int *b[3], int from, int to, int spare)
{
   if(n >=1)
   {
      towers(n-1, b, from, spare, to);

      /*
      for(int l = 0; l < ROWS; l++)
      {
	 if((b[l][to] == 0) && ((b[l-1][to] !=0) || (l == (ROWS-1))))
	 {
	   b[l][to] = n;
	   break;
	 }
      }
      */

      for(int l = (ROWS -1); l >= 0; l--)
      {
	 if((b[l][to] == 0))
	 {
	   b[l][to] = n;
	   break;
	 }
      }
     for(int k = 0; k < ROWS; k++)
     {
	 if(b[k][from] == n)
	 {
	   b[k][from] = 0;
	   break;
	 }
      } 

      //print board
      print(b);

      towers(n-1, b, spare, to, from);
   }
}

void print(int *b[3])
{
   //system("clear");

   for(int i = 0; i < ROWS; i++)
   {
      for(int j = 0; j < COLS; j++)
      {
	 cout << b[i][j];
      }
      cout << endl;
   }
   cout << "---" << endl;
}