C++ based on the artificial intelligence search strategy to solve the farmer crossing the river problem example

In this paper, an example is given to solve the problem of farmers crossing the river based on C++ search strategy based on artificial intelligence. I will share it with you for your reference as follows:

Problem description

A farmer with a Wolf, a sheep and a cabbage across the river, the boat can only once load the farmer and a kind of goods, Wolf can eat sheep, sheep can eat cabbage, only when the farmer is safe. Now we want to make everything safe across the river, including the farmer, for the best answer.

The state space

The 16*4 matrix: a[16][4] is used to store the state of each step. The first column represents the state of the farmer, the second column represents the state of the dish, the third column represents the state of the sheep, the fourth column represents the state of the fox, and the elements in the array a are only 0 or 1, 0 represents the left bank, and 1 represents the right bank.

The initial state is a[0][0]=a[0][1]=a[0][2]=a[0][3]=0, and the target state is that all rows of the matrix are 1.

Operating rules

1. The farmer does a round trip, i, a[i][0] = i%2.
2. Every time the farmer crosses the river, he can choose to bring one piece of goods or not.
3. In the absence of the farmer, the Wolf and the sheep could not be at the same time, and the sheep and the cabbage could not be at the same time.

Search strategy

To avoid repetition, we put the searched state into set, and then avoid searching for that state.

We use depth-first search. The search process was as follows: the farmer did a round-trip exercise. When the farmer went from the left bank to the right bank, he preferred to take the goods across the river; when the farmer went from the right bank to the left bank, he preferred to take no goods across the river. After making the choice, take a step forward to see if the target state has been reached. If not, the farmer goes back and forth until the target state is found, or until a solution is found.

C++ code implementation

#include <iostream>
#include <cstring>
#include <string>
#include <set>
using namespace std;
void search(int i);
int a[16][4];
set<int> s;
int b[16];
string ss[2];
string t[4];
int k;
int level;
int count1(int a[])// Converts the current state to 10 Hexadecimal number  
{
  return a[0]*8+a[1]*4+a[2]*2+a[3];
}
void show(int a[])// Display result function  
{
  cout<<"       Left: ";
  for(int i=1;i<=3;i++)
    if(a[i]==0)
      cout<<t[i]<<" ";
  cout<<"  ";
  cout<<" On the right: ";
  for(int i=1;i<=3;i++)
    if(a[i]==1)
      cout<<t[i]<<" ";
  cout<<endl<<endl; 
}
void bringSomething(int i)// Let's say the farmer takes something  
{
  for(int j=1;j<=3;j++)
  {
    if(a[i][j]==a[i][0])// if j It was the same as the farmer 1 The position, the farmer may be j Take away.  
    {
      a[i+1][j]=a[i+1][0];// Assuming that the j Take away  
      if((!(a[i+1][1]==a[i+1][2]&&a[i+1][1]!=a[i+1][0]||a[i+1][3]==a[i+1][2]&&a[i+1][2]!=a[i+1][0]))&&s.count(count1(a[i+1]))==0&&i>=level)// The first i+1 Layer will j When the condition is satisfied, the search continues i+1 layer  
      {
        s.insert(count1(a[i+1]));
        b[i]=1;
        cout<<ss[a[i][0]]<<t[j]<<"  ";
        show(a[i+1]);
        level++;       
        search(i+1);
      }
      else // If the conditions are not met, resume  
      {
        a[i+1][j]=a[i][j];
      }      
    }
  }
}
void bringNothing(int i)// Suppose the farmer takes nothing  
{
  if((!(a[i+1][1]==a[i+1][2]&&a[i+1][1]!=a[i+1][0]||a[i+1][3]==a[i+1][2]&&a[i+1][2]!=a[i+1][0]))&&s.count(count1(a[i+1]))==0&&i>=level)
  {  
    if(i==0)
      cout<<" The farmer went from left to right with nothing ";
    else 
      cout<<" The farmer went from right to left, carrying nothing ";
    show(a[i+1]);
    s.insert(count1(a[i+1]));
    search(i+1);
    level++;
  }
  else 
    b[i]=0;
}
void search(int i)// From the first i The layer begins searching to judge the first i+1 Layer possibilities  
{ 
  if(i>=16||count1(a[i])==15)
    return;
  for(int j=1;j<=3;j++)// In the first i Layer to initialize the first i+1 layer  
  {
    a[i+1][j]=a[i][j];
  }
  b[i]=-1;
  if(i%2==1)// On the right bank, first consider the farmer taking nothing  
  {
    bringNothing(i);
    if(b[i]==0)
      bringSomething(i);
  }
  else{// On the left bank, let's first think about the farmer taking something with him 1 Things.  
    bringSomething(i);
    if(b[i]!=1)
      bringNothing(i);
  }
}
int main()
{  
  ss[0]=" Farmer from left to right, take it ";
  ss[1]=" The farmer went back from the right to the left and took it with him ";
  t[1]=" food ";
  t[2]=" The sheep ";
  t[3]=" The fox ";
  memset(a,0,sizeof(a));
  for(int i=0;i<16;i++)
  {
    a[i][0]=i%2;
  }
  s.clear();
  k=0;
  level=0;
  s.insert(0);  // So let's store the initial state  
  search(0); // From the first 0 Layer search  
  for(int i=0;i<16;i++)
  {
    for(int j=0;j<4;j++)
      cout<<a[i][j]<<" ";
    cout<<endl;
    if(count1(a[i])==15)
      break;
  }
  return 0;
}

The results of

 The farmer went from right to left, carrying nothing   Left: food   The fox   Right: the sheep 

 The farmer went from the left to the right and brought the food   Left: fox   Right: food   The sheep 

 The farmer went back from the right to the left and took the sheep with him   Left: the sheep   The fox   Right: food 

 The farmer went from left to right and took the fox with him   Left: the sheep   Right: food   The fox 

 The farmer went from right to left, carrying nothing   Left: the sheep   Right: food   The fox 

 The farmer went from the left to the right and took the sheep   Left:   Right: food   The sheep   The fox 

0 0 0 0 
1 0 1 0 
0 0 1 0 
1 1 1 0 
0 1 0 0 
1 1 0 1 
0 1 0 1 
1 1 1 1

I hope this article is helpful to you C++ programming.