Write program in C++.  Write a breadth-first search program to solve 15-puzzle problems in the same way as the 8-puzzle. Keep track of the number of nodes expanded and print that out along with the steps to solve the problem. Define the legal moves as "swap the blank with an adjacent tile," resulting in the blank's moving up, down, left, or right. A sample run should look like this:  Enter 15-puzzle starting state by rows (0 for blank):  1,2,3,4,5,6,7,8,9,10,0,11,13,14,15,12  Enter ending state by rows (0 for blank):  1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0 Solution: Start 1 2 3 4 5 6 7 8 9 10 0 11 13 14 15 12 Swap the blank Right 1 2 3 4 5 6 7 8 9 10 11 0 13 14 15 12 Down 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 

I have this program, However it needs to follow the insructions listed above, but this one does not do it in Breadth First Search, can someone modify it, where it applies all the instruction above in to the code, thanks:

[Code}

#include

using namespace std;

//4x4 Matrix for the number input.

const int xRow = 4;

const int yCol = 4;

int puzzle[xRow][yCol];

int x, y;

void rightSwap() {

if (y != 3) {

int temp;

temp = puzzle[x][y + 1];

puzzle[x][y + 1] = puzzle[x][y];

puzzle[x][y] = temp;

}

y += 1;

cout << "After Right Move " << endl;

for (int i = 0; i < 4; i++) {

for (int j = 0; j < 4; j++)

cout << puzzle[i][j] << " ";

cout << endl;

}

}

void leftSwap() {

if (y != 0) {

int temp;

temp = puzzle[x][y - 1];

puzzle[x][y - 1] = puzzle[x][y];

puzzle[x][y] = temp;

}

y -= 1;

cout << "After Left Move: " << endl;

for (int i = 0; i < 4; i++) {

for (int j = 0; j < 4; j++)

cout << puzzle[i][j] << " ";

cout << endl;

}

}

void upSwap() {

if (x != 0) {

int temp;

temp = puzzle[x - 1][y];

puzzle[x - 1][y] = puzzle[x][y];

puzzle[x][y] = temp;

}

x -= 1;

cout << "After Up Move: " << endl;

for (int i = 0; i < 4; i++) {

for (int j = 0; j < 4; j++)

cout << puzzle[i][j] << " ";

cout << endl;

}

}

void downSwap() {

if (x != 3) {

int temp;

temp = puzzle[x + 1][y];

puzzle[x + 1][y] = puzzle[x][y];

puzzle[x][y] = temp;

}

x += 1;

cout << "After Down Move: " << endl;

for (int i = 0; i < 4; i++)

{

for (int j = 0; j < 4; j++)

cout << puzzle[i][j] << " ";

cout << endl;

}

}

int main() {

cout << "Enter 15-puzzle starting state by rows (0 for blank):" << endl;

for (int i = 0; i < xRow; i++)

{

for (int j = 0; j < yCol; j++)

{

cin >> puzzle[i][j];

cin.ignore();

if (puzzle[i][j] == 0) {

x = i;

y = j;

}

}

}

cout << "Starting: " << endl;

for (int i = 0; i < xRow; i++) {

for (int j = 0; j < yCol; j++)

cout << puzzle[i][j] << " ";

cout << endl;

}

//upSwap();

//leftSwap();

rightSwap();

downSwap();

cout << "Done! Generated xx States" << endl;

}

[/Code]