/* Given: 15 peg piece triangle game board as show:
 *
 *                                    1
 *
 *                                 2     3
 *
 *                              4     5     6
 *
 *                           7     8     9     10
 *
 *                        11    12    13    14    15
 *
 *
 *  Quest: Write a computer program to solve this triangle puzzle.
 *  Rules: Start with a single peg piece removed and jump peg pieces until a single peg piece remains.
 *
 *  by: Gary Argraves - 2006.6.27
 *
 *  compile using Linux command: cc tri_puz.c
 *  then run using Linux command: ./a.out
 *
**/
#include <stdio.h>

const int Jump_possibilities[16][4] = {   // Jumps possibilities
    {0,0,0,0},  // 0 not used
    {2,3,0,0},  // 1            1: 2,3
    {4,5,0,0},  // 2            2: 4,5
    {6,5,0,0},  // 3            3: 6,5
    {2,7,5,8},  // 4            4: 2,7,5,8
    {8,9,0,0},  // 5            5: 8,9
    {3,10,5,9}, // 6            6: 3,10,5,9
    {4,8,0,0},  // 7            7: 4,8
    {5,9,0,0},  // 8            8: 5,9
    {5,8,0,0},  // 9            9: 5,8
    {6,9,0,0},  // 10          10: 6,9
    {7,12,0,0}, // 11          11: 7,12
    {8,13,0,0}, // 12          12: 8,13
    {12,14,8,9},// 13          13: 12,14,8,9
    {13,9,0,0}, // 14          14: 13,9
    {10,14,0,0} // 15          15: 10,14
};

const int Jump_landings[16][4] = {
    {0,0,0,0},  // 0 not used
    {4,6,0,0},  // 1
    {7,9,0,0},  // 2
    {10,8,0,0}, // 3
    {1,11,6,13},// 4
    {12,14,0,0},// 5
    {1,15,4,13},// 6
    {2,9,0,0},  // 7
    {3,10,0,0}, // 8
    {2,7,0,0},  // 9
    {3,8,0,0},  // 10
    {4,13,0,0}, // 11
    {5,14,0,0}, // 12
    {11,15,4,6},// 13
    {12,5,0,0}, // 14
    {6,13,0,0}  // 15
};

//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
void print_board( char *b0, char jumper, char jumpee, char landing, char progress )
{
  char b[16];
  char i;
  for (i=0; i<sizeof(b); i++) b[i] = b0[i] ? 'o': '.';  // copy board;

  printf("MOVE No %d\n", progress);

  b[jumper]  = '1';
  b[jumpee]  = '2';
  b[landing] = '3';

  printf("            %c\n",                            b[1]);
  printf("         %c     %c\n",                     b[2], b[3]);
  printf("      %c     %c     %c\n",               b[4], b[5], b[6]);
  printf("   %c     %c     %c     %c\n",        b[7], b[8], b[9], b[10]);
  printf("%c     %c     %c     %c     %c\n", b[11], b[12], b[13], b[14], b[15]);
  printf("\n");


  b[jumper]  = '.';
  b[jumpee]  = '.';
  b[landing] = 'o';

  printf("\t\t\t            %c\n",                            b[1]);
  printf("\t\t\t         %c     %c\n",                     b[2], b[3]);
  printf("\t\t\t      %c     %c     %c\n",               b[4], b[5], b[6]);
  printf("\t\t\t   %c     %c     %c     %c\n",        b[7], b[8], b[9], b[10]);
  printf("\t\t\t%c     %c     %c     %c     %c\n", b[11], b[12], b[13], b[14], b[15]);
  printf("\n");

  if (progress==13) printf("   *** DONE / SOLVED ***\n");

}//print_board

// statistics use to terminate recursion
int move_call=0;
int move_take_back=0;

//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
char make_move( char *b ) // returns true if move made
{ char i,j;
  int mc, mt;
  char move_made;
  char board[16]; // copy board on recursive stack.

  move_made = 0;
  for (i=0; i<sizeof(board); i++) board[i]=b[i]; // get/copy board
  if ( (move_call - move_take_back) == 13 ) // test progress to see if all done
  { // done
     return 1;
  }

  move_call++; // global move calls
  mc = move_call;
  mt = move_take_back;

  /**** make move ****/
  for (i=1; i<16; i++) // loop to find a peg that can jump something.
  {
    if ( board[i] ) // test if a peg is in board position 'i'
    { // got a peg to serve as the 'jumper' peg.
      // now find a valid jump

      // see if a neighbor peg is in place to be jumped
      for (j=0; j<4; j++) // loop on 4 possible neighbor pegs/jummpees; in most cases there are only 2 neighbors/jumpees
      {
         /* analyize jump case [i,j] to see if a jump is possible */
         if ( Jump_possibilities[i][j] // ignore '0' case possibities, indicating end of jump list.
           &&  board[ Jump_possibilities[i][j] ] // test if the 'jumpee' is on board
           && !board[ Jump_landings[i][j] ] )   // test if the landing area is clear.
         { /* OK, got a valid jump case consisting of:
            *   1) a jumper peg    at  board[i]
            *   2) a jumpee peg    at  board[ Jump_possibilities[i][j]
            *   3) a clear landing at  board[ Jump_landings[i][j]
            */

           // make the jump / make 'this' move
           board[i] = 0; // this is the jumper
           board[ Jump_possibilities[i][j] ] = 0; // this is the peg jumped over
           board[ Jump_landings[i][j] ] = 1; // landing
           move_made = 1;

           // make 'next' move
           if ( !make_move( board ) )
           { // could not make another/next move

             // take back the last move / replace the peices
             board[i] = 1; // this was the jumper
             board[ Jump_possibilities[i][j] ] = 1; // this was the peg jumped over
             board[ Jump_landings[i][j] ] = 0; // landing
             move_made = 0;
             move_take_back++;
             // try the next succesive move in i,j loop logic.
           }//if no move

           if (move_made)
           { printf("\n--------------------------------------------------------------------------\n");
             print_board( board, i, Jump_possibilities[i][j], Jump_landings[i][j], mc-mt ); // allow print_board to highlight move
             printf("move_calls=%d move_take_backs=%d progress=%d\n", mc, mt, mc-mt);
             return 1;
           }
         }//if land clr
      }//for j
    }//if jumper
  }//for i

  return move_made;
}//move

//* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
int main(void)
{ int i;
  char board[16] =
  { 0, // not used must be set to zero for test logic
        1,              // 1
       1,1,             // 2,3
      1,1,1,            // 4,5,6
     1,1,1,1,           // 7,8,9,10
    1,1,1,1,1           // 11,12,13,14,15
  };

  // remove_start_peg
  printf("\n");
  printf("Triangle puzzle solution by: Gary Argraves - 2006.6.27\n");
  printf("\n");
  printf("Given: 15 peg piece triangle game board as show:\n");
  printf("Rules: Start with a single peg piece removed and jump peg pieces until a single peg piece remains.\n\n");

  printf("\n");
  printf("                                     1\n");
  printf(" \n");
  printf("                                  2     3\n");
  printf(" \n");
  printf("                               4     5     6\n");
  printf(" \n");
  printf("                            7     8     9     10\n");
  printf(" \n");
  printf("                         11    12    13    14    15\n");
  printf("\n");
  printf("Which peg do you want to remove to start the puzzle game (1-15) ? ");
  scanf("%d",&i);
  board[i]=0;

  // make first move
  make_move( board ); // pass entire board to move maker

  printf("\n--------------------------------------------------------------------------\n");
  print_board( board,0,0,0,0 ); // print start board
  return 1; //ok
}//main

/*** end of file ***/