Perfetto! Ti ringrazio per l'aiuto, questo dovrebbe essere il codice finale :

codice:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

void crea_matrice_ordinata(int [][4]);
void crea_matrice_random(int [][4]);
void stampa_matrice(int [][4]);
void muovi_numero(int [][4]);
int appartiene_a2D(int n, int [][4]);
int vittoria(int [][4], int [][4]);

int matrice[4][4];
int matrice_random[4][4];
int mossa=1;

int main()
{
    crea_matrice_random(matrice_random);
    crea_matrice_ordinata(matrice);
    stampa_matrice(matrice_random);

    while(mossa<=30 || vittoria(matrice_random,matrice))
    {
        muovi_numero(matrice_random);
        system("cls");
        stampa_matrice(matrice_random);
        mossa++;
    }

    if(mossa>=30)
        printf("\n\nGAME OVER!! Hai raggiunto le 30 mosse possibili.\n");
    else if(vittoria(matrice_random,matrice))
        printf("\n\nCOMPLIMENTI!! Hai ordinato tutti i numeri alla %d-esima mossa\n", mossa);

    return 0;
}

void crea_matrice_ordinata(int campo[][4])
{
    int x,y;
    int i=1;
    for(x=0;x<4;x++)
        for(y=0;y<4;y++)
        {
            campo[x][y]=i;
            if(campo[x][y]==16)
                campo[x][y]=0;
            i++;
        }
}
void crea_matrice_random(int campo[][4])
{
    int i,x,y;
    srand(time(NULL));
    for(i=0;i<16;i++)
        {
            x=rand()%4;
            y=rand()%4;
            if(campo[x][y])
                i--;
            else
                campo[x][y]=i;
        }
}

void stampa_matrice(int campo[][4])
{
    int x,y;
    for(x=0;x<4;x++)
    {
        for(y=0;y<4;y++)
        {
            if(campo[x][y]==0)
                printf("%7c",255);
            else
                printf("%7d",campo[x][y]);
        }
        printf("\n\n\n\n");
    }
}

void muovi_numero(int campo[][4])
{
    int x,y,n;
    printf("\n\n\n\nMossa numero: %d\n",mossa);
    printf("Digita il numero da spostare: ");
    scanf("%d",&n);
    if(appartiene_a2D(n,campo) && n!=0)
    {
        for(x=0;x<4;x++)
        {
            for(y=0;y<4;y++)
            {
                if(campo[x][y]==0)
                {
                    if(campo[x][y+1]==n  && y+1<=3)
                    {
                        campo[x][y]=n;
                        campo[x][y+1]=0;
                        return;
                    }
                    else if(campo[x][y-1]==n && y>=0)
                    {
                        campo[x][y]=n;
                        campo[x][y-1]=0;
                        return;
                    }
                    else if(campo[x+1][y]==n  && x+1<=3)
                    {
                        campo[x][y]=n;
                        campo[x+1][y]=0;
                        return;
                    }
                    else if(campo[x-1][y]==n && x>=0)
                    {
                        campo[x][y]=n;
                        campo[x-1][y]=0;
                        return;
                    }
                    else
                    {
                        printf("\n\nERRORE!! Il numero %d non puo' essere spostato\n\n",n);
                        muovi_numero(campo);

                    }
                }
            }
        }
    }
    else
    {
        printf("\nERRORE!! Devi digitare un numero da 1 a 15.\n");
        muovi_numero(campo);
    }
}

int appartiene_a2D(int n, int campo[][4])
{
    int r,c;
    for(r=0;r<4;r++)
        for(c=0;c<4;c++)
            if(n==campo[r][c])
                return 1;
    return 0;
}

int vittoria(int campo[][4], int campo_ordinato[0][4])
{
    int x,y;
    for(x=0;x<4;x++)
        for(y=0;y<4;y++)
            if(campo[x][y]!=campo_ordinato[x][y])
                return 0;
    return 1;
}
Ho aggiunto anche lo condizioni nei vari if che mi permettono di non sforare le caselle della matrice, come da te suggerito