/**************************************************************
*
* Copyright 2005 by Sean Conner.  All Rights Reserved.
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
*
* Comments, questions and criticisms can be sent to: sean@conman.org
*
****************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <assert.h>

#define MAX_JUMP	100

typedef enum
{
  A,
  B,
  C,
  D,
  E,
  F,
  G,
  H,
  I,
  J,
  K,
  L,
  M,
  N,
  O
} Peg;

struct jump
{
  Peg over;
  Peg to;
};

struct move
{
  Peg from;
  Peg over;
  Peg to;
};

struct peg
{
  int         peg;
  size_t      size;
  struct jump moves[4];
};

/**********************************************************/

size_t      g_nmoves;
struct move g_moves[MAX_JUMP];
size_t      g_pegs      = 14;
struct peg  g_board[15] =
{
  { 1 , 2 , { { B , D } , { C , F } } } ,
  { 1 , 2 , { { D , G } , { E , I } } } ,
  { 1 , 2 , { { E , H } , { F , J } } } ,
  { 1 , 4 , { { B , A } , { E , F } , { H , M } , { G , K } } } ,
  { 1 , 2 , { { E , L } , { I , N } } } ,
  { 1 , 4 , { { C , A } , { E , D } , { I , M } , { J , O } } } ,
  { 1 , 2 , { { H , I } , { D , B } } } ,
  { 1 , 2 , { { I , J } , { E , C } } } ,
  { 1 , 2 , { { H , G } , { E , B } } } ,
  { 1 , 2 , { { I , H } , { F , C } } } ,
  { 1 , 2 , { { L , M } , { G , D } } } ,
  { 1 , 2 , { { H , E } , { M , N } } } ,
  { 1 , 4 , { { L , K } , { N , O } , { H , D } , { I , F } } } ,
  { 1 , 2 , { { M , L } , { I , E } } } ,
  { 1 , 2 , { { N , M } , { J , F } } }
};

/********************************************************/

void print_moves(void)
{
  size_t i;
  
  for (i = 0 ; i < g_nmoves ; i++)
    printf("[%c->%c]",g_moves[i].from + 'A',g_moves[i].to + 'A');
  printf("\n");
}

/*********************************************************/

void jump_the_shark(Peg from,Peg over,Peg to)
{
  g_board[from].peg = 0;
  g_board[over].peg = 0;
  g_board[to].peg   = 1;
  g_pegs--;
  
  g_moves[g_nmoves].from = from;
  g_moves[g_nmoves].over = over;
  g_moves[g_nmoves].to   = to;
  g_nmoves++;

  if (g_pegs == 1)
  {
    print_moves();
    exit(EXIT_SUCCESS);
  }
}

/************************************************************/

void shark_the_jump(void)
{
  Peg from;
  Peg over;
  Peg to;

  g_nmoves--;

  from = g_moves[g_nmoves].from;
  over = g_moves[g_nmoves].over;
  to   = g_moves[g_nmoves].to;
  
  g_board[from].peg = 1;
  g_board[over].peg = 1;
  g_board[to].peg   = 0;
  
  g_pegs++;
}

/************************************************************/  

void jump_to(Peg peg,int look)
{
  size_t      i;
  struct jump target;
  Peg         can;
  
  /*------------------------------------------------
  ; if we can be the destination of a jump, so be it
  ;-----------------------------------------------*/

  for (i = 0 ; i < g_board[peg].size ; i++)
  {
    target = g_board[peg].moves[i];
    if (g_board[target.over].peg && g_board[target.to].peg)
    {
      jump_the_shark(target.to,target.over,peg);
      jump_to(target.over,1);
    }
  }
  
  /*------------------------------------------------
  ; we can't be the recipient of a jump, now find one
  ;---------------------------------------------------*/
  
  if (look == 0) return;

  for ( can = peg + 1 ; can != peg ; can++ )
  {
    if (can > O) can = A;
    assert(can != peg);
    if (g_board[can].peg == 0)
      jump_to(can,0);
  }
  
  /*-------------------------------------------------
  ; no candidates ... need to undo our last move and 
  ; resume ... 
  ;-------------------------------------------------*/

  shark_the_jump();
}

/************************************************************************/

int main(int argc,char *argv[])
{
  Peg start;
  
  if (argc == 1)
    start = A;
  else
  {
    start = toupper(argv[1][0]) - 'A';
    if ((start < A) || (start > O))
      start = A;
  }
  
  g_board[start].peg = 0;
  jump_to(start,1);
  printf("no solution\n");
  return(EXIT_SUCCESS);
}