View Code of Problem 29

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<string>
#include<cmath>

using namespace std;

vector<string> goods = { "ABDE", "ABC", "BCEF", "ADG", "BDEFH", "CFI", "DEGH", "GHI", "EFHI" };
vector<int> ans;

bool dfs(vector<int>& require, vector<int>& temp, vector<int>& res) {

	for (int i = 0; i < temp.size(); i++) {

		if (temp[i] > 4)
			return false;
	}

	int flag = 0;
	for (int i = 0; i < temp.size(); i++) {

		if ((temp[i] + require[i]) % 4 != 0) {

			flag = 1;
			break;
		}
	}

	if (flag == 0) {

		for (int i = 0; i < res.size(); i++)
			ans.push_back(res[i]);

		return true;
	}
		


	for (int i = 0; i < 9; i++) {

		for (int j = 0; j < goods[i].size(); j++) {

			temp[goods[i][j] - 'A']++;
		}

		res.push_back(i + 1);

		if(dfs(require, temp, res))
			return true;

		for (int j = 0; j < goods[i].size(); j++) {

			temp[goods[i][j] - 'A']--;
		}

		res.pop_back();
	}
	
	return false;
}

int main()
{
	vector<int> require(9);
	for (int i = 0; i < 9; i++)
		cin >> require[i];
		
	vector<int> temp(9);
	vector<int> res;

	dfs(require, temp, res);

	for (int i = 0; i < ans.size(); i++) {

		cout << ans[i] << " ";
	}
}