#include<stdio.h>
#include<stdlib.h>
#include<locale.h>
#include<time.h>
#include<conio.h>

main()
{ char box[4][4] = {0},boxR[4][4] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};//коробка
int key, i, j; //для for
int n;//очередная фишка
wchar_t ms[][100] = {
L"не та кнопка"};
setlocale(LC_ALL, ".866");
//разложить фишки случайным образом
srand(time(0));
n = 1;
do
{
i =rand()%4;//номер строки
j =rand()%4;//номер столбца
if(box[i][j] == 0)
box[i][j] = n++;
}while(n < 16);
//цикл игры
while(1)
{

//отображаем содержимое
clear:system("cls");
for (i =0; i<4; i++)
{
for (j=0; j<4; j++)
if(box[i][j])
printf("%4d", box[i][j]);
else //4 пробела в строке ниже
printf(" ");
puts("\n") ; //на 2 строки вниз
}

if (strcmp(box, boxR) ==0)
wprintf(L"победа!!!");
//получение команды
key = getch();
//реакция на символьные клавиши
if (key == 27) break; //ESC
//реакция на управляющие клавиши
if (key == 0 || key ==224)
{
key = getch();
switch(key)
{
case 72://вверх
//поиск пустого места
for(i = 0; i<3; i++)
for(j = 0; j<4; j++)
if (box[i][j] == 0)
{
box[i][j] = box[i+1][j];
box[i+1][j] = 0;
goto clear;
}; break;
case 80://вниз
for(i = 3; i>0; i--)
for(j = 0; j<4; j++)
if (box[i][j] == 0)
{
box[i][j] = box[i-1][j];
box[i-1][j] = 0;
goto clear;
};break;
case 75://влево
for(i = 0; i<4; i++)
for(j = 0; j<3; j++)
if (box[i][j] == 0)
{
box[i][j] = box[i][j+1];
box[i][j+1] = 0;
goto clear;
}break;
case 77://вправо
for(i = 0; i<4; i++)
for(j = 1; j<4; j++)
if (box[i][j] == 0)
{
box[i][j] = box[i][j-1];
box[i][j-1] = 0;
goto clear;
}break;
goto error;
default : goto error;


}//switch





}//if

error:
wprintf(ms[rand()%(sizeof(ms)/sizeof(ms[0]))]);
system("PAUSE");
}//while


}

Про определение возможности выигрыша в конкретной комбинации можно почитать тут
Википедия

Тут есть реализация необходимого алгоритма в оконном приложении на с++. Можно взять что-то оттуда.

Большое спасибо за усовершенствование программы, но препод требует только, чтобы при нажатии на кнопку выводилась именно подсказка на 3 хода, а не программа работала сама.

Ну, это не проблема. Самое простое, вызвать функцию хода три раза, а потом откатить состояние матрицы к исходному. Например, вот так:
[code h=200]#include<stdio.h>
#include<stdlib.h>
#include<locale.h>
#include<time.h>
#include<conio.h>

char Tmp[4][4]; //временная
char Mat[4][4]; //Матрица состояния
char Res[4][4]; //Матрица результата
int Mat_Stop[4][4];
int X, Y; //Координаты пустой клетки
int X_new, Y_new; //Куда подвинуть пустую клетку
int X_old, Y_old; //Предыдущее положение пустой фишки
int iCl, jCl; //Какую фишку будем двигать на место (ее положение)
int i_new, j_new; //Нужное положение фишки
int i_tec, j_tec; //Текущее выставление клетки
int Fish;
int Stop; //Выставленно
int NeedShow; //флаг необходимости вывода
char NextTurn; //фишка для следующего хода

void Init();
void Show ();
void Poloj(char Znach);
void New_Coord();
void Dvig_Fish(int x1, int y1, int x2, int y2);
int Perem();
void Perem_New();
void DvigClick();
void Fish_Three();
void Fish_Foo();
void Sort_Str();
void Out_Old();
void OutNine(int FX, int FY, int NeX, int NeY);
void Set13(int FX, int FY, int NeX, int NeY);
void SetDown();
int HasNoSolve ();
void SaveToTmp ();
void LoadFromTmp ();

void SaveToTmp ()
{
int i, j;
for (i=0; i<4; i++)
for (j=0; j<4; j++)
Tmp[i][j] = Mat[i][j];
}

void LoadFromTmp ()
{
int i, j;
for (i=0; i<4; i++)
for (j=0; j<4; j++)
Mat[i][j] = Tmp[i][j];
}


void Init()
{//Инициализация матрицы
int idx = 1;
char i, j;
char i1;
char i2, j1, j2;
char Cap;
for (i=0; i<4; i++)
for (j=0; j<4; j++)
{ Mat[i][j] = idx;
Res[i][j] = idx;
Mat_Stop[i][j] = 0; idx++;
}
Mat[3][3] = 0; Res[3][3] = 0;

srand(time(NULL));
for (idx=0; idx<30; idx++)
{
i1=(rand()%4); j1=(rand()%4);
i2=(rand()%4); j2=(rand()%4);
Cap = Mat[i1][j1];
Mat[i1][j1] = Mat[i2][j2];
Mat[i2][j2] = Cap;
}
}

void Show ()
{
int i, j;
//отображаем содержимое
if (NeedShow) {
system("cls");
for (i =0; i<4; i++)
{
for (j=0; j<4; j++)
if(Mat[i][j])
printf("%4d", Mat[i][j]);
else //4 пробела в строке ниже
printf(" ");
puts("\n") ; //на 2 строки вниз
}
}
}

void Poloj(char Znach)
{ //Определение положения
int i,j;
int Ok=0;
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
if(Mat[i][j]==Znach) {Ok=1; break;}
if (Ok==1) break;
}
iCl = i; jCl = j;
Mat_Stop[iCl][jCl] = 1;
//Положение пустой клетки
for(i=0; i<4; i++)
for(j=0; j<4; j++)
if(Mat[i][j]==0) {X=i; Y=j;}
}
//---------------------------------------------------------------------------

void New_Coord()
{ //куда переместить пустую клетку
if(iCl>i_new && Mat_Stop[iCl-1][jCl]==0)
{ X_new=iCl-1; Y_new=jCl; return; }//Внизу нужной

if(iCl<i_new && Mat_Stop[iCl+1][jCl]==0)
{ X_new=iCl+1; Y_new=jCl; return; }//Вверху нужной

if(jCl>j_new && Mat_Stop[iCl][jCl-1]==0)
{ X_new=iCl; Y_new=jCl-1; return; }//Слева нужной

if(jCl<j_new && Mat_Stop[iCl][jCl+1]==0)
{ X_new=iCl; Y_new=jCl+1; return; }//Справа нужной

}
//---------------------------------------------------------------------------

void Dvig_Fish(int x1, int y1, int x2, int y2)
{//Смена фишек местами
char S = Mat[x1][y1];
if (Mat[x1][y1]==0) NextTurn = Mat[x2][y2];
else NextTurn = Mat[x1][y1];
Mat[x1][y1] = Mat[x2][y2];
Mat[x2][y2] = S;
}
//---------------------------------------------------------------------------

int Perem()
{//Перемещение пустой клетки
int Mark=-1;
if((X>X_new) && (X-1!=X_old)) Mark = X-1;
if((X<X_new) && (X+1!=X_old)) Mark = X+1;
if ((Mark >= 0 && Mark <= 3) && (Mark!=X && Mat_Stop[Mark][Y] == 0)) //Перестановка по горизонтали
{ Dvig_Fish(X,Y, Mark,Y); X_old=-1; Y_old=-1;
X=Mark; return 1;
}
Mark=-1;
if((Y>Y_new) && (Y-1!=Y_old)) Mark = Y-1;
if((Y<Y_new) && (Y+1!=Y_old)) Mark = Y+1;
if ((Mark >= 0 && Mark <= 3) && (Mark!=Y && Mat_Stop[X][Mark] == 0)) //Перестановка по вертикали
{ Dvig_Fish(X,Y, X,Mark); X_old=-1; Y_old=-1;
Y=Mark; return 1;
}
return 0;
}
//---------------------------------------------------------------------------

void Perem_New()
{ //перемещение куда можно
int Mark=X+1;
if((Mark>=0 && Mark<=3) && (Mat_Stop[Mark][Y]==0 && Mark!=X_old)) //Вниз
{
Dvig_Fish(X,Y, Mark,Y);
X_old=X; Y_old=Y; X=Mark; return;
}

Mark=X-1;
if((Mark>=0 && Mark<=3) && (Mat_Stop[Mark][Y]==0 && Mark!=X_old)) //Вверх
{
Dvig_Fish(X,Y, Mark,Y);
X_old=X; Y_old=Y; X=Mark; return;
}

Mark=Y+1;
if((Mark>=0 && Mark<=3) && (Mat_Stop[X][Mark]==0 && Mark!=Y_old)) //Вправо
{
Dvig_Fish(X,Y, X,Mark);
X_old=X; Y_old=Y; Y=Mark; return;
}

Mark=Y-1;
if((Mark>=0 && Mark<=3) && (Mat_Stop[X][Mark]==0 && Mark!=Y_old)) //Влево
{
Dvig_Fish(X,Y, X,Mark);
X_old=X; Y_old=Y; Y=Mark; return;
}
}
//---------------------------------------------------------------------------

void DvigClick()
{
if(Stop == 1) return;
if(i_tec>=2) {
SetDown();
// j_tec=0;
return;}
if(j_tec>4){ i_tec++; j_tec=0; Fish=0; return; }
Poloj(Res[i_tec][j_tec]);
i_new=i_tec; j_new=j_tec;
New_Coord();

if(j_tec==2 && Fish==0)
{ Mat_Stop[iCl][jCl]=0; Out_Old(); return;}//Исключение неверной ситуации
if(j_tec==2) {Fish_Three(); return;}
if(j_tec==3) {Fish_Foo(); return;}
if(j_tec==4) {Sort_Str(); return;}
if(j_tec>=2) return;
if(iCl==i_new && jCl==j_new) {j_tec++; return; }
if(X==X_new && Y==Y_new){
Mat_Stop[iCl][jCl] = 0;
Dvig_Fish(iCl,jCl, X,Y);
Show();
Poloj(Res[i_tec][j_tec]);
return;
}
if (Perem()==0) Perem_New();
Show();
}
//---------------------------------------------------------------------------

void Fish_Three()
{//Передвижение 3 и 7
Poloj(Res[i_tec][j_tec]);
i_new=i_tec; j_new=j_tec+1;
New_Coord();

if(iCl==i_new && jCl==j_new) {j_tec++; return; }
if(X==X_new && Y==Y_new){
Mat_Stop[iCl][jCl] = 0;
Dvig_Fish(iCl,jCl, X,Y);
Show();
Poloj(Res[i_tec][j_tec]);
return;
}
if (Perem()==0) Perem_New();
Show();
}
//---------------------------------------------------------------------------

void Fish_Foo()
{//Передвижение 4 и 8
Poloj(Res[i_tec][j_tec]);
i_new=i_tec+1; j_new=j_tec;
New_Coord();

if(iCl==i_new && jCl==j_new) {j_tec++; return; }
if(X==X_new && Y==Y_new){
Mat_Stop[iCl][jCl] = 0;
Dvig_Fish(iCl,jCl, X,Y);
Show();
Poloj(Res[i_tec][j_tec]);
return;
}
if (Perem()==0) Perem_New();
Show();
}
//---------------------------------------------------------------------------

void Sort_Str()
{ //Сборка строки
Mat_Stop[i_tec][2] = 0;
X_new=i_tec; Y_new=2;
if (Perem()==0) Perem_New();
Show();
if(X==X_new && Y==Y_new){
Dvig_Fish(i_tec, 3, X,Y); X=i_tec; Y=3;
Mat_Stop[i_tec][2] = 1;
Show();
Dvig_Fish(i_tec+1, 3, X,Y);
Mat_Stop[i_tec+1][3] = 0;
Show();
i_tec++; j_tec=0; Fish=0;
}
}
//---------------------------------------------------------------------------

void Out_Old()
{//Исключение неопределенной ситуации
Poloj(Res[i_tec][3]);
Fish = 0;
if(iCl==3 && jCl==0) {
Mat_Stop[3][0] = 0;
Fish=1; return; }
else{
i_new=3; j_new=0;
New_Coord();
if(X==X_new && Y==Y_new){
Mat_Stop[iCl][jCl] = 0;
Dvig_Fish(iCl,jCl, X,Y);
Show();
return;
}
if (Perem()==0) Perem_New();
Show();
}
}
//---------------------------------------------------------------------------



void OutNine(int FX, int FY, int NeX, int NeY)
{ //Исключение неопредленной ситуации с 9 и 11
Poloj(Res[FX][FY]);
if(iCl==NeX && jCl==NeY) {
Mat_Stop[NeX][NeY] = 0;
j_tec++; return; }
else{
i_new=NeX; j_new=NeY;
New_Coord();
if(X==X_new && Y==Y_new){
Mat_Stop[iCl][jCl] = 0;
Dvig_Fish(iCl,jCl, X,Y);
Show();
return;
}
if (Perem()==0) Perem_New();
Show();
}
}
//---------------------------------------------------------------------------

void Set13(int FX, int FY, int NeX, int NeY)
{//Установка 13 фишки
Poloj(Res[FX][FY]);
i_new=NeX; j_new=NeY;
New_Coord();

if(iCl==i_new && jCl==j_new){ j_tec++; return; }
if(X==X_new && Y==Y_new){
Mat_Stop[iCl][jCl] = 0;
Dvig_Fish(iCl,jCl, X,Y);
Show();
Poloj(Res[FX][FY]);
return;
}
if (Perem()==0) Perem_New();
Show();
}
//---------------------------------------------------------------------------

int Ni (int bone)
{
int i, k = 0;
for (i=bone+1; i<16; i++)
if (*(Mat+i)<*(Mat+bone)) k++;
return k;
}

int HasNoSolve () //возвращает 1, если решений для текущего расклада нет
{
int n = 0, i;
for (i=0; i<15; i++) {
if (*(Mat+i)!=0) n+=Ni(i);
else n+=((int)i/4)+1;
}
return n%2!=0;
}

void SetDown()
{
//Расстановка нижних 2-х рядов
if(Stop == 1) return; //Если выставленно
if(j_tec==0) {OutNine(2,0, 3,3); return; } //9 на позиц. пустой
if(j_tec==1) {Set13(3,0, 2,0); return;} //13 на поз 9
if(j_tec==2) {Set13(2,0, 2,1); return;} //9 на поз 10
if(j_tec==3) {Set13(3,0, 3,0); return; } //13 и 9 на места
if(j_tec==4) {Set13(2,0, 2,0); return; }

if(j_tec==5) {OutNine(2,2, 2,1); return; } //11 на 10
if(j_tec==6) {Set13(2,1, 3,3); return;} //Установка 10 на пустую
if(j_tec==7) {Set13(2,2, 3,2); return;} //Установка 11 на поз 15
if(j_tec==8) {Set13(2,1, 2,3); return;} //Установка 10 на позицию 12
if(j_tec==9) {Set13(2,2, 3,3); return;} //Установка 11 на пустую
if(j_tec==10) {Set13(2,3, 3,2); return;} //12 на 15
if(j_tec==11){Set13(2,1, 2,2); return;} //10 на 11
if(j_tec==12){Set13(2,2, 2,3); return;} //11 на 12
if(j_tec==13){Set13(2,3, 3,3); return;} //12 на пусто
if(j_tec==14){Set13(2,1, 2,1); return;} //10 на 11
if(j_tec==15){Set13(2,2, 2,2); return;} //11 на 12
if(j_tec==16){Set13(2,3, 2,3); return;} //12 на пусто
Stop = 1;
}


main()
{
char box[4][4] = {0},boxR[4][4] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};//коробка
wchar_t ms[][100] = {
L"не та кнопка"};
int key, i, j; //для for
int n;//очередная фишка
X_old=-1; Y_old=-1;
X_new=0; Y_new=0;
i_tec=0; j_tec=0;
Fish = 0;
Stop = 0;
NeedShow = 1;

setlocale(LC_ALL, ".866");
// //разложить фишки случайным образом
// srand(time(0));
// n = 1;
// do
// {
// i =rand()%4;//номер строки
// j =rand()%4;//номер столбца
// if(box[i][j] == 0)
// box[i][j] = n++;
// }while(n < 16);
// //цикл игры
Init ();
while(1)
{

//отображаем содержимое
clear:
NeedShow = 1;
Show();
if (strcmp(Mat, boxR) ==0)
wprintf(L"победа!!!");
if (HasNoSolve())
wprintf(L"Решения нет!");
//получение команды
key = getch();
//реакция на символьные клавиши
if (key == 27) break; //ESC
//реакция на управляющие клавиши
if (key == 0 || key ==224)
{
key = getch();
switch(key)
{
case 59: //F1
SaveToTmp(); //сохраняем состояние
NeedShow = 0; //пока рассчитывается подсказка, отключаем вывод матрицы
wprintf(L"Подсказка: ");
for (i=0; i<3; i++) {
DvigClick (); //делаем три хода
printf ("%4d,", NextTurn);
}
system("pause");
LoadFromTmp(); //загружаем исходное состояние
goto clear;
break;
case 72://вверх
//поиск пустого места
for(i = 0; i<3; i++)
for(j = 0; j<4; j++)
if (Mat[i][j] == 0)
{
Mat[i][j] = Mat[i+1][j];
Mat[i+1][j] = 0;
goto clear;
}; break;
case 80://вниз
for(i = 3; i>0; i--)
for(j = 0; j<4; j++)
if (Mat[i][j] == 0)
{
Mat[i][j] = Mat[i-1][j];
Mat[i-1][j] = 0;
goto clear;
};break;
case 75://влево
for(i = 0; i<4; i++)
for(j = 0; j<3; j++)
if (Mat[i][j] == 0)
{
Mat[i][j] = Mat[i][j+1];
Mat[i][j+1] = 0;
goto clear;
}break;
case 77://вправо
for(i = 0; i<4; i++)
for(j = 1; j<4; j++)
if (Mat[i][j] == 0)
{
Mat[i][j] = Mat[i][j-1];
Mat[i][j-1] = 0;
goto clear;
}break;
goto error;
default : goto error;


}//switch





}//if

error:
wprintf(ms[rand()%(sizeof(ms)/sizeof(ms[0]))]);
system("PAUSE");
}//while


}

[/code]
Пойдёт?

Большое спасибо, то что нужно.