# Priests and devils puzzle problem in C++

In this tutorial, we will learn how to implement the priests and devils puzzle/game using C++.

## PROBLEM:

You are given that there are 3 priests and 3 devils who have to cross a river in a boat. How can we make 3 priests and 3 devils arrive on the other side of the river safely with neither of them killed?

Conditions are:

1. The boat can deliver at most 2 people at a time.
2. If the number of priests is less than the number of devils on the same side of the river, then the devils will kill the priests.

## SOLUTION:

To solve this, let us mark the priests as P1, P2 and P3 and the devils as D1, D2 and D3. Let us also consider that they need to cross the river from side A to side B. There are 6 steps that need to be followed to get all 6 people on the other side of the river:

Initially, the 3 priests and 3 devils are on side A.

1. At first, P1 and D1 will go to side B. D1 will stay on side B and P1 will come back on the boat to side A.
RESULT: D1 is on side B and D2, D3, P1, P2 and P3 is on side A.
2. Then, D2 and D3 will go to side B. D2 will stay and D3 will come back to side A.
RESULT: D1 and D2 are on side B and D3, P1, P2 and P3 are on side A.
3. P1 and P2 will go to side B. P1 will stay and P2 and D2 will go back to side A.
RESULT: D1 and P1 are on side B and D2, D3, P2 and P3 are on side A.
4. P2 and P3 will go to side B and D1 will come back to side A.
RESULT: P1, P2 and P3 are on side B and D1, D2 and D3 are on side A.
5. D1 and D2 will go to side B. D1 will stay and D2 will come back to side A.
RESULT: P1, P2, P3, and D1 are on side B and D2 and D3 are on side A.
6. At last, D2 and D3 will go to side B.
Thus, all the 3 devils and 3 priests arrive on side B.

Now let us implement the above puzzle/game using C++ code.

```#include<bits/stdc++.h>
using namespace std;
void travel(int total, int dinboat, int pinboat, int priestata, int devilata, int priestatb, int devilatb)
{
if(total>2)
{
cout<<"********>>>OOPS..!! The boat can carry at most 2 persons at a time<<<********* \n";
exit(1);
}

if(total==0 || (priestata<pinboat && devilata<dinboat) || (priestatb<pinboat && devilatb<dinboat))
{
cout<<"********>>>OOPS..!! This is not possible<<<********* \n";
exit(1);
}

if((priestata<devilata || priestatb<devilatb) && (priestata!=0 && priestatb!=0))
{
cout<<"OOPS..!! The no of priests can't be less than the number of devils on the same side of the river..!! \n";
cout<<"*********>>>GAME OVER<<<********** \n";
exit(1);
}
if(priestatb==3 && devilatb==3)
{
cout<<"*********>>>GAME OVER<<<********** \n";
cout<<"*********Congratulations!! All the 3 priests and 3 devils have arrived side B safely..!!********* \n";
exit(1);
}
}

void travel(int, int, int, int, int, int, int);
main()
{	cout<<"*************************************************************************************************** \n";
cout<<"WELCOME TO THE GAME..!! \n";
cout<<"YOU ARE GIVEN 3 PRIESTS AND 3 DEVILS. HELP THEM TO CROSS THE RIVER. \n";
cout<<">>>REMEMBER THE NO OF PRIESTS SHOULD'NT EXCEED THE NO OF DEVILS ON THE SAME SIDE OF THE RIVER..!!<<< \n";
cout<<">>>AND THE BOAT CAN CARRY AT MOST 2 PERONS AT A TIME<<< \n";
cout<<"*************************************************************************************************** \n\n\n";

int pinboat=0, dinboat=0, total=0;
int priestata=3, devilata=3, priestatb=0, devilatb=0;

while(priestatb<=3 && devilatb<=3)
{
if(devilata!=0)
{
cout<<"Enter the no of devil going from side A to side B : \n";
cin>>dinboat;
}
if(dinboat!=2 && priestata!=0)
{
cout<<"Enter the no of priest going from side A to side B : \n";
cin>>pinboat;
}
else
{
pinboat=0;
}
total=(dinboat + pinboat);
devilatb+=dinboat;
devilata-=dinboat;
priestatb+=pinboat;
priestata-=pinboat;

travel(total, dinboat, pinboat, priestata, devilata, priestatb, devilatb);

if(devilatb!=0)
{
cout<<"Enter the no of devil going from side B to side A : \n";
cin>>dinboat;
}
if(dinboat!=2 && priestatb!=0)
{
cout<<"Enter the no of priest going from side B to side A : \n";
cin>>pinboat;
}
else
{
pinboat=0;
}
total=(dinboat + pinboat);
devilata+=dinboat;
devilatb-=dinboat;
priestata+=pinboat;
priestatb-=pinboat;

travel(total, dinboat, pinboat, priestata, devilata, priestatb, devilatb);

cout<<"\n\nAT SIDE A"<<"\n"<<"No of devils = "<<devilata<<"\t"<<"No of priests = "<<priestata<<"\n";
cout<<"\n\nAT SIDE B"<<"\n"<<"No of devils = "<<devilatb<<"\t"<<"No of priests = "<<priestatb<<"\n\n";
}
}```

### OUTPUT:

```***************************************************************************************************
WELCOME TO THE GAME..!!
YOU ARE GIVEN 3 PRIESTS AND 3 DEVILS. HELP THEM TO CROSS THE RIVER.
>>>REMEMBER THE NO OF PRIESTS SHOULD'NT EXCEED THE NO OF DEVILS ON THE SAME SIDE OF THE RIVER..!!<<<
>>>AND THE BOAT CAN CARRY AT MOST 2 PERONS AT A TIME<<<
***************************************************************************************************

Enter the no of devil going from side A to side B :
1
Enter the no of priest going from side A to side B :
1
Enter the no of devil going from side B to side A :
0
Enter the no of priest going from side B to side A :
1

AT SIDE A
No of devils = 2 No of priests = 3
AT SIDE B
No of devils = 1 No of priests = 0

Enter the no of devil going from side A to side B :
2
Enter the no of devil going from side B to side A :
1

AT SIDE A
No of devils = 1 No of priests = 3
AT SIDE B
No of devils = 2 No of priests = 0

Enter the no of devil going from side A to side B :
0
Enter the no of priest going from side A to side B :
2
Enter the no of devil going from side B to side A :
1
Enter the no of priest going from side B to side A :
1

AT SIDE A
No of devils = 2 No of priests = 2
AT SIDE B
No of devils = 1 No of priests = 1

Enter the no of devil going from side A to side B :
0
Enter the no of priest going from side A to side B :
2
Enter the no of devil going from side B to side A :
1
Enter the no of priest going from side B to side A :
0

AT SIDE A
No of devils = 3 No of priests = 0
AT SIDE B
No of devils = 0 No of priests = 3

Enter the no of devil going from side A to side B :
2
Enter the no of devil going from side B to side A :
1
Enter the no of priest going from side B to side A :
0

AT SIDE A
No of devils = 2 No of priests = 0
AT SIDE B
No of devils = 1 No of priests = 3

Enter the no of devil going from side A to side B :
2
*********>>>GAME OVER<<<**********
*********Congratulations!! All the 3 priests and 3 devils have arrived side B safely..!!*********```

There are multiple ways one can implement the priests and devils puzzle problem in C++. Now try it yourself.