Write program in C++. Write a breadth-first search program to solve 15-puzzle pr
ID: 3871141 • Letter: W
Question
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 Done! Generated States.
Explanation / Answer
C++ Program
#include<iostream>
using namespace std;
int puzzle[4][4];
int right();
int left();
int top();
int down();
int x,y;
int main()
{
cout<<"Enter 15-puzzle starting state by rows (0 for blank):"<<endl;
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
cin>>puzzle[i][j];
if(puzzle[i][j]==0)
{
x=i;
y=j;
}
}
cout<<"Starting "<<endl;
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
cout<<puzzle[i][j]<<" ";
cout<<endl;
}
right();
down();
}
int right()
{
if(y!=3)
{
int temp;
temp=puzzle[x][y+1];
puzzle[x][y+1]=puzzle[x][y];
puzzle[x][y]=temp;
}
y=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;
}
return 0;
}
int left()
{
if(y!=0)
{
int temp;
temp=puzzle[x][y-1];
puzzle[x][y-1]=puzzle[x][y];
puzzle[x][y]=temp;
}
y=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;
}
return 0;
}
int top()
{
if(x!=0)
{
int temp;
temp=puzzle[x-1][y];
puzzle[x-1][y]=puzzle[x][y];
puzzle[x][y]=temp;
}
x=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;
}
return 0;
}
int down()
{
if(x!=3)
{
int temp;
temp=puzzle[x+1][y];
puzzle[x+1][y]=puzzle[x][y];
puzzle[x][y]=temp;
}
x=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;
}
return 0;
}
OUTPUT
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
Starting
1 2 3 4
5 6 7 8
9 10 0 11
13 14 15 12
After Right Move
1 2 3 4
5 6 7 8
9 10 11 0
13 14 15 12
After Down Move
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.