狼、羊、菜問題 C++ 解題

古老的智力遊戲題其實最適合用 functional language 或 logic language 或 AI language (Prolog)去解，但這解題的程式碼是我多年前寫下的，懶得修改，只貼出來留念，有興趣的人可以用更適合 language去解題，程式應該是少很多，而且解題思路會更清晰。

問題:

一個農夫帶著一只狼，一只羊和一籃菜回家，途中要過一條河，唯一的渡河工具是一條小船，因為船真的是太小了，農夫最多只能帶三樣東西的其中一件划船過河；可是，要是農夫不在旁的話，狼會咬羊，羊會吃菜，農夫應怎樣過河才可使得羊和菜都無損呢？



 

#include <iostream>
#include <vector>
using namespace std;

const int TARGET_STATE = 15;  // 1111b

vector<int> crossSnapshot;
vector<int> takerSnapshot;

enum{
  FARMER=8, // 1000 b
  WOLF=4, // 0100 b
  GOAT = 2, // 0010 b
  CABBAGE=1 // 0001 b
};


//toggle the bit N array
//at bankA = 0, at bankB = 1

int cross[] = {
 FARMER, //FARMER  //1000b, 8, Farmer at bankB
 FARMER | WOLF, //FARMER, WOLF //1100b, 12
 FARMER | GOAT, //FARMER, GOAT //1010b, 10
 FARMER | CABBAGE //FARMER,CABBAGE //1001b, 9
};

void printState(int iState){
 //print out Bit N, N start from 0

 int N=4;
 for(int i=N-1;i>=0;i--)
 {
  cout << ((iState >> i ) & 1);//show Bit 3
 }
 cout << endl;
}


int farmer(int iState){
 //get a Bit N of iState, N start from 0
 return ((iState >> 3 ) & 1);
}
int wolf(int iState){
 return ((iState >> 2 ) & 1);
}
int goat(int iState){
 return ((iState >> 1 ) & 1);
}
int cabbage(int iState){
 return ((iState >> 0 ) & 1);
}

bool isSafe(int state){
 if( goat(state) == wolf(state) &&
  goat(state) != farmer(state))
 {
  return false;
 }

 if( goat(state) == cabbage(state) &&
  goat(state)!=farmer(state))
 {
  return false;
 }

 return true;
}

bool isTry(int state){
 bool isTried = false;

 for(int j=0; j < crossSnapshot.size();j++){
  //printState(crossSnapshot[j]);

  if (state == crossSnapshot[j]){
   isTried = true;
   break;
  }
 }
 return isTried;
}


void printTaker2(int i){
 char* msg[] = {
  "farmer goes alone",
  "farmer takes wolf",
  "farmer takes goat",
  "farmer takes cabbage"
 };

 if(i >= 0 && i <= 3) {
  cout << msg[i] << endl;;
 }
}

void printEveryState(vector<int> &crossSnapshot){
 cout << "total number cross state = " << crossSnapshot.size()<<endl;

 for(int j=0; j < crossSnapshot.size();j++){
  printState(crossSnapshot[j]);
  //printTaker2(crossSnapshot[j]);
 }
}

void printEveryState2(vector<int> &takerSnapshot){
 cout << "The cross step is show as belowing." << endl;

 for(int j=0; j < takerSnapshot.size();j++){
  cout << j+1 << ". ";
  printTaker2(takerSnapshot[j]);
 }

 cout <<endl;
}

void recordTriedState(int state, int i, vector<int> &crossSnapshot){
 //save snapshot
 crossSnapshot.push_back(state);
 takerSnapshot.push_back(i);
}

void RollbackRecordState(int state, vector<int> &crossSnapshot){
 //delete previous snapshot
 crossSnapshot.pop_back();
 takerSnapshot.pop_back();
}

void crossRiver(int state, vector<int> &crossSnapshot){
 if (state == TARGET_STATE){
  //printEveryState(crossSnapshot);
  printEveryState2(takerSnapshot);
  //stop recurive iteration
  return;
 }

 //for every cross choice
 for(int i=0; i<4; i++){
  int nextCrossState = state ^ cross[i]; // use bitwise^ to toggle the Bit i

  if(isSafe(nextCrossState) && !isTry(nextCrossState)){
   recordTriedState(nextCrossState, i, crossSnapshot);

   //printTaker(i, state);
   //recurive to call itself
   crossRiver(nextCrossState, crossSnapshot);

   RollbackRecordState(nextCrossState, crossSnapshot);
  }
 }
}

int main() {
 int initialState = 0;

 //save first snapshot
 crossSnapshot.push_back(initialState);

 crossRiver(initialState, crossSnapshot);

    cout << "Press any key to be continue" << endl;
 getchar();
 return 0;
} 

Output:

The cross step is show as belowing.
1. farmer takes goat
2. farmer goes alone
3. farmer takes wolf
4. farmer takes goat
5. farmer takes cabbage
6. farmer goes alone
7. farmer takes goat

The cross step is show as belowing.
1. farmer takes goat
2. farmer goes alone
3. farmer takes cabbage
4. farmer takes goat
5. farmer takes wolf
6. farmer goes alone
7. farmer takes goat

Press any key to be continue

 
延伸閱讀：

狐狸、鵝、豆子問題 - 維基百科，自由的百科全書

http://en.wikipedia.org/wiki/Fox,_goose_and_bag_of_beans_puzzle

 數學遊戲與欣賞 - 過河問題

渡河問題 - 维基百科，自由的百科全书


過河問題的圖論解法 - 那個誰 - CSDNBlog