1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const char* race[] = {"norge", "english", "dutch", "german", "swiss"};
  8. const char* color[] = {"white", "yellow", "green", "red", "blue"};
  9. const char* drink[] = {"water", "coffee", "milk", "beer", "tea"};
  10. const char* pet[] = {"cat", "horse", "bird", "fish", "dog"};
  11. const char* smoke[] = {"dunhil", "marlboro", "pallmall", "morris", "rothmans"};
  12.  
  13. bool check (vector<vector<int>>& solve, int fill) {
  14. 	for (int i = 0; i < 5; ++i) {
  15. 		switch (fill) {
  16. 			case 4:
  17. 				/*  5 */ if (solve[4][i] == 4) if ((i > 0 && solve[3][i-1] == 0) || (i < 4 && solve[3][i+1] == 0)) /* empty */; else return false;
  18. 				/*  6 */ if (solve[1][i] == 1 && solve[4][i] != 0) return false;
  19. 				/*  7 */ if (solve[0][i] == 3 && solve[4][i] != 1) return false;
  20. 				/*  9 */ if (solve[2][i] == 0) if ((i > 0 && solve[4][i-1] == 4) || (i < 4 && solve[4][i+1] == 4)) /* empty */; else return false;
  21. 				/* 10 */ if (solve[4][i] == 2 && solve[3][i] != 2) return false;
  22. 				/* 14 */ if (solve[4][i] == 3 && solve[2][i] != 3) return false;
  23. 				break;
  24. 			case 3:
  25. 				/* 13 */ if (solve[3][i] == 1 && solve[1][i] != 4) return false;
  26. 				/* 11 */ if (solve[0][i] == 4 && solve[3][i] != 4) return false;
  27. 				break;
  28. 			case 2:
  29. 				/*  4 */ if (solve[0][i] == 2 && solve[2][i] != 4) return false;
  30. 				/*  8 */ if (i == 2 && solve[2][i] != 2) return false;
  31. 				/* 15 */ if (solve[1][i] == 2 && solve[2][i] != 1) return false;
  32. 				break;
  33. 			case 1:
  34. 				/*  2 */ if (solve[0][i] == 1 && solve[1][i] != 3) return false;
  35. 				/* 3a */ if (solve[1][i] == 2 && i < 4 && solve[1][i+1] != 0) return false;
  36. 				/* 3b */ if (solve[1][i] == 2 && i == 4) return false;
  37. 				/* 12 */ if (solve[0][i] == 0) if ((i > 0 && solve[1][i-1] == 4) || (i < 4 && solve[1][i+1] == 4)) /* empty */; else return false;
  38. 				break;
  39. 			case 0:
  40. 				/*  1 */ if (solve[0][i] == 0 && i != 0) return false;
  41. 		}
  42. 	}
  43. 	return true;
  44. }
  45.  
  46. void recurse(vector<int>& tmp, vector<vector<int>>& solve, int it) {
  47. 	if (it == 5) {
  48. 		for (int i = 0; i < 5; ++i) {
  49. 			cout << i + 1 << " " << race[solve[0][i]] << " " << color[solve[1][i]] << " ";
  50. 			cout << drink[solve[2][i]] << " " << pet[solve[3][i]] << " " << smoke[solve[4][i]] << " " << endl;
  51. 		} cout << endl;
  52. 	} else {
  53. 		solve[it] = tmp;
  54. 		do {
  55. 			if (!check(solve, it)) continue;
  56. 			recurse(tmp, solve, it + 1);
  57. 		} while(next_permutation(solve[it].begin(), solve[it].end()));
  58. 	}
  59. }
  60.  
  61. int main () {
  62. 	vector<vector<int>> solve(6);
  63. 	vector<int> tmp(5);
  64. 	for (int i = 0; i < 5; ++i) tmp[i] = i;
  65. 	recurse(tmp, solve, 0);
  66. 	system("pause");
  67. }