The problem is " The shape of a puzzle board and positions of each puzzle are given for the input. Decide whether the puzzle is solved able or not using C++ programming language ".
" 15 Puzzle " others names are: " Gem Puzzle, 16 Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square ". The introduction of " 15 Puzzle " can be described as " one empty tile slot in a sliding puzzle with 15 square tiles numbered 1–15 in a frame (that is 4 tiles high and 4 tiles wide. 4 by 4 square shape board ) ".
15 puzzle problem solutions in C++
#include<iostream>
#define s 100
using namespace std;
int main()
{
int n, i, j, mat[s][s], arr[s], inv=0, num=0, input, row;
cin>>n;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
cin>>input;
arr[num++]=input;
if(arr[num-1]==0)
row=n-i+1;
}
}
cout<<endl<<num<<endl;
for(i=0; i<num; i++)
{
for(j=i+1; j<num; j++)
{
if( arr[i]>arr[j] && arr[i]!=0 && arr[j]!=0)
{
inv++;
}
}
}
cout<<"NO of Inversion : "<<inv<<endl;
if((n%2==1 && inv%2==0) || (n%2==0 && inv%2==1 && row%2==0)|| (n%2==0 && inv%2==0 && row%2==1))
cout<<"Solve able\n";
else
cout<<"Not Possible\n";
}
How does it work?
Step 1: Take variables for the solution. All variables of this problem are integers. The variable descriptions are,
n = The input variable for the shape of the puzzle's board
i, j = Tor the running of loops
mat[s][s] = The matrices which represent the puzzle board. The board will be generated according to the shape of the 's' variable. Here, the 's' (size) integer variable is predefined by default as 100.
arr[s] = The 2D array matrix 'mat[s][s]' variable will be converted into a 1D array for the easy computation. Here, the 'arr[s]' will store the values.
inv = This variable is initially set as '0'. It will count the number of puzzle exchange positions for every computation.
input = The input numbers of the 2D matrix. This variable will temporarily store the puzzle positions.
num = This variable is also initially set as '0'. It will count the input numbers in the array 'arr[s]'
row = This variable represents the row numbers in the 2D matrix 'mat[s][s]'. We can also build the row in a 1D array.
NoteBook: The 'mat[s][s]' variable will not be used right now. So, 2D to 1D conversion is skipped in this post. We introduce the variable for proper understanding.
Step 2: Take the inputs for the board shape and the position of each puzzle. We will take it by the 'cin' input function.
cin>>n;
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
cin>>input;
arr[num++]=input;
if(arr[num-1]==0)
row=n-i+1;
}
}
The condition 'arr[num-1]==0' is used to find the empty position. The '0' represents the empty position of the puzzle board.
Step 3: Now find the inversion number to solve the puzzle. We will do this by checking some conditions between the position's input numbers. The simple branch and bounding process is done here.
for(i=0; i<num; i++)
{
for(j=i+1; j<num; j++)
{
if( arr[i]>arr[j] && arr[i]!=0 && arr[j]!=0)
{
inv++;
}
}
}
Step 4: Check the number of inversions and print whether the puzzle is solvable or not. The conditions are given below with proper code,
if((n%2==1 && inv%2==0) || (n%2==0 && inv%2==1 && row%2==0)|| (n%2==0 && inv%2==0 && row%2==1))
cout<<"Solve able\n";
else
cout<<"Not Possible\n";
15 puzzle problem solutions in Python
n=int(input())
inv=0
num=0
row=0
arr=list(map(int, input().split()))
for i in range(n):
if arr[i-1]==0:
row=n-i+1
for i in range(0, len(arr), 1):
for j in range(i+1, len(arr), 1):
if (arr[i]>arr[j] and arr[i]!=0 and arr[j]!=0):
inv+=1
print("Shape of the puzzle: ", n*n, "(", n, "*", n, ")")
print("No. of Inversion: ",inv)
if((n%2==1 and inv%2==0) or (n%2==0 and inv%2==1 and row%2==0) or (n%2==0 and inv%2==0 and row%2==1)):
print("Solve able")
else:
print("Not Possible")
Sample Input:
4
2 3 4 6 7 8 5 9 10 0 1 15 14 12 13 11
Sample Output:
Shape of the puzzle: 16 ( 4 * 4 )
No. of Inversion: 21
Solve ableComparison of the conversion between C++ and Python input method
In C++:
The input of puzzle board size and puzzles position in the board
cin>>n; //puzzle board size
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
cin>>input;
arr[num++]=input; //puzzles position
}
}
In Python:
The input of puzzle board size and puzzle position in the board
n=int(input()) #puzzle board sizearr=list(map(int, input().split())) #puzzles position
0 মন্তব্যসমূহ