// Congklak version 1.0
// Coded by Patrick Coston
// Dec 2005
// http://patcoston.com/
// patcoston@gmail.com

#include <iostream>
using namespace std;

int b1[17], b2[17], opposite[8], trymove[101], starthole[3], endhole[3], pocket[3], initmove[100];


__inline int string2int(char* digit) {
   int result = 0;

   // Convert each digit char and add into result.
   while (*digit >= '0' && *digit <='9') {
      result = (result * 10) + (*digit - '0');
      digit++;
   }

   return result;
}

__inline void initmoves()
{
    for (int i=1; i<=99; i++)
        initmove[i] = 1;
}

__inline void setmoves(char *s)
{
    int i, n;
    char num[2];

    n = strlen(s);
    num[1] = 0; // end of string
    for (i=0; i<=(n-1); i++)
    {
        num[0] = s[i];
        initmove[i+1] = string2int(num);
    }
}

__inline void initboard(void)
{
    int i;
    for (i=1;  i<=16; i++)
        b2[i] = b1[i];
}

__inline void setboard(char **s, int n)
{
    int i;

    for (i=1; i<=16; i++)
    {
        b1[i] = string2int(s[n]);
        n++;
    }
}

__inline void initvars(void)
{
    //   7  6  5  4  3  2  1
    // 8                     16
    //   9 10 11 12 13 14 15

    //   7  7  7  7  7  7  7
    // 0                     0
    //   7  7  7  7  7  7  7

    // REM Player 1
    b1[1]  = 7;
    b1[2]  = 7;
    b1[3]  = 7;
    b1[4]  = 7;
    b1[5]  = 7;
    b1[6]  = 7;
    b1[7]  = 7;
    b1[8]  = 0; // pocket for player 1

    // REM Player 2
    b1[9]  = 7;
    b1[10] = 7;
    b1[11] = 7;
    b1[12] = 7;
    b1[13] = 7;
    b1[14] = 7;
    b1[15] = 7;
    b1[16] = 0; // pocket for player 2

    pocket[1] = 8;    pocket[2] = 16;     // pockets for players 1/2
    starthole[1] = 1; endhole[1] = 7;     // player 1 from/to
    starthole[2] = 9; endhole[2] = 15;    // player 2 from/to

    opposite[1] = 15;
    opposite[2] = 14;
    opposite[3] = 13;
    opposite[4] = 12;
    opposite[5] = 11;
    opposite[6] = 10;
    opposite[7] = 9;

    initmoves();

}

__inline void outputboard()
{
    int i;
    for (i=starthole[1]; i<=endhole[1]; i++)
    {
        if (b2[i] < 10) cout << " "; // pad with space
        cout << b2[i] << " ";
    }
    cout << "[";
    if (b2[pocket[1]] < 10) cout << " "; // pad with space
    cout << b2[pocket[1]] << "] ";
    for (i=starthole[2]; i<=endhole[2]; i++)
    {
        if (b2[i] < 10) cout << " "; // pad with space
        cout << b2[i] << " ";
    }
    cout << "[";
    if (b2[pocket[2]] < 10) cout << " "; // pad with space
    cout << b2[pocket[2]] << "] ";
}

__inline void output(int iTurns)
{
    int i;
    if (b2[pocket[1]] < 10) cout << "0"; // pad with 0
    cout << b2[pocket[1]] << "-";
    if (iTurns < 10) cout << "0"; // pad with 0
    cout << iTurns << ":";
    outputboard();
    cout << ": ";
    for (i=1; i<=iTurns; i++)
        cout << trymove[i];
    cout << endl;
}


__inline int SeedsLeft(int iPlayer)     // any seeds left for this player?
{
    int i;
    for (i=starthole[iPlayer]; i<=endhole[iPlayer]; i++)  // for each space
        if (b2[i]!=0)       // if hole has a seed
            return 1;       // seeds found
    return 0;               // no seeds found
}

__inline int MoveDone(int iHole)
{
    int bDone, n;
    if (iHole==pocket[1]) // ended in home, take another turn
        bDone = 1;
    else if ((iHole>=starthole[2]) && (iHole<=endhole[2])) // land on opponents side
    {
        if (b2[iHole]==1) // if only seed in hole
            bDone = 1;
        else // if many seeds
            bDone = 0;
    }
    else if ((iHole>=starthole[1]) && (iHole<=endhole[1])) // land on our side
    {
        if (b2[iHole]==1) // if only seed in hole
        {
            bDone = 1;          // turn over
            n = opposite[iHole];
            if (b2[n] > 0)
            {
                b2[pocket[1]] = b2[pocket[1]] + b2[n]; // take opponents seeds
                b2[n] = 0;
                b2[pocket[1]] = b2[pocket[1]] + 1; // put your seed in home
                b2[iHole] = 0;
            }
        }
        else // if many seeds
            bDone = 0;
    }

    return bDone;
}

__inline int nxt(int n)
{
    n = n + 1;
    if (n > 15) n = 1;
    return n;
}

__inline int DoMove(int iHole)
{
    int bMoveDone, iHand, i;

    do
    {
        iHand = b2[iHole];
        b2[iHole] = 0;
        for (i=1; i<=iHand; i++)
        {
            iHole = nxt(iHole);
            b2[iHole] = b2[iHole] + 1;
        }
        bMoveDone = MoveDone(iHole);
    }
    while (!bMoveDone);

    return iHole;
}



int main( int argc, char *argv[] )
{

int      m1,  m2,  m3,  m4,  m5,  m6,  m7,  m8,  m9;
int m10, m11, m12, m13, m14, m15, m16, m17, m18, m19;
int m20, m21, m22, m23, m24, m25, m26, m27, m28, m29;
int m30, m31, m32, m33, m34, m35, m36, m37, m38, m39;
int m40, m41, m42, m43, m44, m45, m46, m47, m48, m49;
int m50, m51, m52, m53, m54, m55, m56, m57, m58, m59;
int m60, m61, m62, m63, m64, m65, m66, m67, m68, m69;
int m70, m71, m72, m73, m74, m75, m76, m77, m78, m79;
int m80, m81, m82, m83, m84, m85, m86, m87, m88, m89;
int m90, m91, m92, m93, m94, m95, m96, m97, m98, m99;

int i, iTry, iHole, iBest;
int iMoveLow, iMoveHigh, iPocketLow, iPocketHigh, iBestMode;
int bOutputBoardEveryMove, bSetMoves;
int B1, B2;

cout << "Dakon" << endl;

if (argc == 1 )
{
    cout << "Syntax: " << argv[0] << " [options]" << endl;
    cout << "options:" << endl;
    cout << "-go" << endl;
    cout << " run with default settings" << endl;
    cout << " do not include any other settings" << endl;
    cout << "-setmoves 1252151" << endl;
    cout << " set the opening moves" << endl;
    cout << " numbers must be between 1 and 7 with no spaces." << endl;
    cout << "-setboard 13 0 1 13 13 1 2 10 13 3 1 3 4 14 1 6" << endl;
    cout << " This specifies the starting board." << endl;
    cout << " Must specify 16 number seperated by spaces." << endl;
    cout << " Numbers 8 and 16 are the pockets." << endl;
    cout << "-rangepocket n1 n2" << endl;
    cout << " n1 default 1, n2 default 99" << endl;
    cout << " Must include both numbers.  Use to filter output." << endl;
    cout << " example: -rangepocket 10 20 would only move" << endl;
    cout << " display sequences that result in 10 20 pieces" << endl;
    cout << "-rangemove n1 n2" << endl;
    cout << " constrain the output" << endl;
    cout << " to a range of moves." << endl;
    cout << " n1 default 1, n2 default 99" << endl;
    cout << " Must include both numbers.  Use to filter output." << endl;
    cout << " example: -rangemove 20 25 would only display" << endl;
    cout << " move sequences of 20 25 moves" << endl;
    cout << "-xoutput1" << endl;
    cout << " extra output #1: view the board after every move" << endl;
    cout << "-best n1" << endl;
    cout << " n1 default is 0" << endl;
    cout << " 0 - display all solutions" << endl;
    cout << " 1 - display solutions >= most pieces found" << endl;
    cout << " 2 - display solutions > most pieces found" << endl;
    return 0;
}

initvars();
initboard();

iBest = 0;
bSetMoves = 0;
bOutputBoardEveryMove = 0;
iMoveLow = 0;
iMoveHigh = 99;
iPocketLow = 0;
iPocketHigh = 99;
iBestMode = 0;       // 0. all answers  1. >= best  2. > best

if (argc>1)
{
	for ( i=1; i<argc; i++ )
	{
		if ( !stricmp( argv[i], "-setmoves" ) )
		{
		    bSetMoves = 1;
		    setmoves(argv[i+1]);
		    i++;
		}
		else if ( !stricmp( argv[i], "-setboard" ) )
		{
	        setboard(argv, i+1);  // set init board
	        initboard();          // init board
	        i += 16;
		}
		else if ( !stricmp( argv[i], "-rangemove" ) )
		{
		    iMoveLow = string2int(argv[i+1]);   // new low for move range
		    iMoveHigh = string2int(argv[i+2]);  // new high for move range
		    i += 2;
		}
		else if ( !stricmp( argv[i], "-rangepocket" ) )
		{
		    iPocketLow = string2int(argv[i+1]);   // new low for pocket range
		    iPocketHigh = string2int(argv[i+2]);  // new high for pocket range
		    i += 2;
		}
		else if ( !stricmp( argv[i], "-xoutput1" ) )
		{
		    bOutputBoardEveryMove = 1;
		}
		else if ( !stricmp( argv[i], "-best" ) )
		{
		    iBestMode = string2int(argv[i+1]);   // 1. >= Best  2. > Best
		    i++;
		}
		else if ( !stricmp( argv[i], "-go" ) )
		{
		    // do nothing
		}
		else
		{
		    cout << "ERROR: Unknown parameter [" << argv[i] << "]" << endl;
		    return 0;
		}
	}
}

cout << "Start Board: ";
outputboard();
cout << endl;

for (m1=initmove[1]; m1<=7; m1++) {
for (m2=initmove[2]; m2<=7; m2++) {
for (m3=initmove[3]; m3<=7; m3++) {
for (m4=initmove[4]; m4<=7; m4++) {
for (m5=initmove[5]; m5<=7; m5++) {
for (m6=initmove[6]; m6<=7; m6++) {
for (m7=initmove[7]; m7<=7; m7++) {
for (m8=initmove[8]; m8<=7; m8++) {
for (m9=initmove[9]; m9<=7; m9++) {
for (m10=initmove[10]; m10<=7; m10++) {
for (m11=initmove[11]; m11<=7; m11++) {
for (m12=initmove[12]; m12<=7; m12++) {
for (m13=initmove[13]; m13<=7; m13++) {
for (m14=initmove[14]; m14<=7; m14++) {
for (m15=initmove[15]; m15<=7; m15++) {
for (m16=initmove[16]; m16<=7; m16++) {
for (m17=initmove[17]; m17<=7; m17++) {
for (m18=initmove[18]; m18<=7; m18++) {
for (m19=initmove[19]; m19<=7; m19++) {
for (m20=initmove[20]; m20<=7; m20++) {
for (m21=initmove[21]; m21<=7; m21++) {
for (m22=initmove[22]; m22<=7; m22++) {
for (m23=initmove[23]; m23<=7; m23++) {
for (m24=initmove[24]; m24<=7; m24++) {
for (m25=initmove[25]; m25<=7; m25++) {
for (m26=initmove[26]; m26<=7; m26++) {
for (m27=initmove[27]; m27<=7; m27++) {
for (m28=initmove[28]; m28<=7; m28++) {
for (m29=initmove[29]; m29<=7; m29++) {
for (m30=initmove[30]; m30<=7; m30++) {
for (m31=initmove[31]; m31<=7; m31++) {
for (m32=initmove[32]; m32<=7; m32++) {
for (m33=initmove[33]; m33<=7; m33++) {
for (m34=initmove[34]; m34<=7; m34++) {
for (m35=initmove[35]; m35<=7; m35++) {
for (m36=initmove[36]; m36<=7; m36++) {
for (m37=initmove[37]; m37<=7; m37++) {
for (m38=initmove[38]; m38<=7; m38++) {
for (m39=initmove[39]; m39<=7; m39++) {
for (m40=initmove[40]; m40<=7; m40++) {
for (m41=initmove[41]; m41<=7; m41++) {
for (m42=initmove[42]; m42<=7; m42++) {
for (m43=initmove[43]; m43<=7; m43++) {
for (m44=initmove[44]; m44<=7; m44++) {
for (m45=initmove[45]; m45<=7; m45++) {
for (m46=initmove[46]; m46<=7; m46++) {
for (m47=initmove[47]; m47<=7; m47++) {
for (m48=initmove[48]; m48<=7; m48++) {
for (m49=initmove[49]; m49<=7; m49++) {
for (m50=initmove[50]; m50<=7; m50++) {
for (m51=initmove[51]; m51<=7; m51++) {
for (m52=initmove[52]; m52<=7; m52++) {
for (m53=initmove[53]; m53<=7; m53++) {
for (m54=initmove[54]; m54<=7; m54++) {
for (m55=initmove[55]; m55<=7; m55++) {
for (m56=initmove[56]; m56<=7; m56++) {
for (m57=initmove[57]; m57<=7; m57++) {
for (m58=initmove[58]; m58<=7; m58++) {
for (m59=initmove[59]; m59<=7; m59++) {
for (m60=initmove[60]; m60<=7; m60++) {
for (m61=initmove[61]; m61<=7; m61++) {
for (m62=initmove[62]; m62<=7; m62++) {
for (m63=initmove[63]; m63<=7; m63++) {
for (m64=initmove[64]; m64<=7; m64++) {
for (m65=initmove[65]; m65<=7; m65++) {
for (m66=initmove[66]; m66<=7; m66++) {
for (m67=initmove[67]; m67<=7; m67++) {
for (m68=initmove[68]; m68<=7; m68++) {
for (m69=initmove[69]; m69<=7; m69++) {
for (m70=initmove[70]; m70<=7; m70++) {
for (m71=initmove[71]; m71<=7; m71++) {
for (m72=initmove[72]; m72<=7; m72++) {
for (m73=initmove[73]; m73<=7; m73++) {
for (m74=initmove[74]; m74<=7; m74++) {
for (m75=initmove[75]; m75<=7; m75++) {
for (m76=initmove[76]; m76<=7; m76++) {
for (m77=initmove[77]; m77<=7; m77++) {
for (m78=initmove[78]; m78<=7; m78++) {
for (m79=initmove[79]; m79<=7; m79++) {
for (m80=initmove[80]; m80<=7; m80++) {
for (m81=initmove[81]; m81<=7; m81++) {
for (m82=initmove[82]; m82<=7; m82++) {
for (m83=initmove[83]; m83<=7; m83++) {
for (m84=initmove[84]; m84<=7; m84++) {
for (m85=initmove[85]; m85<=7; m85++) {
for (m86=initmove[86]; m86<=7; m86++) {
for (m87=initmove[87]; m87<=7; m87++) {
for (m88=initmove[88]; m88<=7; m88++) {
for (m89=initmove[89]; m89<=7; m89++) {
for (m90=initmove[90]; m90<=7; m90++) {
for (m91=initmove[91]; m91<=7; m91++) {
for (m92=initmove[92]; m92<=7; m92++) {
for (m93=initmove[93]; m93<=7; m93++) {
for (m94=initmove[94]; m94<=7; m94++) {
for (m95=initmove[95]; m95<=7; m95++) {
for (m96=initmove[96]; m96<=7; m96++) {
for (m97=initmove[97]; m97<=7; m97++) {
for (m98=initmove[98]; m98<=7; m98++) {
for (m99=initmove[99]; m99<=7; m99++) {

if (bSetMoves)
{
    bSetMoves = 0;
    initmoves();
}

initboard(); // init board to starting board

trymove[1]=m1;
trymove[2]=m2;
trymove[3]=m3;
trymove[4]=m4;
trymove[5]=m5;
trymove[6]=m6;
trymove[7]=m7;
trymove[8]=m8;
trymove[9]=m9;
trymove[10]=m10;
trymove[11]=m11;
trymove[12]=m12;
trymove[13]=m13;
trymove[14]=m14;
trymove[15]=m15;
trymove[16]=m16;
trymove[17]=m17;
trymove[18]=m18;
trymove[19]=m19;
trymove[20]=m20;
trymove[21]=m21;
trymove[22]=m22;
trymove[23]=m23;
trymove[24]=m24;
trymove[25]=m25;
trymove[26]=m26;
trymove[27]=m27;
trymove[28]=m28;
trymove[29]=m29;
trymove[30]=m30;
trymove[31]=m31;
trymove[32]=m32;
trymove[33]=m33;
trymove[34]=m34;
trymove[35]=m35;
trymove[36]=m36;
trymove[37]=m37;
trymove[38]=m38;
trymove[39]=m39;
trymove[40]=m40;
trymove[41]=m41;
trymove[42]=m42;
trymove[43]=m43;
trymove[44]=m44;
trymove[45]=m45;
trymove[46]=m46;
trymove[47]=m47;
trymove[48]=m48;
trymove[49]=m49;
trymove[50]=m50;
trymove[51]=m51;
trymove[52]=m52;
trymove[53]=m53;
trymove[54]=m54;
trymove[55]=m55;
trymove[56]=m56;
trymove[57]=m57;
trymove[58]=m58;
trymove[59]=m59;
trymove[60]=m60;
trymove[61]=m61;
trymove[62]=m62;
trymove[63]=m63;
trymove[64]=m64;
trymove[65]=m65;
trymove[66]=m66;
trymove[67]=m67;
trymove[68]=m68;
trymove[69]=m69;
trymove[70]=m70;
trymove[71]=m71;
trymove[72]=m72;
trymove[73]=m73;
trymove[74]=m74;
trymove[75]=m75;
trymove[76]=m76;
trymove[77]=m77;
trymove[78]=m78;
trymove[79]=m79;
trymove[80]=m80;
trymove[81]=m81;
trymove[82]=m82;
trymove[83]=m83;
trymove[84]=m84;
trymove[85]=m85;
trymove[86]=m86;
trymove[87]=m87;
trymove[88]=m88;
trymove[89]=m89;
trymove[90]=m90;
trymove[91]=m91;
trymove[92]=m92;
trymove[93]=m93;
trymove[94]=m94;
trymove[95]=m95;
trymove[96]=m96;
trymove[97]=m97;
trymove[98]=m98;
trymove[99]=m99;

for (iTry=1; iTry<=99; iTry++)
{
    if (iTry>iMoveHigh) // filter out the higher moves if a lower-high specified
        break;

    iHole = trymove[iTry];
    if (b2[iHole]==0)   // cannot take pieces from an empty hole
        break;
    else                // take turn
    {
        iHole = DoMove(iHole); // do move and return current hole
        if (bOutputBoardEveryMove)
        {
            cout << "Move[" << trymove[iTry] << "]";
            outputboard();
            cout << endl;
        }
        B1 = SeedsLeft(1);              // does player 1 have seeds left?
        B2 = SeedsLeft(2);              // does player 2 have seeds left?
        if (B1 && !B2)                  // if player 1 has seeds but player 2 has none, continue player 1 turn
            continue;
        else
        {
            B1 = !B1 && !B2;            // board empty?
            B2 = iHole != pocket[1];    // hole is not player 1 pocket
            if (B1 || B2) // if board empty or hole is not player 1 pocket
            {
                if (iBestMode==0)                   // display all moves
                    B1 = 1;
                else if (iBestMode==1)
                    B1 = (b2[pocket[1]] >= iBest);  // display moves >= best
                else
                    B1 = (b2[pocket[1]] > iBest);   // dispolay moves > best
                    
                if (B1)  // if pocket 1 contains same or more than best
                {
                    iBest = b2[pocket[1]]; // set new best
                    B1 = (iTry>=iMoveLow) && (iTry<=iMoveHigh);         // is tries within range
                    B2 = (iBest>=iPocketLow) && (iBest<=iPocketHigh);   // is pieces won within range
                    if (B1 && B2)
                        output(iTry);       // output results
                }
                break;
            }
        }
    }
}

if (iTry < 99) break; }
if (iTry < 98) break; }
if (iTry < 97) break; }
if (iTry < 96) break; }
if (iTry < 95) break; }
if (iTry < 94) break; }
if (iTry < 93) break; }
if (iTry < 92) break; }
if (iTry < 91) break; }
if (iTry < 90) break; }
if (iTry < 89) break; }
if (iTry < 88) break; }
if (iTry < 87) break; }
if (iTry < 86) break; }
if (iTry < 85) break; }
if (iTry < 84) break; }
if (iTry < 83) break; }
if (iTry < 82) break; }
if (iTry < 81) break; }
if (iTry < 80) break; }
if (iTry < 79) break; }
if (iTry < 78) break; }
if (iTry < 77) break; }
if (iTry < 76) break; }
if (iTry < 75) break; }
if (iTry < 74) break; }
if (iTry < 73) break; }
if (iTry < 72) break; }
if (iTry < 71) break; }
if (iTry < 70) break; }
if (iTry < 69) break; }
if (iTry < 68) break; }
if (iTry < 67) break; }
if (iTry < 66) break; }
if (iTry < 65) break; }
if (iTry < 64) break; }
if (iTry < 63) break; }
if (iTry < 62) break; }
if (iTry < 61) break; }
if (iTry < 60) break; }
if (iTry < 59) break; }
if (iTry < 58) break; }
if (iTry < 57) break; }
if (iTry < 56) break; }
if (iTry < 55) break; }
if (iTry < 54) break; }
if (iTry < 53) break; }
if (iTry < 52) break; }
if (iTry < 51) break; }
if (iTry < 50) break; }
if (iTry < 49) break; }
if (iTry < 48) break; }
if (iTry < 47) break; }
if (iTry < 46) break; }
if (iTry < 45) break; }
if (iTry < 44) break; }
if (iTry < 43) break; }
if (iTry < 42) break; }
if (iTry < 41) break; }
if (iTry < 40) break; }
if (iTry < 39) break; }
if (iTry < 38) break; }
if (iTry < 37) break; }
if (iTry < 36) break; }
if (iTry < 35) break; }
if (iTry < 34) break; }
if (iTry < 33) break; }
if (iTry < 32) break; }
if (iTry < 31) break; }
if (iTry < 30) break; }
if (iTry < 29) break; }
if (iTry < 28) break; }
if (iTry < 27) break; }
if (iTry < 26) break; }
if (iTry < 25) break; }
if (iTry < 24) break; }
if (iTry < 23) break; }
if (iTry < 22) break; }
if (iTry < 21) break; }
if (iTry < 20) break; }
if (iTry < 19) break; }
if (iTry < 18) break; }
if (iTry < 17) break; }
if (iTry < 16) break; }
if (iTry < 15) break; }
if (iTry < 14) break; }
if (iTry < 13) break; }
if (iTry < 12) break; }
if (iTry < 11) break; }
if (iTry < 10) break; }
if (iTry < 9) break; }
if (iTry < 8) break; }
if (iTry < 7) break; }
if (iTry < 6) break; }
if (iTry < 5) break; }
if (iTry < 4) break; }
if (iTry < 3) break; }
if (iTry < 2) break; }

}

    return 0;
}