#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>

#define MAXPILES 15

int field[MAXPILES][5];
int done[MAXPILES];
struct { int src; int tgt; int cnt; } s[65535];
int slen=0;
int donecnt=0;
int onlyfirst=1; /* exit after first solution */
int showtables=1; /* show initial and final tableaus */
int tracelvl=4; /* Trace Level */
int letter=0;   /* Stack format: A->O or 1->15 */

int chkmove (int src, int tgt) { 
   int *sp=field[src],*tp=field[tgt];
   int st=sp[sp[0]],tt=tp[tp[0]]; int i,cnt;

   /* trivial cases */
   if (st==0 || (tt!=0 && st!=tt)) {return 0;}
   
   /* determine number of cards to move */
   for (cnt=1,i=sp[0]-1; sp[i]==st && i>0 ; i--,cnt++) {}

   /* a very special case:
    * there is one pile with two top-cards same
    * and two piles with matching top-card and
    * one place left on each.  -- Do this only
    * for the first target.
    */
   if (cnt==2 && tp[0]==3 && tp[3]==st) {
      for (i=tgt+1; i<MAXPILES; i++) { int *cp=field[i];
         if (i!=src && cp[0]==3 && cp[3]==st) { return -i-1; }
      }
   }
   /* if target can't hold them ... */
   if (cnt+tp[0] > 4) {return 0;}

   /* three extra rules for empty targets */
   if (tt==0) { 

      /* don't move complete piles to empty spaces */
      if (cnt==sp[0]) {return 0;}

      /* see, whether there wasn't/isn't a "better" target */
      for (i=0; i<MAXPILES; i++) { 
         int *cp=field[i];
         if (i==tgt || i==src) continue;
         if (cp[0]==0) {
            /* another empty target (with larger index) */
            /* only the last one is tried */
            if (i>tgt) {return 0;}
         } else {
            /* prefer non-empty targets */
            if (cp[cp[0]]==st && cnt+cp[0] <= 4) {return 0;}
         }
      }
   }
   return cnt;
}

int chkdone(int p) { int *pl=field[p];
   if (pl[0]!=4) {return 0;}
   return (pl[1]==pl[2] && pl[2]==pl[3] && pl[3]==pl[4]);
}

void move(int src,int tgt,int cnt) {
   int *sp=field[src],*tp=field[tgt];
   while (cnt) { tp[tp[0]+1]=sp[sp[0]]; tp[0]++; sp[0]--; cnt--; }
}

int doit(int src, int tgt) {
   int cnt=chkmove(src,tgt);
   if (cnt>0) {
      move(src,tgt,cnt);
      if (chkdone(tgt)) { done[tgt]=1; donecnt++; }
      slen++; s[slen].src=src; s[slen].tgt=tgt; s[slen].cnt=cnt;
   } else if (cnt<0) {
      move(src,tgt,1);
      move(src,-cnt-1,1);
      /* pile-completion impossible in this case */
      slen++; s[slen].src=src; s[slen].tgt=tgt; s[slen].cnt=-1;
      slen++; s[slen].src=src; s[slen].tgt=-cnt-1; s[slen].cnt=-1;
   }
   return cnt;
}

void undo() {
   int src=s[slen].src, tgt=s[slen].tgt, cnt=s[slen].cnt; slen--;
   if (chkdone(tgt)) { done[tgt]=0; donecnt--; }
   if (cnt>0) {
      move(tgt,src,cnt); 
   } else {
      move(tgt,src,1); move(s[slen].tgt,s[slen].src,1); slen--;
   }
}

void printtable() {
   int i,j;
   for (i=0; i<MAXPILES; i++) {
      for (j=1; j<=5; j++) {
          putchar( (j<=field[i][0])?field[i][j]:' ' );
      }; putchar( ((i&3)==3)?'\n':'\t');
   }; putchar('\n'); fflush(stdout);
}
void printstack() { int i;
   int base; char *fmt;
   if (letter) { base='A'; fmt=" %c->%c \t "; } 
   else { base=1; fmt="%2d->%-2d\t "; }
   for (i=1; i<=slen; i++) {
      printf(fmt,s[i].src+base,s[i].tgt+base);
   }; putchar('\n'); fflush(stdout);
}

void madeit() {
   printstack();
   if (showtables) printtable();
   if (onlyfirst) exit(1);
}

void step(int c,int lasttgt) { int src,tgt;
   if(c<=tracelvl) {printstack();}
   if (donecnt==13) { madeit(); return; }
   for (tgt=0; tgt<MAXPILES; tgt++) {
      if (field[tgt][0]==4) continue;
      for (src=0; src<MAXPILES; src++) {
         if (done[src] || src==lasttgt || src==tgt) continue;
         if (doit(src,tgt)) { step(c+1,tgt); undo(); }
      }
   }
}

void verify() {
   int cnt[14]; int i,j;
   for (i=1; i<14; i++) cnt[i]=0;
   for (i=0; i<MAXPILES; i++) {
      for (j=1; j<=4; j++) {
          int ch=field[i][j];
          if (ch>='2' && ch<='9') { ch-='0';
          } else if (ch=='a') { ch = 1;
          } else if (ch=='z') { ch = 10;
          } else if (ch=='j') { ch = 11;
          } else if (ch=='q') { ch = 12;
          } else if (ch=='k') { ch = 13;
          }
          cnt[ch]++;
      }
   }
   for (i=1; i<14; i++) if (cnt[i]!=4) {
      puts("inconsistency!"); exit(1);
   }
}

void init(const char *src) { int i,j; char *data;
   char d[100]; data=d;
   if (src) {
      strncpy(d,src,100); 
   } else {
      src="a234,5678,9zjq,ka23,4567,89zj,qka2,3456,789z,jqka,2345,6789,zjqk,,,";
      strncpy(d,src ,100); 
      for (i=0; i<52; i++) { int i1,j1; char c;
         j=i+random()%(52-i);
         i1=i+i/4, j1=j+j/4;
         c=d[j1]; d[j1]=d[i1]; d[i1]=c;
      }
   }
   i=0; j=0;
   while (*data) { char ch=*data++;
      if (ch==' ' || ch==',') {
         field[i][0]=j; done[i]=0; i++; j=0;
      } else {
         j++; field[i][j]= ch;
      }
   }
   verify();
}

int main(int argc, char *argv[]) {
    int optret; char *d=NULL; char *opts="aqvlht:s:";

    while ((optret=getopt(argc,argv,opts))!=-1) {
        switch (optret) {
            case 'a': onlyfirst=0; if (showtables==1) {showtables=0;} break;
            case 's': d=optarg; break;
            case 'q': showtables=0; break; 
            case 'v': showtables=2; break; 
            case 'l': letter=1; break; 
            case 't': tracelvl=atoi(optarg); break; 
            case 'h': case '?': printf("%s: %s\n",argv[0],opts); exit(1);
            default: break;
        }
    }

    if (d) { 
        init(d); 
    } else {
        if (optind+1!=argc) { puts("no or too many jobs."); exit(1); } 
        srandom(atoi(argv[optind]));
        init(NULL); 
        printf("Spiel-Nr: %s\n",argv[optind]); 
    }
    if (showtables) printtable();

    step(1,-1);
    return 0;
}