题解 | 等式填充问题

#include <stdio.h>
#include <vector>
#include <unordered_set>

using namespace std;

vector<vector<int>> result;
bool used[10];

int max_commom_divisor(int a, int b) {
	if (a < b) { //确保a>b
		int tem = a;
		a = b;
		b = tem;
	}
	int remain = a % b;
	int divisor = b;
	while (remain != 0) {
		a = b;
		b = remain;
		remain = a % b;
		divisor = b;
	}
	return divisor;
}

bool formula_verification(vector<int>f) {
	if (f.size() != 9) {
		return false;
	}
	float a = (float)(f[0] * 10 + f[1]) / f[2];
	float b = (float)(f[3] * 10 + f[4]) / f[5];
	float c = (float)(f[6] * 10 + f[7]) / f[8];
	if (a + b == c) {
		return true;
	}
	return false;
}
vector<vector<int>> build_fraction() {
	vector<int> f;
	vector<int> numbers;
	vector<vector<int>>fractions;
	numbers.clear();
	fractions.clear();
	for (int i = 1; i <= 9; i++) {
		if (!used[i]) {
			numbers.push_back(i);
		}
	}
	for (int i = 0; i < numbers.size(); i++) {
		f.clear();
		f.push_back(numbers[i]);
		used[numbers[i]] = true;
		for (int j = 0; j < numbers.size(); j++) {
			if (!used[numbers[j]]) {
				f.push_back(numbers[j]);
				used[numbers[j]] = true;
				for (int k = 0; k < numbers.size(); k++) {
					if (!used[numbers[k]]) {
						f.push_back(numbers[k]);
						used[numbers[k]] = true;
						if (f[2] != 1 && max_commom_divisor(f[0] * 10 + f[1], f[2]) == 1) {
							fractions.push_back(f);
						}
						f.pop_back();
						used[numbers[k]] = false;
					}
				}
				f.pop_back();
				used[numbers[j]] = false;
			}
		}
		used[numbers[i]] = false;
	}
	return fractions;
}
void build_formula() {
	vector<int> formula;
	vector<vector<int>>fractions1 = build_fraction();
	for (int i = 0; i < fractions1.size(); i++) {
		formula.clear();
		for (int j = 0; j < fractions1[i].size(); j++) {
			formula.push_back(fractions1[i][j]);
			used[fractions1[i][j]] = true;
		}

		vector<vector<int>>fractions2 = build_fraction();
		for (int k = 0; k < fractions2.size(); k++) {
			for (int v = 0; v < fractions2[k].size(); v++) {
				formula.push_back(fractions2[k][v]);
				used[fractions2[k][v]] = true;
			}

			vector<vector<int>>fractions3 = build_fraction();
			for (int x = 0; x < fractions3.size(); x++) {
				for (int y = 0; y < fractions3[x].size(); y++) {
					formula.push_back(fractions3[x][y]);
				}
				if (formula_verification(formula)) {
					result.push_back(formula);
				}
				for (int y = 0; y < fractions3[x].size(); y++) {
					formula.pop_back();
				}
			}

			for (int v = 0; v < fractions2[k].size(); v++) {
				formula.pop_back();
				used[fractions2[k][v]] = false;
			}

		}

		for (int j = 0; j < fractions1[i].size(); j++) {
			used[fractions1[i][j]] = false;
		}
	}
}

int main() {
	for (int i = 0; i < 10; i++) {
		used[i] = false;
	}
	build_formula();
	for (int i = 0; i < result.size(); i++) {
		printf("%d%d/%d+%d%d/%d=%d%d/%d", result[i][0], result[i][1], result[i][2], result[i][3], result[i][4], result[i][5], result[i][6], result[i][7], result[i][8]);
		printf("\n");
	}
}