哑谜，回文和暴力之美

暴力搜索是一个有趣的东西。至少刘汝佳是这么认为的。编程之美的4.10节就是典型的暴力题。虽然作者将其难度定义为一颗星，但却不能因此认为这个类型的问题就是那么容易的，很多可能需要一些有创造力的想法。

不妨试试下面这几道题：

Island of Logic:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=533

Meta-loopless sort:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=107&page=show_problem&problem=46

How big is it?:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=953

No tipping:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=109&page=show_problem&problem=1064

Addition chains:

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=109&page=show_problem&problem=470

我先把其中的例题用深搜来试解一下。因为题目的解空间非常小，所以没有做什么优化。

关于节后问题：问题1，N位的总回文数为：9*pow(10, n/2 + n&1 - 1)。问题2见下面的代码。

1. 神奇的9位数：

vector<int> res;
int used[10];

void dfs(int i = 1, int v = 0) {
if (i == 10) {
 res.push_back(v);
return;
 }

for (int k = 1; k <= 9; ++k) {
if (used[k]) continue;
int vv = v*10 + k;
if (vv%i) continue;
 used[k] = 1;
 dfs(i+1, vv);
 used[k] = 0;
 }
}

int main() {
 dfs();
for (size_t i = 0; i < res.size(); ++i)
 cout<<res[i]<<'\n';
return 0;
}

2. 人过大佛寺×我=寺佛大过人以及问题2

下面的程序没有经过优化，所以会比较慢一点。另外，评估函数也只是简单满足需要。

vector<string> results;
vector<int> tested;
vector<int> used;

string equation;
int base;

bool satisfy(const string& s) {
char* next = 0;
int r = strtoul(s.c_str(), &next, base);
while (*next != '=') {
char op = *next++;
int t = strtoul(next, &next, base);
switch(op) {
case '+': r += t; break;
case '-': r -= t; break;
case '*': r *= t; break;
case '/': r /= t; break;
 }
 }

int b = strtoul(++next, 0, base);
return r == b;
}

void init(const string& str, int b = 10) {
 equation = str;
base = b;
 used.assign(base, 0);
 tested.assign(26, 0);
 results.clear();
}

void dfs(size_t i = 0) {
while (i < equation.length() && !islower(equation[i])) ++i;
if (i >= equation.length()) {
if (satisfy(equation))
 results.push_back(equation);
return;
 }

char c = equation[i], cc = c;
if (tested[c - 'a']) return;
 tested[c - 'a'] = 1;

for (int k = (i == 0 || !isalnum(equation[i-1])); k < base; ++k) {
if (used[k]) continue;
 used[k] = 1;
char t = k < 10? '0' + k: 'A' + k - 10;
 replace(equation.begin() + i, equation.end(), cc, t);
 dfs(i+1);
 cc = t; // for next iteration
 used[k] = 0;
 }
 replace(equation.begin() + i, equation.end(), cc, c);
 tested[c - 'a'] = 0;
}

void output(ostream& os) {
if (results.size()) {
for (size_t i = 0; i < results.size(); ++i)
 os<<results[i]<<'\n';
 }
else
 os<<"No solution.\n";
}

int main() {
 init("abcde*f=edcba", 10);
 dfs();
 output(cout);
 cout<<'\n';

 init("he*he=she", 10);
 dfs();
 output(cout);
 cout<<'\n';

 init("he*he=she", 16);
 dfs();
 output(cout);

return 0;
}