/* solitaer solver
 * author: Werner Hoch
 * licence: public domain
 */

#include <stdio.h>
#include <inttypes.h>
#include <time.h>

#define TEST 0

/************************** GLOBALS *************************/
#define STATE_FILE "state.txt"
#define PRINTTIME 10.0

uint64_t jumps_mask[109];
uint64_t jumps_pins[109];
uint64_t field;
int successor[109][109];
int move_nr;
int moves[45];
uint64_t count_moves=0;
uint64_t solutions=0;
int moves_per_sec=0;

int position_to_bit[9][9];
int bit_to_position[45][2]; /* x=lowest byte, y=next byte */

/*************************** FUNCTIONS *************************/
void 
save_state() {
  FILE *f;
  int i;
  f=fopen(STATE_FILE,"wt");
  fprintf(f,"%llu\n",field);
  fprintf(f,"%llu\n",solutions);
  fprintf(f,"%llu\n",count_moves);
  fprintf(f,"%i\n",move_nr);
  for (i=0; i<45; i++)
    fprintf(f,"%i\n",moves[i]);
  fclose(f);
}

void
save_result() {
  int i;
  FILE *f;
  solutions++;
  f=fopen("solitaer_result.txt","at");
  fprintf(f,"solution %llu: movecount=%llu: ",solutions, count_moves);
  for (i=0; i< 44; i++) {
    fprintf(f," %i",moves[i]);
  }
  fprintf(f,"\n");
  fclose(f);
}

int
load_state() {
  FILE *f;
  int i;
  if ((f=fopen(STATE_FILE,"rt"))==NULL)
    return -1;
  fscanf(f,"%llu\n",&field);
  fscanf(f,"%llu\n",&solutions);
  fscanf(f,"%llu\n",&count_moves);
  fscanf(f,"%i\n",&move_nr);
  for (i=0; i<45; i++)
    fscanf(f,"%i\n",&(moves[i]));
  fclose(f);
  return 0;
}

void
reset() {
  int i;
  move_nr=0;
  field=0;
  for (i=0;i<45; i++) {
    field |= (uint64_t) 1<<i;
  }
  field &= ~ ((uint64_t)  1<<22); /* clear center pin */
  for (i=0; i<45; i++)
    moves[i]=0;
}

void
setup() {
  int x,y,i,j;
  int num=0;
  int position, prev;
  for (y=0; y<9; y++) {
    for (x=0; x<9; x++) {
      if (x>2 && x<6 || y>2 && y<6) {/* inside the field cross */
	position_to_bit[x][y]=num;
	bit_to_position[num][0]=x;
	bit_to_position[num][1]=y;
	num++;
      }
      else {
	position_to_bit[x][y]= -1; /* mark fields outside */
      }
    }
  }

#if TEST
  for (y=0; y<9; y++) {
    for (x=0; x<9; x++) {
      printf("%3i ",position_to_bit[x][y]);
    }
    printf("\n");
  }
  for (i=0; i<45; i++) {
    printf("bit_to_position[%i]: x=%i, y=%i\n",i,
	   bit_to_position[i][0],bit_to_position[i][1]);
  }  
#endif
  /* create the list of posible moves */
  num=1;
  for (position=0; position<45; position++) {
    x=bit_to_position[position][0];
    y=bit_to_position[position][1];

    /* move to the top: */
    if (bit_to_position[position][1]>1) { /* enough space on the top side */
      if (position_to_bit[x][y-2] >=0) {
	jumps_mask[num]=((uint64_t) 1<<position_to_bit[x][y-2] 
			 | (uint64_t) 1<<position_to_bit[x][y-1]
			 | (uint64_t) 1<<position_to_bit[x][y-0]);
	jumps_pins[num]=((uint64_t) 1<<position_to_bit[x][y-1]  
			 | (uint64_t) 1<<position_to_bit[x][y-0]);
	num++;
      }
    }

    /* move to the left: */
    if (bit_to_position[position][0]>1) { /* enough space on the left side */
      if (position_to_bit[x-2][y] >=0) {
	jumps_mask[num]=((uint64_t) 1<<position_to_bit[x-2][y] 
			 | (uint64_t) 1<<position_to_bit[x-1][y]
			 | (uint64_t) 1<<position_to_bit[x-0][y]);
	jumps_pins[num]=((uint64_t) 1<<position_to_bit[x-1][y] 
			 | (uint64_t) 1<<position_to_bit[x-0][y]);
	num++;
      }
    }

    /* move to the bottom: */
    if (bit_to_position[position][1]<7) { /* enough space on the bottom side */
      if (position_to_bit[x][y+2] >=0) {
	jumps_mask[num]=((uint64_t) 1<<position_to_bit[x][y+2] 
			 | (uint64_t) 1<<position_to_bit[x][y+1]
			 | (uint64_t) 1<<position_to_bit[x][y+0]);
	jumps_pins[num]=((uint64_t) 1<<position_to_bit[x][y+1] 
			 | (uint64_t) 1<<position_to_bit[x][y+0]);
	num++;
      }
    }
    /* move to the right: */
    if (bit_to_position[position][0]<7) { /* enough space on the right side */
      if (position_to_bit[x+2][y] >=0) { 
	jumps_mask[num]=((uint64_t) 1<<position_to_bit[x+2][y] 
			 | (uint64_t) 1<<position_to_bit[x+1][y]
			 | (uint64_t) 1<<position_to_bit[x+0][y]);
	jumps_pins[num]=((uint64_t) 1<<position_to_bit[x+1][y] 
			 | (uint64_t) 1<<position_to_bit[x+0][y]);
	num++;
      }
    }
  }
#if TEST
  for (num=1; num < 109; num++)
    printf("jumps_mask[%i]=%16llX jumps_pins[%i]=%16llX\n",
	   num, jumps_mask[num], num, jumps_pins[num]);
#endif
  /* create the table of good successor moves */
  for (i=1; i<109; i++) {
    prev=0;
    for (j=1; j<109; j++) {
      if (((i<j)   /* only use the lower move if two moves don't intersect */
	   || jumps_mask[i] & jumps_mask[j])
	  && !(jumps_mask[i] & jumps_mask[j]   /* impossible moves */ 
	       & ~(jumps_pins[i]^jumps_pins[j]))) {
	successor[i][prev]=j;
	prev=j;
      }
      else {
	successor[i][j]=0;
      }
    }
    successor[i][prev]=0;
  }
  for (j=0; j<108; j++)
    successor[0][j]=j+1;
  successor[0][108]=0;
  
#if TEST
  for (i=0; i<109; i++) {
    for (j=0; j<109; j++) {
      printf("%3i ",successor[i][j]);
    }
    printf("\n");
  }
#endif
}


void
draw() {
  int x,y,i;
  char area[9][9];
  printf("\n Solitaer Solution Finder \n");
  for (y=0; y<9; y++)
    for (x=0; x<9; x++)
      area[x][y]=' ';
  for (i=0; i<45; i++) {
    if (((uint64_t) 1<<i) & field)
      area[bit_to_position[i][0]][bit_to_position[i][1]]='X';
    else
      area[bit_to_position[i][0]][bit_to_position[i][1]]='0';
  }
  for (y=0; y<9; y++) {
    printf("\n    ");
    for (x=0; x<9; x++)
      printf(" %c",area[x][y]);
  }
  printf("\n\nmovecount: %llu, solutions: %llu, moves/sec: %i\nmoves: ",
	 count_moves, solutions, moves_per_sec);
  for (i=0; i<44; i++)
    printf("%i ",moves[i]);
  printf("\n");
}

int 
simulate(uint64_t count) {
  int n, go_on;
  while (count_moves < count) {
    /* generate next possible move */
    moves[move_nr]=successor[moves[move_nr-1]][moves[move_nr]];
    /* no moves are left, go one step back */
    if (!moves[move_nr]) {
      if (move_nr > 42) {
	printf("new result found\n");
	save_result();
	draw();
      }
      moves[move_nr]=0;
      move_nr--;
      field ^= (uint64_t) jumps_mask[moves[move_nr]];

#if TEST
      printf("step back\n");
      draw();
#endif
    }
    else {
      /* check if the move is ok and move */
      if (!((field ^ jumps_pins[moves[move_nr]])
	    & jumps_mask[moves[move_nr]])) {
	for (n=move_nr-1, go_on=1; n >=0; n--) {
	  if (jumps_mask[moves[move_nr]] & jumps_mask[moves[n]])
	    break;
	  if (moves[n] > moves[move_nr]) {
	    go_on=0;
	    break;
	  }
	}
	if (go_on) {
	  field ^= (uint64_t) jumps_mask[moves[move_nr]];
	  move_nr++;
	  count_moves++;
#if TEST      
	  draw();
#endif
	}
      }
    }
  }
  return 1;
}



/************************* MAIN *************************/

int
main() {
  int increment=10000;
  float delta_t;
  int clk1, clk2;
  setup();
  if (load_state() < 0)
    reset();

  while (1)    {
    clk1=clock(); 
    simulate(count_moves+increment);
    draw();
    save_state();
    clk2=clock();
    delta_t=(float)(clk2-clk1)/CLOCKS_PER_SEC; 
    moves_per_sec=(float) increment/ delta_t;
    /* regulate the turns, so that the computer needs the calculating time 
       that is eqal to PRINTTIME  */
    increment = (float)increment*(PRINTTIME+1)/(delta_t+1);
  }
  return 0;
}