#include

int fromu[20],fromv[20],tou[20],tov[20];
unsigned long branches;
unsigned long nodes;
unsigned long pegs[20];
unsigned long eleg;
int f,g;
FILE *fout;

init_one(board)
int board[9][9];
{
int i,j;

for (i=0; i<9; i++)
for (j=0; j<9; j++)
{board[i][j]=9;
}

for (i=0; i<16; i++)
pegs[i]=0;
}
init_two(board)
int board[9][9];
{
int i,j;

for (i=2; i<7; i++)
for (j=2; j<(9-i); j++)
{board[i][j]=1;
}
}
output(board)
int board[9][9];
{
int i,j;

for (i=2; i<7; i++)
{for (j=2; j<(9-i); j++)
{printf("%d ",board[i][j]);
}
printf("\n");
}
}
copy(source,dest)
int source[9][9],dest[9][9];
{
int i,j;
for (i=0; i<9; i++)
{for (j=0; j<9; j++)
dest[i][j]=source[i][j];
}
}
int chk_moves(board,fromx,fromy,tox,toy)
int board[9][9];
int fromx[20],fromy[20],tox[20],toy[20];
{
int i,j,m;
m = 0;
for (i=2; i<7; i++)
{for (j=2; j<(9-i); j++)
{if (board[i][j]==0 && board[i+1][j]==1 && board[i+2][j]==1)
{m = m+1;
fromx[m]=i+2; fromy[m]=j; tox[m]=i; toy[m]=j;
}
if (board[i][j]==0 && board[i-1][j]==1 && board[i-2][j]==1)
{m = m+1;
fromx[m]=i-2; fromy[m]=j; tox[m]=i; toy[m]=j;
}
if (board[i][j]==0 && board[i][j+1]==1 && board[i][j+2]==1)
{m =m+1;
fromx[m]=i; fromy[m]=j+2; tox[m]=i; toy[m]=j;
}
if (board[i][j]==0 && board[i][j-1]==1 && board[i][j-2]==1)
{m=m+1;
fromx[m]=i; fromy[m]=j-2; tox[m]=i; toy[m]=j;
}
if (board[i][j]==0 && board[i+1][j-1]==1 && board[i+2][j-2]==1)
{m=m+1;
fromx[m]=i+2; fromy[m]=j-2; tox[m]=i; toy[m]=j;
}
if (board[i][j]==0 && board[i-1][j+1]==1 && board[i-2][j+2]==1)
{m=m+1;
fromx[m]=i-2; fromy[m]=j+2; tox[m]=i; toy[m]=j;
}
if (board[i][j]==0 && board[i+1][j+1]==1 && board[i+2][j+2]==1)
{m=m+1;
fromx[m]=i+2; fromy[m]=j+2; tox[m]=i; toy[m]=j;
}
if (board[i][j]==0 && board[i-1][j-1]==1 && board[i-2][j-2]==1)
{m=m+1;
fromx[m]=i-2; fromy[m]=j-2; tox[m]=i; toy[m]=j;
}
}
}
return(m);
}
make_move(board,a,b,c,d)
int a,b,c,d;
int board[9][9];
{
board[a][b]=0;
board[c][d]=1;
board[(a+c)/2][(b+d)/2]=0;
}
answer(layer)
int layer;
{
int i;

for (i=1; i<=layer; i++)
fprintf(fout,"%d%d%d%d",fromu[i]-1,fromv[i]-1,tou[i]-1,tov[i]-1);
fprintf(fout,"\n");
}
solve(layer,move,newboard)
int layer,move;
int newboard[9][9];
{
int fromx[20],fromy[20],tox[20],toy[20];
int oldboard[9][9];
int i,c,s;

copy(newboard,oldboard);
c = chk_moves(newboard,fromx,fromy,tox,toy);
nodes = nodes + 1;
if (c == 0)
{branches = branches + 1;
pegs[14-layer] = pegs[14-layer]+1;
}
if ((branches%100000) == 0)
printf("branches = %d, nodes = %d\n",branches,nodes);
for (i=1; i<=c; i++)
{copy(oldboard,newboard);
make_move(newboard,fromx[i],fromy[i],tox[i],toy[i]);
fromu[layer]=fromx[i]; fromv[layer]=fromy[i];
tou[layer] = tox[i]; tov[layer] = toy[i];
if (layer > 12)
{
if ((f == tou[layer]) && (g == tov[layer]))
eleg = eleg + 1;
answer(layer);
}
s = solve(layer+1,i,newboard);
}
return(0);
}
main()
{
int s,t;
int newboard[9][9],oldboard[9][9];

fout = fopen("cracker4.out","w");

branches = 0; nodes = 0; eleg = 0;

for (f=2; f<7; f++)
{
for (g=2; g<(9-f); g++)
{
init_one(oldboard);
init_two(oldboard);
copy(oldboard,newboard);
newboard[f][g]=0;

s = solve(1,1,newboard);
printf("nodes = %d\n",nodes);
printf("branches = %d\n",branches);
printf("f = %d, g = %d, eleg = %d\n",f,g,eleg);
for (t=0; t<20; t++)
printf("pegs %d = %d\n",t,pegs[t]);

}
}
}