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

• 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);

}