[k0nt3]

una soluzione con la tabella di hash può essere la seguente (nella fattispecie si tratta di double hashing):

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

#define MAX_PEDINE 20
#define NUM_ROWS 15
#define NUM_COLS 15

//#define DEBUG

typedef struct Pedina {
  int colore;
  int x, y;
} Pedina;

int hashFunction(int x, int y);
int probeFunction(int x, int y, int i);
int insertPedina(int x, int y, Pedina* ht[]);
void printScacchiera(Pedina* ht[]);

int main(int argc, char* argv[])
{
  Pedina* hashTable[MAX_PEDINE];

  int i=0;
  for(i; i<MAX_PEDINE; ++i)
    hashTable[i] = NULL;

  insertPedina(1, 1, hashTable);
  insertPedina(2, 2, hashTable);
  insertPedina(4, 4, hashTable);
  printScacchiera(hashTable);
  return EXIT_SUCCESS;
}

int hashFunction(int x, int y)
{
  return (x*NUM_ROWS + y*NUM_COLS)%MAX_PEDINE;
}

int probeFunction(int x, int y, int i)
{
  return (i*(2*x-y))%MAX_PEDINE;
}

int insertPedina(int x, int y, Pedina* ht[])
{
  Pedina* p = (Pedina*)malloc(sizeof(Pedina));
  p->x = x;
  p->y = y;
  int h = hashFunction(x, y);
  #ifdef DEBUG
    printf("hash: %d\n", h);
  #endif
  if(ht[h] == NULL)
  {
    ht[h] = p;
    return 0;
  }
  else
  {
    int i = 1;
    int j = 0;
    h = probeFunction(x, y, i);
    #ifdef DEBUG
      printf("probe(%d): %d\n", i, h);
    #endif
    while(ht[h] != NULL && j++ < MAX_PEDINE)
    {
      h = probeFunction(x, y, ++i);
      #ifdef DEBUG
	printf("probe(%d): %d\n", i, h);
      #endif
    }

    if(j > MAX_PEDINE)
      return -1;

    ht[h] = p;
    return i;
  }
}

void printScacchiera(Pedina* ht[])
{
  int i=0;
  for(i; i<MAX_PEDINE; ++i)
  {
    if(ht[i] != NULL)
      printf("pedina in (%d, %d)\n", ht[i]->x, ht[i]->y);
  }
}

ma secondo me ti complichi la vita e basta. IMHO la matrice rimane la scelta migliore se non stiamo parlando di una scacchiera immensa con pochissime pedine.
tra l'altro non c'è motivo di ottimizzare prima di aver riscontrato un qualsiasi problema prestazionale
un tale di nome Donald diceva: "Early optimisation is the root of all evil"