mixster

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

#define PIECE_NP 0
#define PIECE_P1 1
#define PIECE_P2 2
#define PIECE_P3 3
#define PIECE_P4 4
#define PIECE_PB 5
#define PIECE_PR 6
#define PIECE_PK 7
#define PIECE_PQ 8
#define PIECE_PJ 9

#define BOARD_WIDTH 6
#define BOARD_HEIGHT 6

struct Tile {
  int x;
  int y;
  int piece;
  int valid;
  struct Tile **child;
  int num_child;
};

int high_moves = 0;
struct Tile *best_moves;
unsigned long long counter = 0;

char piece_to_chr(int piece) {
  switch(piece) {
    case PIECE_NP: return ' ';
    case PIECE_P1: return '1';
    case PIECE_P2: return '2';
    case PIECE_P3: return '3';
    case PIECE_P4: return '4';
    case PIECE_PB: return 'B';
    case PIECE_PR: return 'R';
    case PIECE_PK: return 'K';
    case PIECE_PQ: return 'Q';
    case PIECE_PJ: return 'J';
    default      : return 'E';
  }
}

int chr_to_piece(char piece) {
  switch(piece) {
    case '0': return PIECE_NP;
    case '1': return PIECE_P1;
    case '2': return PIECE_P2;
    case '3': return PIECE_P3;
    case '4': return PIECE_P4;
    case 'B': return PIECE_PB;
    case 'R': return PIECE_PR;
    case 'K': return PIECE_PK;
    case 'Q': return PIECE_PQ;
    case 'J': return PIECE_PJ;
    default : return PIECE_NP;
  }
}

int tile_valid(int a, int b) {
  return ((b >= 0) && (b < BOARD_HEIGHT) && (a >= 0) && (a < BOARD_WIDTH));
}

void append_tile(struct Tile ***board, struct Tile *tile, int x, int y, int a, int b) {
  if (((b != y) || (a != x)) && tile_valid(a, b)) {
    tile->child[tile->num_child] = &((*board)[b][a]);
    tile->num_child++;
  }
}

void assign_normal_move(struct Tile ***board, int x, int y) {
  int n = 0;
  int b;
  int a;
  struct Tile *tile = &((*board)[y][x]);

  switch (tile->piece) {
    case PIECE_P1: n = 1;
                   break;
    case PIECE_P2: n = 2;
                   break;
    case PIECE_P3: n = 3;
                   break;
    case PIECE_P4: n = 4;
                   break;
  }

  tile->num_child = 0;

  for (b = y - n; b <= y + n; b += n) {
    for (a = x - n; a <= x + n; a += n) {
      append_tile(board, tile, x, y, a, b);
    }
  }
}

void assign_bishop_move(struct Tile ***board, int x, int y) {
  int a = 0;
  int b = 0;
  struct Tile *tile = &((*board)[y][x]);

  b = y - x;
  append_tile(board, tile, x, y, a, b);

  b = y + x;
  append_tile(board, tile, x, y, a, b);

  a = BOARD_WIDTH - 1;
  b = (y + BOARD_WIDTH) - (x + 1);
  append_tile(board, tile, x, y, a, b);

  b = (y + x + 1) - BOARD_WIDTH;
  append_tile(board, tile, x, y, a, b);

  a = x - y;
  b = 0;
  append_tile(board, tile, x, y, a, b);

  a = x + y;
  append_tile(board, tile, x, y, a, b);

  a = (x + BOARD_HEIGHT) - (y + 1);
  b = BOARD_HEIGHT - 1;
  append_tile(board, tile, x, y, a, b);

  a = (x + y + 1) - BOARD_HEIGHT;
  append_tile(board, tile, x, y, a, b);
}

void assign_rook_move(struct Tile ***board, int x, int y) {
  int a;
  int b;
  struct Tile *tile = &((*board)[y][x]);

  a = 0;
  b = y;
  append_tile(board, tile, x, y, a, b);

  a = BOARD_WIDTH - 1;
  append_tile(board, tile, x, y, a, b);

  a = x;
  b = 0;
  append_tile(board, tile, x, y, a, b);

  b = BOARD_HEIGHT - 1;
  append_tile(board, tile, x, y, a, b);
}

void assign_knight_move(struct Tile ***board, int x, int y) {
  int a;
  int b;
  struct Tile *tile = &((*board)[y][x]);

  a = x - 2;
  b = y - 1;
  append_tile(board, tile, x, y, a, b);

  b = y + 1;
  append_tile(board, tile, x, y, a, b);

  a = x + 2;
  b = y - 1;
  append_tile(board, tile, x, y, a, b);

  b = y + 1;
  append_tile(board, tile, x, y, a, b);

  a = x - 1;
  b = y - 2;
  append_tile(board, tile, x, y, a, b);

  a = x + 1;
  append_tile(board, tile, x, y, a, b);

  a = x - 1;
  b = y + 2;
  append_tile(board, tile, x, y, a, b);

  a = x + 1;
  append_tile(board, tile, x, y, a, b);
}

void assign_queen_move(struct Tile ***board, int x, int y) {
  int a;
  int b;

  assign_bishop_move(board, x, y);
  assign_rook_move(board, x, y);
}

void assign_joker_move(struct Tile ***board, int x, int y) {
  int a;
  int b;
  struct Tile *tile = &((*board)[y][x]);

  tile->num_child = 0;

  for (b = 0; b < BOARD_HEIGHT; b++) {
    for (a = 0; a < BOARD_WIDTH; a++) {
      append_tile(board, tile, x, y, a, b);
    }
  }
}

void assign_possible_moves(struct Tile ***board, int x, int y) {
  struct Tile *tile = &((*board)[y][x]);

  switch (tile->piece) {
    case PIECE_P1:
    case PIECE_P2:
    case PIECE_P3:
    case PIECE_P4: assign_normal_move(board, x, y);
                   break;
    case PIECE_PB: assign_bishop_move(board, x, y);
                   break;
    case PIECE_PR: assign_rook_move(board, x, y);
                   break;
    case PIECE_PK: assign_knight_move(board, x, y);
                   break;
    case PIECE_PQ: assign_queen_move(board, x, y);
                   break;
    case PIECE_PJ: assign_joker_move(board, x, y);
                   break;
    default      : printf("Unknown piece\n");
  }
}

void print_board(struct Tile **board) {
  int x;
  int y;

  printf("   |");
  for (x = 0; x < BOARD_WIDTH; x++) {
    printf(" %d |", x);
  }
  printf("\n---");
  for (x = 0; x < BOARD_WIDTH; x++) {
    printf("+---");
  }
  printf("+\n");

  for (y = 0; y < BOARD_HEIGHT; y++) {
    printf(" %d |", y);
    for (x = 0; x < BOARD_WIDTH; x++) {
      printf(" %c |", piece_to_chr(board[y][x].piece));
    }
    printf("\n---");
    for (x = 0; x < BOARD_WIDTH; x++) {
      printf("+---");
    }
    printf("+\n");
  }
}

void parse_board(struct Tile ***board) {
  char inp [BOARD_WIDTH];
  int x;
  int y;

  for (y = 0; y < BOARD_HEIGHT; y++) {
    scanf("%s", inp);
    for (x = 0; x < BOARD_WIDTH; x++) {
      (*board)[y][x].piece = chr_to_piece(inp[x]);
      assign_possible_moves(board, x, y);
    }
  }
}

int get_move(struct Tile ***board, int x, int y, int depth, struct Tile *res[BOARD_HEIGHT * BOARD_WIDTH]) {
  int m;
  res[depth] = &((*board)[y][x]);
  counter += 1;

  if (depth > high_moves) {
    high_moves = depth;
    for (m = 0; m <= depth; m++) {
      best_moves[m] = *(res[m]);
    }

    //printf("Best now %d moves\n", (depth + 1));
  }

  if ((depth + 1) == (BOARD_HEIGHT * BOARD_WIDTH)) {
    return 1; // Should be 1
  }

  for (m = 0; m < (*board)[y][x].num_child; m++) {
    if ((*board)[y][x].child[m]->valid) {
      (*board)[y][x].child[m]->valid = 0;
      if (get_move(board, (*board)[y][x].child[m]->x, (*board)[y][x].child[m]->y, depth + 1, res)) {
        return 1;
      }
      res[depth]->child[m]->valid = 1;
    }
  }
  return 0;
}

void find_move(struct Tile **board) {
  int x;
  int y;
  struct Tile *res[BOARD_HEIGHT * BOARD_WIDTH];

  srand((unsigned)(time(0)));
  x = rand() % BOARD_WIDTH;
  y = rand() % BOARD_HEIGHT;

  printf(">> %d, %d\n", x, y);

  if (board[y][x].valid) {
    board[y][x].valid = 0;
    if (get_move(&board, x, y, 0, res)) {
      return;
    }
    board[y][x].valid = 1;
  }
}

void find_new_move(struct Tile **board, int x, int y, int pie) {
  struct Tile temp = board[y][x];
  struct Tile temp2;
  struct Tile **res;
  int m;

  res = (struct Tile**) malloc(BOARD_WIDTH * BOARD_HEIGHT * sizeof(struct Tile*));

  board[y][x].piece = pie;
  assign_possible_moves(&board, x, y);

  temp2 = board[y][x];
  board[y][x] = temp;

  for (m = 0; m < temp2.num_child; m++) {
    if (temp2.child[m]->valid) {
      temp2.child[m]->valid = 0;
      if (get_move(&board, temp2.child[m]->x, temp2.child[m]->y, 0, res)) {
        free(res);
        return;
      }
      temp2.child[m]->valid = 1;
    }
  }
}

void print_moves(struct Tile *res, int depth) {
  int m;

  for (m = 0; m <= depth; m++) {
    printf("%d: %c - %d, %d\n", (m + 1), piece_to_chr(res[m].piece), res[m].x, res[m].y);
  }
}

void ex_program(int sig) {
  printf("Cought signal: %d\n", sig);
  printf("Best solution came to %d moves\n", (high_moves + 1));
  print_moves(best_moves, high_moves);
  printf("Counter says % llu\n", counter);
  (void) signal(SIGINT, SIG_DFL);
}

int main()
{
  struct Tile **board;
  int x;
  int y;
  int a;
  int b;
 (void) signal(SIGINT, ex_program);

  best_moves = (struct Tile*) malloc(BOARD_WIDTH * BOARD_HEIGHT * sizeof(struct Tile));

  board = (struct Tile**) malloc(BOARD_HEIGHT * sizeof(struct Tile*));
  for (y = 0; y < BOARD_HEIGHT; y++) {
      board[y] = (struct Tile*) malloc(BOARD_WIDTH * sizeof(struct Tile));
      for (x = 0; x < BOARD_WIDTH; x++) {
        board[y][x].x = x;
        board[y][x].y = y;
        board[y][x].piece = PIECE_NP;
        board[y][x].valid = 1;
        board[y][x].num_child = 0;
        board[y][x].child = (struct Tile**) malloc(BOARD_WIDTH * BOARD_HEIGHT * sizeof(struct Tile*));
      }
  }

  parse_board(&board);
  print_board(board);

  find_move(board);
  //find_new_move(board, 4, 2, PIECE_P4);
  print_moves(best_moves, high_moves);

  free(best_moves);
  for (y = 0; y < BOARD_HEIGHT; y++) {
    free(board[y]);
  }

  printf("Counter says % llu\n", counter);
  return 0;
}