Language: C++

#include <iostream>
#include <string>
#include <stdio.h> 	 //printf
#include <stdlib.h> 	 //system("cls")：画面クリア
#include <time.h>	 //ランダム設定用
using namespace std;

static const int kBoardWidth = 4;
static const int kBoardHeight = 4;
static const int kSpaceNum = 16;

struct Puzzle {
	int x_pos_;
	int y_pos_;
};

static int board[kBoardHeight][kBoardWidth];

void CreatBoard(){
	for (int y = 0; y < kBoardHeight; y++){
		for (int x = 0; x < kBoardWidth; x++){
			board[y][x] = y*kBoardWidth + x + 1;
		}
	}
}
Puzzle GetSpacePos(){
	Puzzle space_pos = {-1,-1};
	for (int y = 0; y < kBoardHeight; y++){
		for (int x = 0; x < kBoardWidth; x++){
			if(board[y][x] == kSpaceNum){
				space_pos = {x,y};
			}
		}
	}
	return space_pos;
}
void MoveToSpace(Puzzle move_pos){
	if( !(0 <= move_pos.x_pos_ && move_pos.x_pos_ < kBoardWidth) ||
		 !(0 <= move_pos.y_pos_ && move_pos.y_pos_ < kBoardHeight) ){
		return;
	}
	Puzzle space_pos = GetSpacePos();
	int tmp_space_pos = board[space_pos.y_pos_][space_pos.x_pos_];
	board[space_pos.y_pos_][space_pos.x_pos_] = board[move_pos.y_pos_][move_pos.x_pos_];
	board[move_pos.y_pos_][move_pos.x_pos_] = tmp_space_pos;
}
void ShuffleBoard(){
	srand((unsigned)time(NULL));
	for(int i = 0; i < 100; ++i){
		Puzzle move_pos = GetSpacePos();
		string command = "";
		switch(rand() % 4){
		case 0:
			move_pos.y_pos_++;
			break;
		case 1:
			move_pos.y_pos_--;
			break;
		case 2:
			move_pos.x_pos_++;
			break;
		case 3:
			move_pos.x_pos_--;
			break;
		}
		MoveToSpace(move_pos);
	}
}
void JudgeClearGame(){
	bool is_clear = true;
	for (int y = 0; y < kBoardHeight; y++){
		for (int x = 0; x < kBoardWidth; x++){
			if(board[y][x] != y*kBoardWidth + x + 1){
				is_clear = false;
			}
		}
	}
	if(is_clear){
		cout << "Congratulations!!!" << endl;
	}
}
void PrintNowBoard(){
	cout << "+--+--+--+--+" << endl;
	for (int y = 0; y < kBoardHeight; y++){
		for (int x = 0; x < kBoardWidth; x++){
			if(board[y][x] == kSpaceNum){
				printf("|  ");
			}
			else{
				printf("|%2d", board[y][x]);
			}
		}
		printf("|\n");
		cout << "+--+--+--+--+" << endl;
	}
}
int main() {
    /************** initialize ***************/
	CreatBoard();
	ShuffleBoard();

	while(true){
		system("cls");
		PrintNowBoard();
		JudgeClearGame();

		Puzzle move_pos = GetSpacePos();
		string command = "";
		cin >> command;
		switch(command[0]){
		case 's':
			move_pos.y_pos_++;
			break;
		case 'w':
			move_pos.y_pos_--;
			break;
		case 'd':
			move_pos.x_pos_++;
			break;
		case 'a':
			move_pos.x_pos_--;
			break;
		case 'p':
			cout << "GAME OVER !!!" << endl;
			return EXIT_SUCCESS;
		default :
			break;
		}
		MoveToSpace(move_pos);
	}
	return EXIT_FAILURE;
}

/**
 *
 * 現在の盤面からゴールになるまでの少ない計算量で算出出来る最短手数を盤面の状態ごとに計算します。
 * 例えば、各パネル同士のマンハッタン距離の合計はO(1)で計算出来るのでその値を使います。
 * それを、現在の盤面の経過手数に足した値が45手を超えていたらその盤面はもう見ません。
 * また、このようなマンハッタン距離の合計は、正当なA*探索アルゴリズムのヒューリスティックアルゴリズムを与えます。
 * 詳しくはhttps://ja.wikipedia.org/wiki/A*  を参照 
 * 
 * 
 *
 * 15パズル：
 * 空白を使ってパネルを上下左右にスライドさせ、絵柄を揃えるパズル
 *
 * 計算量：O(n!)
 *
 * 入力例：4×4のパネル（0が空白）
 *
    1 3 6 0
    5 2 7 4
    9 10 12 8
    13 14 11 15
 *
 *  出力例：この順番に揃えるまでの最短手数
    1   2   3   4
    5   6   7   8
    9   10  11  12
    13  14  15  0
 *
 *  11
 * 
 */

#include <cstdio>
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <cassert>
#include <algorithm>
using namespace std;


static const int kBoardWidth = 4;
static const int kBoardHeight = 4;
static const int kDirectionNum = 4;
static const int kPanelNum = 16;
static const int kAlreadyPassing = 2;
static const int kMaxMovementNum = 100;

enum PuzzleDirection{
	RIGHT = 0,
	UP,
	LEFT,
	DOWN,
};

// 進行方向（right,up,left,down）の略称
static const char kDirection[kDirectionNum] = { 'r', 'u', 'l', 'd' };
//進行方向に対するx座標値(y_pos)の増減
static const int dx[kBoardWidth] = { 0, -1, 0, 1 };
//進行方向に対するy座標値(x_pos)の増減
static const int dy[kBoardHeight] = { 1, 0, -1, 0 };
//ManhattanDistanceTable
static int MDT[kPanelNum][kPanelNum];

struct Puzzle {
	int board_situation[kPanelNum];
	int idx_space_pos;
	int sum_MD;
};

int GetSumMD(Puzzle pz) {
	int cnt = 0;
	for (int i = 0; i < kPanelNum; i++) {
		if (pz.board_situation[i] == kPanelNum) {
			continue;
		}
		cnt += MDT[i][pz.board_situation[i] - 1];
	}
	return cnt;
}
//デバッグ用
void PrintNowBoard(const Puzzle& now_puzzle){
  cout << "+--+--+--+--+" << endl;
  for (int i = 0; i < kPanelNum; i++) {
    if (now_puzzle.board_situation[i] == kPanelNum) {
      printf("|  ");
    } 
    else {
      printf("|%2d", now_puzzle.board_situation[i]);
    }
    if ((i != 0) && (i % kBoardWidth == 3)){
      cout << "|" << endl;
      cout << "+--+--+--+--+" << endl;
    } 
	}
}

void UpdateBoardInfo(Puzzle* board_current_state, const int y_pos, const int x_pos, const int y_pos_moved, const int x_pos_moved){
  	int idx_space_pos_destination = y_pos_moved * kBoardWidth + x_pos_moved;
		int idx_space_pos_current = y_pos * kBoardWidth + x_pos;

		board_current_state->sum_MD -= MDT[idx_space_pos_destination][board_current_state->board_situation[idx_space_pos_destination] - 1];
		board_current_state->sum_MD += MDT[idx_space_pos_current][board_current_state->board_situation[idx_space_pos_destination] - 1];
		swap(board_current_state->board_situation[idx_space_pos_destination], board_current_state->board_situation[idx_space_pos_current]);
		board_current_state->idx_space_pos = idx_space_pos_destination;
}

/**
 * dfs関数：深さ優先探索
 */
bool DFS(int current_depth, int prev_direction, Puzzle board_current_state, int depth_limit, vector<int>* route) {
  //デバッグ用
  // static int cnt = 0;
  // cout << cnt++ << "回目" << endl;
  // PrintNowBoard(board_current_state);
  // cout << "SumMD : " << board_current_state.sum_MD << endl << endl;
	
  if (board_current_state.sum_MD == 0)
		return true;
	//現在の深さ＋下限値(LowerBound)＞今回の深さ制限
	//これ以上先に進んでも無駄
	if (current_depth + board_current_state.sum_MD > depth_limit)
		return false;

	//左上を原点(0,0)としたときの現在の「0」の位置（(y_pos,x_pos)座標）
	int y_pos = board_current_state.idx_space_pos / kBoardHeight;
	int x_pos = board_current_state.idx_space_pos % kBoardWidth;

	//右、上、左、下の順にループ
	for (int direction = RIGHT; direction < kDirectionNum; direction++) {
		int y_pos_moved = y_pos + dx[direction];
		int x_pos_moved = x_pos + dy[direction];
    //boardの範囲の場合continue
		if( !(0<=y_pos_moved && y_pos_moved<kBoardHeight) || !(0<=x_pos_moved && x_pos_moved<kBoardWidth) ){
			continue;
		}
    //以前通った方角の場合continue
		if (max(prev_direction, direction) - min(prev_direction, direction) == kAlreadyPassing) {
			continue;
		}
		Puzzle tmp_board_state = board_current_state;
    
    UpdateBoardInfo(&board_current_state, y_pos, x_pos, y_pos_moved, x_pos_moved);

		//MDの合計値が0（各パネルが正しい位置に整列済み）のときに真
		if (DFS(current_depth + 1, direction, board_current_state, depth_limit, route)) {
			(*route)[current_depth] = direction;
			return true;
		}
		board_current_state = tmp_board_state;
	}
	return false;
}

string ParseShortestPath(Puzzle input_puzzle) {
	Puzzle board_current_state;
	int limit;
	vector<int> route(kMaxMovementNum,0);
	//各値の最短手数の合計値
	input_puzzle.sum_MD = GetSumMD(input_puzzle);
//	cout << input_puzzle.sum_MD << endl;
	for (limit = input_puzzle.sum_MD; limit <= kMaxMovementNum; limit++) {
		board_current_state = input_puzzle;
		if (DFS(0, -100, board_current_state, limit, &route)) {
			string direction_movement = "";
			for (int i = 0; i < limit; i++)
				direction_movement += kDirection[route[i]];
			return direction_movement;
		}
	}
	return "unsolvabe";
}
int main() {
    /************** initialize ***************/
	for (int i = 0; i < kPanelNum; i++){
		for (int j = 0; j < kPanelNum; j++){
			MDT[i][j] = abs(i / kBoardHeight - j / kBoardHeight) + abs(i % kBoardWidth - j % kBoardWidth);
		}
	}
	// for (int i = 0; i < kPanelNum; i++){
	// 	for (int j = 0; j < kPanelNum; j++){
  //     cout << MDT[i][j] << " ";
  //   }
  //   cout << endl;
  // }

	Puzzle input_puzzle;
	for (int i = 0; i < kPanelNum; i++) {
		cin >> input_puzzle.board_situation[i];
		if (input_puzzle.board_situation[i] == 0) {
			input_puzzle.board_situation[i] = kPanelNum;
			input_puzzle.idx_space_pos = i;
		}
	}
	string direction_movement = ParseShortestPath(input_puzzle);
//	cout << ans << endl;
	cout << direction_movement.size() << endl;
	return 0;
}

Compiler output:
a.cc:176:18: error: redefinition of 'const int kBoardWidth'
  176 | static const int kBoardWidth = 4;
      |                  ^~~~~~~~~~~
a.cc:8:18: note: 'const int kBoardWidth' previously defined here
    8 | static const int kBoardWidth = 4;
      |                  ^~~~~~~~~~~
a.cc:177:18: error: redefinition of 'const int kBoardHeight'
  177 | static const int kBoardHeight = 4;
      |                  ^~~~~~~~~~~~
a.cc:9:18: note: 'const int kBoardHeight' previously defined here
    9 | static const int kBoardHeight = 4;
      |                  ^~~~~~~~~~~~
a.cc:199:8: error: redefinition of 'struct Puzzle'
  199 | struct Puzzle {
      |        ^~~~~~
a.cc:12:8: note: previous definition of 'struct Puzzle'
   12 | struct Puzzle {
      |        ^~~~~~
a.cc: In function 'int GetSumMD(Puzzle)':
a.cc:208:24: error: 'struct Puzzle' has no member named 'board_situation'
  208 |                 if (pz.board_situation[i] == kPanelNum) {
      |                        ^~~~~~~~~~~~~~~
a.cc:211:34: error: 'struct Puzzle' has no member named 'board_situation'
  211 |                 cnt += MDT[i][pz.board_situation[i] - 1];
      |                                  ^~~~~~~~~~~~~~~
a.cc: In function 'void PrintNowBoard(const Puzzle&)':
a.cc:219:20: error: 'const struct Puzzle' has no member named 'board_situation'
  219 |     if (now_puzzle.board_situation[i] == kPanelNum) {
      |                    ^~~~~~~~~~~~~~~
a.cc:223:33: error: 'const struct Puzzle' has no member named 'board_situation'
  223 |       printf("|%2d", now_puzzle.board_situation[i]);
      |                                 ^~~~~~~~~~~~~~~
a.cc: In function 'void UpdateBoardInfo(Puzzle*, int, int, int, int)':
a.cc:236:38: error: 'struct Puzzle' has no member named 'sum_MD'
  236 |                 board_current_state->sum_MD -= MDT[idx_space_pos_destination][board_current_state->board_situation[idx_space_pos_destination] - 1];
      |                                      ^~~~~~
a.cc:236:100: error: 'struct Puzzle' has no member named 'board_situation'
  236 |                 board_current_state->sum_MD -= MDT[idx_space_pos_destination][board_current_state->board_situation[idx_space_pos_destination] - 1];
      |                                                                                                    ^~~~~~~~~~~~~~~
a.cc:237:38: error: 'struct Puzzle' has no member named 'sum_MD'
  237 |                 board_current_state->sum_MD += MDT[idx_space_pos_current][board_current_state->board_situation[idx_space_pos_destination] - 1];
      |                                      ^~~~~~
a.cc:237:96: error: 'struct Puzzle' has no member named 'board_situation'
  237 |                 board_current_state->sum_MD += MDT[idx_space_pos_current][board_current_state->board_situation[idx_space_pos_destination] - 1];
      |                                                                                                ^~~~~~~~~~~~~~~
a.cc:238:43: error: 'struct Puzzle' has no member named 'board_situation'
  238 |                 swap(board_current_state->board_situation[idx_space_pos_destination], board_current_state->board_situation[idx_space_pos_current]);
      |                                           ^~~~~~~~~~~~~~~
a.cc:238:108: error: 'struct Puzzle' has no member named 'board_situation'
  238 |                 swap(board_current_state->board_situation[idx_space_pos_destination], board_current_state->board_situation[idx_space_pos_current]);
      |                                                                                                            ^~~~~~~~~~~~~~~
a.cc:239:38: error: 'struct Puzzle' has no member named 'idx_space_pos'
  239 |                 board_current_state->idx_space_pos = idx_space_pos_destination;
      |                                      ^~~~~~~~~~~~~
a.cc: In function 'bool DFS(int, int, Puzzle, int, std::vector<int>*)':
a.cc:252:27: error: 'struct Puzzle' has no member named 'sum_MD'
  252 |   if (board_current_state.sum_MD == 0)
      |                           ^~~~~~
a.cc:256:49: error: 'struct Puzzle' has no member named 'sum_MD'
  256 |         if (current_depth + board_current_state.sum_MD > depth_limit)
      |                                                 ^~~~~~
a.cc:260:41: error: 'struct Puzzle' has no member named 'idx_space_pos'
  260 |         int y_pos = board_current_state.idx_space_pos / kBoardHeight;
      |                                         ^~~~~~~~~~~~~
a.cc:261:41: error: 'struct Puzzle' has no member named 'idx_space_pos'
  261 |         int x_pos = board_current_state.idx_space_pos % kBoardWidth;
      |                                         ^~~~~~~~~~~~~
a.cc: In function 'std::string ParseShortestPath(Puzzle)':
a.cc:294:22: error: 'struct Puzzle' has no member named 'sum_MD'
  294 |         input_puzzle.sum_MD = GetSumMD(input_puzzle);
      |                      ^~~~~~
a.cc:296:35: error: 'struct Puzzle' has no member named 'sum_MD'
  296 |         for (limit = input_puzzle.sum_MD; limit <= kMaxMovementNum; limit++) {
      |                                   ^~~~~~
a.cc: At global scope:
a.cc:307:5: error: redefinition of 'int main()'
  307 | int main() {
      |     ^~~~
a.cc:97:5: note: 'int main()' previously defined here
   97 | int main() {
      |     ^~~~
a.cc: In function 'int main()':
a.cc:323:37: error: 'struct Puzzle' has no member named 'board_situation'
  323 |                 cin >> input_puzzle.board_situation[i];
      |                                     ^~~~~~~~~~~~~~~
a.cc:324:34: error: 'struct Puzzle' has no member named 'board_situation'
  324 |                 if (input_puzzle.board_situation[i] == 0) {
      |                                  ^~~~~~~~~~~~~~~
a.cc:325:38: error: 'struct Puzzle' has no member named 'board_situation'
  325 |                         input_puzzle.board_situation[i] = kPanelNum;
      |                                      ^~~~~~~~~~~~~~~
a.cc:326:38: error: 'struct Puzzle' has no member named 'idx_space_pos'
  326 |                         input_puzzle.idx_space_pos = i;
      |                                      ^~~~~~~~~~~~~