>Number:         4929
>Category:       c++
>Synopsis:       Internal compiler error in c++
>Confidential:   no
>Severity:       critical
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu Nov 22 09:36:01 PST 2001
>Closed-Date:
>Last-Modified:
>Originator:     ?
>Release:        unknown-1.0
>Organization:
>Environment:
cygwin
>Description:
$ c++ -O3 soli.cpp
soli.cpp: In function `struct enddata * MakeEndGameData(enddata *, int)':
soli.cpp:472: Internal compiler error.
soli.cpp:472: Please submit a full bug report.
soli.cpp:472: See <URL:http://www.gnu.org/software/gcc/bugs.html> for instructions.
>How-To-Repeat:

>Fix:

>Release-Note:
>Audit-Trail:
>Unformatted:
----gnatsweb-attachment----
Content-Type: text/plain; name="soli.cpp"
Content-Disposition: inline; filename="soli.cpp"

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

//#define S_DEBUG
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define LONG_MAX 1000000000

struct u {
  int val; // val = -1 <=> udefineret; val = 0 <=> tom; val = 1 <=> pind
  //int mark;
} U;
struct pt {
  int x,y,z,w,n;
} PT;
struct peg {
  int x,y;
} PEG;
struct game {
  int max;
  struct peg *p;
} GAME;
struct gamelist {
  int max;
  struct game *g;
} GAMELIST;
struct enddata {
  int max;
  struct gamelist *l;
} ENDDATA;

struct pt mvList[33];
struct pt moves[33];
int moveTop = 0, listMax = -1, treeBest = -1;
long leaves = 0,skips = 0, solutions = 0, level = -1, pSize = 1, tmpEstTreeSize;
double progress;
char p = '%';

void init_malloc(struct u **b);
void init_values(struct u **b);
void print(struct u **b);
int randintval(int low, int high);
double randval(double low, double high);
int nMoves(struct u **b);
int move(struct u **b, int x, int y, int r);
int isMove(struct u **b, int x, int y, int r);
struct pt *MoveList(struct u **b, int *size);
struct pt searchAll(struct u **b, int removed);
int loadboard(struct u **b, char *filename, int *removed);
int saveboard(struct u **b, char *filename);
int isSolvable(struct u **b,int removed);
struct enddata *MakeEndGameData(struct enddata *db, int calclevel);
void PrintEndGameData(struct enddata *db, char *filename);
struct pt trf(int id, int x, int y);
int compareINT(const int *arg1, const int *arg2);
int comparePEG(const struct peg *arg1, const struct peg *arg2);
int compareGAME(const struct game *arg1, const struct game *arg2);
struct enddata *loadDbFromFile(struct enddata *db, char *filename);
struct enddata *EndGameDataAddLevel(struct enddata *db);

struct enddata *db;
int dblevel = 0;

int main(int argc, char *argv[]) {
  struct u **b;
  struct pt res;
  int i,x=-1,y=-1,r=-1, removed=0, points=0,tmp,bDone=0,movesLeft,j,inited=0;
  char c[80];
  char filename[256];
  char gameover [] = "\
============================================================\n\
================        GAME OVER !!          ==============\n\
============================================================\n";
  char line [] = "============================================================\n";
  printf("%s",line);
  srand((unsigned)time(NULL)); 
  // malloc
  b = (struct u **)malloc(7 * sizeof(U));
  for(i=0;i<7;i++)
    b[i] = (struct u *)malloc(7 * sizeof(U));
  
  if (argc > 1) {
    sscanf(argv[1], "%s", filename);
    inited = loadboard(b,filename,&removed);
  }
  if (!inited)
    init_values(b);
  db = NULL;

  while (removed < 31 && (movesLeft = nMoves(b)) > 0) {
    //printf("Press a key\n");
    //fgets(c,80,stdin);
    print(b);
    printf("Moves left: %d  Removed: %d\n",movesLeft,removed);
    fgets(c,80,stdin);
    sscanf(c,"%d.%d.%d\n",&x,&y,&r);
    if (c[0] == 's') {
      printf("Save g)ame or d)atabase ? \n");
      fgets(c,80,stdin);
      if (c[0] ==  'g') {
        printf("Filename: " );
        gets(filename);
        if (saveboard(b,filename))
          printf("The board was saved\n");
      } else if (c[0] == 'd') {
        printf("Enter a filename to save the database in (doesn't save if no filename): ");
        gets(filename);
        PrintEndGameData(db,filename);
      }
    } else if (c[0] == 'a') {
      db = EndGameDataAddLevel(db);
    } else if (c[0] == 'm') {
      int i;
      for(i=0,printf("Moves:  ");i<moveTop;i++)
        printf("(%d.%d.%d) ",moves[i].x,moves[i].y,moves[i].z);
      printf("\n");
    } else if (c[0] == 10) {
      printf("No input\n");
    } else if (c[0] == 'r') {
      x = moves[moveTop].x;
      y = moves[moveTop].y;
      r = moves[moveTop].z;
    } else if (c[0] == 'd') {
      int calclevel = 0;
      printf("How many pegs should the precalculated boards at most contain?\n");
      fgets(c,80,stdin);
      sscanf(c,"%d\n",&calclevel);
      if (calclevel > 0) {
        db = MakeEndGameData(db,calclevel-1);
        //system("pause");
      } else
        printf("No precomputation done this time.\n");
      dblevel = calclevel;
    } else if (c[0] == 'u') {
      if (moveTop > 0) {
        int lx,ly,lz;
        moveTop--;
        lx = moves[moveTop].x;
        ly = moves[moveTop].y;
        lz = moves[moveTop].z;
        b[lx][ly].val = 1;
        if (lz == 1) {b[lx-1][ly].val = 1; b[lx-2][ly].val = 0;}
        else if (lz == 2) {b[lx+1][ly].val = 1; b[lx+2][ly].val = 0;}
        else if (lz == 3) {b[lx][ly-1].val = 1; b[lx][ly-2].val = 0;}
        else if (lz == 4) {b[lx][ly+1].val = 1; b[lx][ly+2].val = 0;}
        removed--;
      }
    } else if (c[0] == 't') {
      printf("%s\n",(isSolvable(b,removed)) ? "Kan loeses" : "Kan ikke loeses");
    } else if (c[0] == 'l') {
      printf("Load g)ame or d)atabase ? \n");
      fgets(c,80,stdin);
      if (c[0] == 'g') {
        printf("load!\n");
        printf("Filename: " );
        gets(filename);
        if (loadboard(b,filename,&removed))
          printf("The board was loaded\n");
      } else if (c[0] == 'd') {
        printf("Trying to load database from file: ");
        gets(filename);
        if ((db = loadDbFromFile(db, filename)) != NULL) {
          printf("done!\n");
          dblevel = db->max;
          //PrintEndGameData(db);
        } else {
          printf("ERROR\n");
          dblevel = 0;
        }
      }
    } else if (c[0] == 'q') {
      printf("quit!\n");
      exit(0);
    }
    if (x == 99) {
      int tStart = clock();
      leaves=0; skips = 0; solutions = 0;
      treeBest = listMax = -1;
      tmpEstTreeSize = 1;
      progress = 0;
      for(j=0;j<33;j++)
        mvList[j].x = mvList[j].y = mvList[j].z = mvList[j].w = mvList[j].n = -1;
      res = searchAll(b,removed);
      printf("\nMax: %d  Removed: %d  Best: %d (%d nodes searched; %d branches were cut; %d sol's.(%.1lfs - %d node/s))\nList:",res.x,res.z,res.y,leaves,skips,solutions,(float) (clock()-tStart)/CLOCKS_PER_SEC, (int)((float)leaves / (float)((clock()-tStart)/CLOCKS_PER_SEC)));
      for(j=0;j<listMax;j++)
        printf("(%d,%d,%d,n%d(%d)) ",mvList[j].x,mvList[j].y,mvList[j].z,mvList[j].n,mvList[j].w);
      printf("\n");
    }
    if (isMove(b,x,y,r)) {
      moves[moveTop].x = x;
      moves[moveTop].y = y;
      moves[moveTop].z = r;
      moveTop++;
    }
    tmp = move(b,x,y,r);

    removed += tmp;
    if (removed == 31 && b[3][3].val == 1)
      removed = 32;
    x=y=r=-1;
  }
  print(b);
  printf("\n%s%sTotal %d removed\n%s",line,(removed == 32 ? "Congratulations, you cleared the board.\n" : "You didn't clear the board and missed the bonus.\n"),removed,gameover);
  printf("Save the game. Enter a filename: " );
  gets(filename);
  if (saveboard(b,filename))
    printf("The board was saved\n");
  return 0;
}

int compareINT(const int *arg1, const int *arg2) {
  if ((*arg1)<(*arg2)) return -1;
  if ((*arg1)>(*arg2)) return 1;
  return 0;
}

int comparePEG(const struct peg *arg1, const struct peg *arg2) {
  if (arg1->x < arg2->x) return -1;
  if (arg1->x > arg2->x) return 1;
  // HERE: arg1->x == arg2->x
  if (arg1->y < arg2->y) return -1;
  if (arg1->y > arg2->y) return 1;
#ifdef S_DEBUG
  printf("comparePEG: Argument 1 and 2 are equal: (%d,%d)\n",arg1->x,arg1->y);
  fflush(stdout);
#endif
  return 0;
}

int compareGAME(const struct game *arg1, const struct game *arg2) {
  // input: 2 sorterede games
  int i, compare;
  for(i=0;i<arg1->max;i++)
    if ((compare = comparePEG(&arg1->p[i],&arg2->p[i])) != 0) return compare;
#ifdef S_DEBUG
  printf("compareGAME: Argument 1 and 2 are equal\n");
  fflush(stdout);
#endif
  return 0;
}

void setPeg(struct enddata *db, int level, int game, int peg, int x, int y) {
  db->l[level].g[game].p[peg].x = x;
  db->l[level].g[game].p[peg].y = y;
}

void setPeg2(struct game *g, int k, int x, int y) {
  g->p[k].x = x;
  g->p[k].y = y;
}

int isPegSet(struct game *g, int x, int y) {
  int i;
  for(i=0;i<g->max;i++) {
    if ((g->p[i].x == x) && (g->p[i].y == y)) return 1;
  }
  return 0;
}

int equalUnderTrans(struct game *g1, int t, struct game *g2) {
  int i;

  if (g1->max != g2->max) return 0; // the two boardpositions must be of same size to be equal
  for(i=0;i<g1->max;i++) {
    struct pt aPt = trf(t,g1->p[i].x,g1->p[i].y);
    if (!isPegSet(g2,aPt.x,aPt.y))
      return 0;
  }
  return 1;
}

int isPrevBoard(struct game *g, int k, int r) {
  int x = g->p[k].x ,y = g->p[k].y;
  switch (r) {
  case 1:
    if (x < 2 || x > 6 || y < 0 || y > 6) return 0;
    if ((y >= 5 || y < 2) && x < 4) return 0;
    if (isPegSet(g,x-2,y) || isPegSet(g,x-1,y)) return 0;
    return 1;
    break;
  case 2:
    if (x > 4 || x < 0 || y < 0 || y > 6) return 0;
    if ((y >= 5 || y < 2) && x > 2) return 0;
    if (isPegSet(g,x+2,y) || isPegSet(g,x+1,y)) return 0;
    return 1;
    break;
  case 3:
    if (y < 2 || y > 6 || x < 0 || x > 6) return 0;
    if ((x >= 5 || x < 2) && y < 4) return 0;
    if (isPegSet(g,x,y-2) || isPegSet(g,x,y-1)) return 0;
    return 1;
    break;
  case 4:
    if (y > 4 || y < 0 || x < 0 || x > 6) return 0;
    if ((x >= 5 || x < 2) && y > 2) return 0;
    if (isPegSet(g,x,y+2) || isPegSet(g,x,y+1)) return 0;
    return 1;
    break;
  default:
    return 0;
    break;
  }
}

void setGame(struct game *g,struct game *newgame, int i) {
  g[i] = *newgame;
}

struct enddata *EndGameDataAddLevel(struct enddata *db) {
  int j,k,m,r,l,s=0,t=0,top = 0, procent = 0;
  if (db == NULL || db->max < 1) {
    printf("Can't add when there is no existing levels to add on.\n");
    return db;
  }
  db->max++;
  m = db->max;
  db->l = (struct gamelist *)realloc(db->l, m * sizeof(GAMELIST));

  db->l[m-1].max = db->l[m-2].max * (m-1) * 4;
  db->l[m-1].g = (struct game *)malloc(db->l[m-1].max * sizeof(GAME));

  printf("|");
  for(j=1;j<49;j++)
    printf("-");
  printf("|\n");
  for(j=0;j<db->l[m-2].max;j++) { // for all games on level m-2
    int progress = 100 * j / db->l[m-2].max;
    while (procent < progress) {
      if ((procent % 2) == 0) {printf("."); fflush(stdout);}
      procent++;
    }
    ;// find all boards, b, that lead to db[m-2][j]
    for(k=0;k<db->l[m-2].g[j].max;k++) { // for all pegs in a game
      for(r=1;r<5;r++) { // for all directions of move
        struct game *newgame = (struct game *)malloc(sizeof(GAME)); // make a potential new game
        if (isPrevBoard(&db->l[m-2].g[j],k,r)) { // checks if the board db->l[m-2].g[j] could come from
          int add = 1;                        // a board where 2 pegs were removed from the direction r to become the single peg, k
          int n1x, n1y, n2x, n2y, lx = db->l[m-2].g[j].p[k].x, ly = db->l[m-2].g[j].p[k].y;
          switch (r) {
          case 1:
            n1x = lx-1; n2x = lx-2; n1y = n2y = ly; break;
          case 2:
            n1x = lx+1; n2x = lx+2; n1y = n2y = ly; break;
          case 3:
            n1y = ly-1; n2y = ly-2; n1x = n2x = lx; break;
          case 4:
            n1y = ly+1; n2y = ly+2; n1x = n2x = lx; break;
          }
          newgame->p = (struct peg *)malloc(((db->l[m-2].g[j].max)+1) * sizeof(PEG));
          for(l=0;l<db->l[m-2].g[j].max;l++) {
            setPeg2(newgame, l, db->l[m-2].g[j].p[l].x, db->l[m-2].g[j].p[l].y);
          }
          setPeg2(newgame, k, n1x, n1y);
          setPeg2(newgame, db->l[m-2].g[j].max, n2x, n2y);
          newgame->max = (db->l[m-2].g[j].max) + 1;
          
          ;// if (for all transformations: b is not on any place in db[m-2+1])
          ;// add b to db[m-2+1]
          /*
          for(s=0;s<db->l[m-2+1].max && (add == 1);s++) {
            for(t=0;t<8 && (add == 1);t++) {
              if (equalUnderTrans(newgame,t,&db->l[m-2+1].g[s])) add = 0;
            }
          }
          */
          if (add == 1) {
            qsort((void *)newgame->p,(size_t)newgame->max,sizeof(PEG),(int (__cdecl *)(const void *,const void *))comparePEG);
            setGame(db->l[m-2+1].g,newgame,top++);
            //db->l[m-2+1].max = (db->l[m-2+1].max) + 1;
          } else
            free(newgame);
        }
      }
    }
  }
  printf("\nSize of new level %d: %d\n",m-1,top);
  db->l[m-1].max = top;
  qsort((void *)db->l[m-1].g,(size_t)db->l[m-1].max,sizeof(GAME),(int (__cdecl *)(const void *,const void *))compareGAME);
  
  // mark duplicates
  l = 0;
  for(j=1;j<db->l[m-1].max;j++) {
    if ((j%1000) == 0) printf(".");
    if (compareGAME(&db->l[m-1].g[l],&db->l[m-1].g[j]) == 0) {db->l[m-1].g[j].p[0].x = 9; top--;}
    else l = j;
  }
  printf("Marking done!\n");
  // sort again, so duplicates are put in the end
  qsort((void *)db->l[m-1].g,(size_t)db->l[m-1].max,sizeof(GAME),(int (__cdecl *)(const void *,const void *))compareGAME);
  db->l[m-1].max = top;
  printf("\nSize of new level %d: %d\n",m-1,top);

  /*
  for(j=0;j<db->l[m-1].max;j++) {
    for(k=j+1;k<db->l[m-1].max;k++) {
      for(t=0;t<8;t++)
        if (equalUnderTrans(&db->l[m-1].g[j],t,&db->l[m-1].g[k])) printf("coll (%d,%d) ",j,k);
    }
  }
  */
  return db;
}
struct enddata *MakeEndGameData(struct enddata *db, int calclevel) {
  int i,j,k,l,r,t,s,nlevels; //9
  int levelsize[] = {1,1,2,8,39,171,719,2757,9751,31312};
  nlevels = calclevel;

  // space allocation
  db = (struct enddata *)malloc(sizeof(ENDDATA));
  db->max = nlevels + 1;
  db->l = (struct gamelist *)malloc(db->max * sizeof(GAMELIST));

  // malloc and set set initial board
  for(i=0;i<db->max;i++)
    db->l[i].g = (struct game *)malloc(levelsize[i] * sizeof(GAME));

  db->l[0].max = 1;
  // only allocation for level 0
  // other levels will be allocated later
  for(i=1;i<db->max;i++)
    db->l[i].max = 0;
  db->l[0].g[0].p = (struct peg *)malloc(1 * sizeof(PEG));
  db->l[0].g[0].max = 1;
  setPeg(db,0,0,0,3,3); // set level 0, game 0, peg 0 to 3,3


  printf("Max-level: %d\n",db->max-1);
  for(i=0;i<db->max-1;i++) { // for all levels
    int procent = 0;
    printf("Level %d ",i+1);
    for(j=0;j<db->l[i].max;j++) { // for all games on a level
      int progress = 100 * j / db->l[i].max;
      while (procent < progress) {
        if ((procent % 2) == 0) {printf("."); fflush(stdout);}
        procent++;
      }
      ;// find all boards, b, that lead to db[i][j]
      for(k=0;k<db->l[i].g[j].max;k++) { // for all pegs in a game
        for(r=1;r<5;r++) { // for all directions of move
          struct game *newgame = (struct game *)malloc(sizeof(GAME)); // make a potential new game
          if (isPrevBoard(&db->l[i].g[j],k,r)) { // checks if the board db->l[i].g[j] could come from
            int add = 1;                        // a board where 2 pegs were removed from the direction r to become the single peg, k
            int n1x, n1y, n2x, n2y, lx = db->l[i].g[j].p[k].x, ly = db->l[i].g[j].p[k].y;
            switch (r) {
            case 1:
              n1x = lx-1; n2x = lx-2; n1y = n2y = ly; break;
            case 2:
              n1x = lx+1; n2x = lx+2; n1y = n2y = ly; break;
            case 3:
              n1y = ly-1; n2y = ly-2; n1x = n2x = lx; break;
            case 4:
              n1y = ly+1; n2y = ly+2; n1x = n2x = lx; break;
            }
            newgame->p = (struct peg *)malloc(((db->l[i].g[j].max)+1) * sizeof(PEG));
            for(l=0;l<db->l[i].g[j].max;l++) {
              setPeg2(newgame, l, db->l[i].g[j].p[l].x, db->l[i].g[j].p[l].y);
            }
            setPeg2(newgame, k, n1x, n1y);
            setPeg2(newgame, db->l[i].g[j].max, n2x, n2y);
            newgame->max = (db->l[i].g[j].max) + 1;

            ;// if (for all transformations: b is not on any place in db[i+1])
            ;// add b to db[i+1]
            for(s=0;s<db->l[i+1].max && (add == 1);s++) {
              for(t=0;t<8 && (add == 1);t++) {
                if (equalUnderTrans(newgame,t,&db->l[i+1].g[s])) add = 0;
              }
            }
            if (add == 1) {
              qsort((void *)newgame->p,(size_t)newgame->max,sizeof(PEG),(int (__cdecl *)(const void *,const void *))comparePEG);
              setGame(db->l[i+1].g,newgame,db->l[i+1].max);
              db->l[i+1].max = (db->l[i+1].max) + 1;
            } else
              free(newgame);
          }
        }
      }
    }
    qsort((void *)db->l[i+1].g,(size_t)db->l[i+1].max,sizeof(GAME),(int (__cdecl *)(const void *,const void *))compareGAME);
    printf("\n");
    fflush(stdout);
  }
  return db;
}

struct enddata *loadDbFromFile(struct enddata *db, char *filename) {
  int *levelsize;
  int t_levels = 0,i,j,tmp1,tmp2;
  FILE *dbfile = fopen(filename,"r");
  if (dbfile == NULL) {
    printf("Error in loadDbFromFile - cannot open file %s\n",filename);
    fflush(stdout);
    return NULL;
  }
  
  if (fscanf(dbfile,"Total %d levels: ", &t_levels) == EOF) printf("error\n");
  if (t_levels <= 0) return NULL;
  levelsize = (int *)malloc(t_levels * sizeof(int));
  for(i=0;i<t_levels;i++) {
    fscanf(dbfile,"%d ",&levelsize[i]);
    printf("Levelsize %d: %d\n",i+1,levelsize[i]);
  }
  fscanf(dbfile,"\n");
  
  // space allocation
  db = (struct enddata *)malloc(sizeof(ENDDATA));
  db->max = t_levels;
  db->l = (struct gamelist *)malloc(db->max * sizeof(GAMELIST));
  
  // malloc and set set initial board
  for(i=0;i<db->max;i++) {
    db->l[i].g = (struct game *)malloc(levelsize[i] * sizeof(GAME));
    db->l[i].max = levelsize[i];
  }
  
  printf("Max-level: %d\n",db->max-1);
  for(i=0;i<db->max;i++) { // for all levels
    int procent = 0;
    printf("Level %d ",i+1);
    fscanf(dbfile,"List of %d possible boards with %d pegs\n",&tmp1,&tmp2);
    for(j=0;j<db->l[i].max;j++) { // for all games on a level
      int l,progress = 100 * j / db->l[i].max;
      struct game *newgame = (struct game *)malloc(sizeof(GAME)); // make a potential new game
      fscanf(dbfile,"%d\t",&tmp1);
      while (procent < progress) {
        if ((procent % 2) == 0) {printf("."); fflush(stdout);}
        procent++;
      }
      newgame->p = (struct peg *)malloc((i+1) * sizeof(PEG));
      for(l=0;l<i+1;l++)
        fscanf(dbfile,"(%d,%d) ",&newgame->p[l].x,&newgame->p[l].y);
      fscanf(dbfile,"\n");
      newgame->max = i + 1;
      setGame(db->l[i].g,newgame,j);  
    }
    printf("\n");
  }
  printf("\n");
  fflush(stdout);
  fclose(dbfile);
  return db;
}

void printgame(struct game *g) {
  int i;
  for(i=0;i<g->max;i++)
    printf("(%d,%d) ",g->p[i].x,g->p[i].y);
}

void PrintEndGameData(struct enddata *db, char *filename) {
  int i,j,k;
  FILE *dbfile;

  dbfile = fopen(filename,"w");
  if (dbfile == NULL) {
    printf("Error in PrintEndGameData - cannot open file %s\n",filename);
    fflush(stdout);
    return;
  }

  fprintf(dbfile,"Total %d levels: ",db->max);
  for(i=0;i<db->max;i++)
    fprintf(dbfile,"%d ",db->l[i].max);
  fprintf(dbfile,"\n");

  for(i=0;i<db->max;i++) {
    printf("Level %d - %d boards\t",i+1,db->l[i].max);
    printf("Adding level %d to file: %s...\n",i,filename);
    fprintf(dbfile,"List of %d possible boards with %d pegs\n",db->l[i].max,i+1);
    for(j=0;j<db->l[i].max;j++) {
      fprintf(dbfile,"%d\t",j+1);
      for(k=0;k<db->l[i].g[j].max;k++)
        fprintf(dbfile,"(%d,%d) ",db->l[i].g[j].p[k].x,db->l[i].g[j].p[k].y);
      fprintf(dbfile,"\n");
    }    
  }
  printf("Done!\n");
  fclose(dbfile);
}

int loadboard(struct u **b, char *filename, int *removed) {
  int i,j,val;
  FILE *boardfile;
  int tmpremoved = -1;

  if ((boardfile = fopen(filename,"r")) == NULL) {
    printf("The file %s couldn't be opened\n",filename);
    return 0;
  } else
    printf("The file %s was opened\n",filename);
  fflush(stdout);

  for(j=6;j>=0;j--) {
    for(i=0;i<7;i++) {
      val = -2;
      fscanf(boardfile,"%d",&val);
      if (val < -1 || val > 1)
        return 0;
      b[i][j].val = val;
      if (b[i][j].val == 0) tmpremoved++;
    }
    fscanf(boardfile,"\n");
  }
  *removed = tmpremoved;

  fscanf(boardfile,"\nMoves (%d):\n",&moveTop);
  for(i=0;i<moveTop;i++)
    fscanf(boardfile,"(%d.%d.%d)\n",&moves[i].x,&moves[i].y,&moves[i].z);
 
  fclose(boardfile);
  return 1;
}

int saveboard(struct u **b, char *filename) {
  int i,j;
  FILE *boardfile;

  if ((boardfile = fopen(filename,"w")) == NULL) {
    printf("The file %s couldn't be opened\n",filename);
    return 0;
  } else
    printf("The file %s was opened\n",filename);
  fflush(stdout);

  for(j=6;j>=0;j--) {
    for(i=0;i<7;i++) {
      if (b[i][j].val >= 0) fprintf(boardfile," ");
      fprintf(boardfile,"%d ",b[i][j].val);
    }
    fprintf(boardfile,"\n");
  }
  fprintf(boardfile,"\nMoves (%d):\n",moveTop);
  for(i=0;i<moveTop;i++)
    fprintf(boardfile,"(%d.%d.%d)\n",moves[i].x,moves[i].y,moves[i].z);
  fclose(boardfile);
  return 1;
}

int move(struct u **b, int x, int y, int r) {
  if (isMove(b,x,y,r)) {
    switch (r) {
    case 1:
      b[x][y].val = 0; b[x-1][y].val = 0; b[x-2][y].val = 1;
      break;
    case 2:
      b[x][y].val = 0; b[x+1][y].val = 0; b[x+2][y].val = 1;
      break;
    case 3:
      b[x][y].val = 0; b[x][y-1].val = 0; b[x][y-2].val = 1;
      break;
    case 4:
      b[x][y].val = 0; b[x][y+1].val = 0; b[x][y+2].val = 1;
      break;
    }
    return 1;
  } else
    return 0;
}

int isMove(struct u **b, int x, int y, int r) {
  if (x < 0 || y < 0 || x > 6 || y > 6)
    return 0;
  if (b[x][y].val == 1) {
    switch (r) {
    case 1:
      if (x > 1 && b[x-1][y].val == 1 && b[x-2][y].val == 0)
        return 1;
      break;
    case 2:
      if (x < 5 && b[x+1][y].val == 1 && b[x+2][y].val == 0)
        return 1;
      break;
    case 3:
      if (y > 1 && b[x][y-1].val == 1 && b[x][y-2].val == 0)
        return 1;
      break;
    case 4:
      if (y < 5 && b[x][y+1].val == 1 && b[x][y+2].val == 0)
        return 1;
      break;
    }
  }
  return 0;
}

int isPeg(struct u **b, struct pt point) {
  return (b[point.x][point.y].val == 1);
}

void r90c(int *x, int *y) {
  int tmp = *x;
  *x = *y;
  *y = 6 - tmp;
}

struct pt trf(int id, int x, int y) {
  int i;
  struct pt ret;
  if (id >= 0 && id < 8) {
    if (id >= 4) // spejling i vandret linje
      y = 6 - y;
    for(i=0;i<(id%4);i++)
      r90c(&x,&y);
  } else {
    printf("Errorneous use of tfr => No rotation done, id is illegal: %d\n",id);
    fflush(stdout);
  }
  ret.x = x;
  ret.y = y;
  return ret;
}

void trfGAME(int t, struct game *g) {
  int i;
  for(i=0;i<g->max;i++) {
    struct pt aPt;
    aPt = trf(t,g->p[i].x,g->p[i].y);
    g->p[i].x = aPt.x;
    g->p[i].y = aPt.y;
  }
}

int findBoardInDB(struct game *g, struct gamelist *l) {
  int i_min = 0, i_max = l->max;
  int f, compare;

  while (i_max - i_min > 0) {
    f = (i_max + i_min) / 2;
    compare = compareGAME(&l->g[f],g);
    if (compare == 0) return f;
    else if (compare == -1) i_min = f+1;
    else if (compare == 1) i_max = f;
  }
  return -1;
}

int isSolvable(struct u **b,int removed) {
  int i,j;
    removed = MIN(removed,31);
  if (dblevel > 0 && 32 - removed <= dblevel) {
    struct game *g = (struct game *)malloc(sizeof(GAME));
    g->max = 0;
    g->p = (struct peg *)malloc((32 - removed) * sizeof(PEG));
    for(i=0;i<7;i++) {
      for(j=0;j<7;j++)
        if (b[i][j].val == 1) {
          g->p[g->max].x = i;
          g->p[g->max].y = j;
          g->max++;
        }
    }
    if (g->max != 32 - removed) {
      printf("Strange!(%d,%d)",g->max,32 - removed);
      fflush(stdout);
    }
    
    for(i=0;i<8;i++) {
      if (findBoardInDB(g,&db->l[32 - removed - 1]) != -1) {
        free(g->p);
        free(g);
        return 1;
      }
      trfGAME(1,g);
      if (i==3) trfGAME(4,g);
      qsort((void *)g->p,(size_t)g->max,sizeof(PEG),(int (__cdecl *)(const void *,const void *))comparePEG);
    }
    free(g->p);
    free(g);
    return 0;
  }
  else
  {
    
    switch (removed) {
/*
    case 32: 
      return 1;
      break;
*/
    case 31:
      if (isPeg(b,trf(0,3,3))) return 1;
      return 0;
      break;
    case 30:
      for (i=0;i<4;i++) 
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,2,3))) return 1;
        return 0;
        break;
    case 29:
      for (i=0;i<8;i++) {
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,2,2)) && isPeg(b,trf(i,2,1))) return 1;
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,3,3)) && isPeg(b,trf(i,4,3))) return 1;
      }
      return 0;
      break;
    case 28:
      for (i=0;i<8;i++) {
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,2,1)) && isPeg(b,trf(i,3,2)) && isPeg(b,trf(i,4,2))) return 1;
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,2,1)) && isPeg(b,trf(i,2,3)) && isPeg(b,trf(i,2,4))) return 1;
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,2,1)) && isPeg(b,trf(i,1,2)) && isPeg(b,trf(i,0,2))) return 1;
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,2,2)) && isPeg(b,trf(i,3,1)) && isPeg(b,trf(i,4,1))) return 1;
        if (isPeg(b,trf(i,2,1)) && isPeg(b,trf(i,2,2)) && isPeg(b,trf(i,2,3)) && isPeg(b,trf(i,3,3))) return 1;
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,4,3)) && isPeg(b,trf(i,3,4)) && isPeg(b,trf(i,3,5))) return 1;
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,3,3)) && isPeg(b,trf(i,4,4)) && isPeg(b,trf(i,4,5))) return 1;
        if (isPeg(b,trf(i,1,3)) && isPeg(b,trf(i,3,3)) && isPeg(b,trf(i,5,3)) && isPeg(b,trf(i,6,3))) return 1;
      }
      return 0;
      break;
    default:
      return -1; // return error-value when called with illegal remove-value 
      break;
    }
  }
}

struct pt searchAll(struct u **b, int removed) {
  // find alle "traekmuligheder"
  // for alle muligheder: searchAll(mulighed_i)
  // find den bedste og returner
  
  int i,i2,j,n,tmp;
  int solved=0, bestMove, bestRemoved;
  struct u **bCopy;
  struct pt *list;
  double tSize = tmpEstTreeSize;
  
  struct pt ret;
  struct pt tmppt;
  tmppt.x = 0;
  
  
#ifdef S_DEBUG
  printf("(l-e%d ",level);
  fflush(stdout);
#endif
  level++;
  
  bestMove = -1;
  bestRemoved = removed;
  
  //  lav en kopi af b
  bCopy = (struct u **)malloc(7 * sizeof(U));
  for(i=0;i<7;i++)
    bCopy[i] = (struct u *)malloc(7 * sizeof(U));
  for(i=0;i<7;i++) {
    for(j=0;j<7;j++) {
      bCopy[i][j].val = b[i][j].val;
    }
  }
  
  list = MoveList(bCopy,&n);  // find clusters og laeg dem paa liste
#ifdef S_DEBUG
  printf(" n%d ",n);
  fflush(stdout);
#endif

  if (n > 0)
    tmpEstTreeSize *= n;
  for(i=0;i<n;i++) {  // FOR ALL TRAEK
    int intRemoved,k=0;
    double tmpProgress = progress;
    
    if (level < 3) {
      printf("\n");
      while (k++ < level)
        printf(" ");
      printf("(%d/%d,%.2lf%c)",i,n,progress,p);
      fflush(stdout);
    }
    
    tmp = move(bCopy,list[i].x,list[i].y,list[i].z);
    intRemoved = removed + tmp;
    if (intRemoved == 31 && bCopy[3][3].val == 1)
      intRemoved = 32;

    if (/*intRemoved >= 28 || */(32 - intRemoved <= dblevel)) {
      if (isSolvable(bCopy,intRemoved) == 0) {
        skips++;
#ifdef S_DEBUG
        print(bCopy);
        printf("Kan ikke løses");
        system("pause");
#endif
      } else if (isSolvable(bCopy,intRemoved) == 1) {
        solutions++;
        intRemoved = 32;
#ifdef S_DEBUG
        print(bCopy);
        printf("Kan løses");
        system("pause");
#endif
      } else {
        printf("Error!! isSolvable returned error-value\n");
        exit(0);
      }
    } else {
      tmppt = searchAll(bCopy,intRemoved);
      intRemoved = tmppt.z;
    }
    progress = tmpProgress + 100 / tSize / (double)n;
    
#ifdef S_DEBUG
    printf(" ret ");
    fflush(stdout);
#endif
    
    if (intRemoved > bestRemoved) {
      bestMove = i;
      bestRemoved = intRemoved;
      if (intRemoved > mvList[level].w) {
        mvList[level].w = intRemoved;
        mvList[level].x = list[i].x;
        mvList[level].y = list[i].y;
        mvList[level].z = list[i].z;
        mvList[level].n = i;
      }
      if (intRemoved > treeBest) {
        treeBest = intRemoved;
        listMax = level+1;
      }
    }
    
    if (intRemoved == 32 || tmppt.x == 1) {
      if (tmppt.x == 0) {
        printf("Game solved, returning from level %d ...\n",level);
        fflush(stdout);
      }
      ret.x = 1; ret.y = bestMove; ret.z = bestRemoved;
      level--;
      return ret;
    }
    
    for(i2=0;i2<7;i2++) {  // restore board from recursive call alterations
      for(j=0;j<7;j++) {
        bCopy[i2][j].val = b[i2][j].val;
        //bCopy[i2][j].mark = b[i2][j].mark;
      }
    }
  }
  tmpEstTreeSize = (long)tSize;

#ifdef S_DEBUG
  printf(" loop)");
  fflush(stdout);
#endif

  if (i==0) {
    leaves++;
    if ((leaves % 100000) == 0) {
      printf(".");
      fflush(NULL);
    }
  }
  
  for(i=0;i<7;i++)
    free(bCopy[i]);
  free(bCopy); free(list);
  
  ret.x = 0; ret.y = bestMove; ret.z = bestRemoved;
  level--;
  return ret;
}

int nMoves(struct u **b) {
  int n = 0;
  int x,y,z;
  
  for (x=0;x<7;x++) {
    for(y=0;y<7;y++) {
      for(z=1;z<5;z++) {
        if (isMove(b,x,y,z))
          n++;
      }
    }
  }
  return n;
}

struct pt *MoveList(struct u **b, int *size) {
  int n = 0;
  int x,y,z;
  struct pt *list;
  list = (struct pt *)malloc(75 * sizeof(PT));
  
  for (x=0;x<7;x++) {
    for(y=0;y<7;y++) {
      for (z=1;z<5;z++) {
        if (isMove(b,x,y,z)) {
          list[n].x = x;
          list[n].y = y;
          list[n].z = z;
          n++;
        }
      }
    }
  }
  *size = n;
  list = (struct  pt *)realloc(list, n * sizeof(PT));
  return list;
}

int randintval(int low, int high)
{
  return (int) randval(low,high+1);
}

double randval(double low, double high)
{
  double val;
  val = ((double)(rand()%1000)/1000.0)*(high - low) + low;
  return(val);
}

void init_malloc(struct u **b) {
  int i;
  b = (struct u **)malloc(7 * sizeof(int));
  for(i=0;i<7;i++)
    b[i] = (struct u *)malloc(7 * sizeof(int));
}

void init_values(struct u **b) {
  int x,y;
  for (x=0;x<7;x++) {
    for(y=0;y<7;y++)
      b[x][y].val = 1;
  }
  b[0][0].val = b[0][1].val = b[1][0].val = b[1][1].val = -1;
  b[0][5].val = b[0][6].val = b[1][5].val = b[1][6].val = -1;
  b[5][0].val = b[5][1].val = b[6][0].val = b[6][1].val = -1;
  b[5][5].val = b[5][6].val = b[6][5].val = b[6][6].val = -1;

  b[3][3].val = 0;
}

void print(struct u **b) {
  int x,y;
  
  for(y=6;y>=0;y--) {
    printf("%d    ",y);
    for (x=0;x<7;x++) {
      if (b[x][y].val == 1)
        printf(" X");
      else if (b[x][y].val == 0)
        printf(" .");
      else
        printf("  ");
        printf("  ");
    }
    printf("\n|     ");
    if (y > 0)
      for (x=0;x<7;x++) {
          printf("    ");
      }
      printf("\n");
  }
  
  printf("|\n -----");
  for(x=0;x<7;x++)
    printf("%d---",x);
  printf("%d\n\n",x);  
}