Tchisla簡介
最近玩到一個挺有意思的數字解密小游戲《Tchisla》，其規則類似算24點，也是利用一些數學運算和初始數字計算出目標數字，與算24點不同的是，Tchisla允許不限次數地使用一種初始數字（1~9），運算操作除了加減乘除外還包括了冪、平方根和階乘，以及重復這個數字形成多位數（比如初始數字為7，那么777也可以使用）。游戲中的題目以“target # seed”的形式給出，我們的目標就是使用盡量少的初始數字seed加以各種計算得到目標數字target，比如題目11 # 7，最簡解法就是11 = 77 / 7，比如題目5 # 9，最簡解法為5 = √9 + (√9)! / √9。這里有篇文章更詳細地介紹了這個游戲插電數字游戲——Tchisla 。
Tchisla求解器
這個游戲講道理還是挺難的，尤其是挑戰題目中的目標數都上千了，手動解題很難找到最優解，因此我花了半天用python寫了個求解器，目前看起來效果不錯，幾十秒鐘就幫我找到了了2016 # 1~9的所有最優解：
在求解Tchisla題目的過程中我相信是有一些內在的數學規律的，不過似乎很難總結出一套普適的最優求解算法，還是得暴力求解。暴力求解的思路其實挺簡單的，從1個初始數字開始，找到所有合理的可達值及其表達式，放入一個列表中，這個稱為第1代。后面再繼續搜索第2代、第3代等等，對于第n代，其中的可達值就是n個初始數字可以表示的所有結果，計算第n代時我們可以根據前面的n-1代結果進行組合來生成新一代數據，比如5個初始數字可以得到的目標值就是第1代結果+第4代結果的各種算數組合加上第2代結果+第3代結果的各種算數組合。過程中一但發現目標值，我們就得到答案了。
雖然思路很簡單，不過其中有些要注意的點，首先開方和階乘運算這樣的單目運算符不消耗初始數字，可以對一個表達式無限操作，為了避免無限搜索下去，所以第一點限制就是開方只對整數做、階乘只對小于一定值的整數做。另外浮點數的精度丟失問題比較麻煩，需要合適的取整。此外，為了避免一些不太可能的無效搜索，合理的限制搜索數據的最大值也是必要的。
除了以上思路之外，為了得到結果，我們還需要一套表達式系統來跟蹤我們的計算步驟，畢竟我們需要知道的最終是如何運算得到目標值而不僅僅是可以得到目標值的一個肯定。
以下放出代碼，除了階乘調用了系統庫外，沒有依賴別的庫。代碼前半部分是表達式系統，后半部分是求解器：
from math import factorialclass Expr:threshold = 1e-10def __init__(self, value):if isinstance(value, float):if value.is_integer():value = int(value)elif abs(value - round(value)) < Expr.threshold:value = round(value)self.value = valuedef __str__(self):raise TypeError("Should not call Expr.__str__()")class LiteralExpr(Expr):def __init__(self, value):Expr.__init__(self, value)self.literal = str(value)def __str__(self):return self.literalclass FactorialExpr(Expr):def __init__(self, expr: Expr):Expr.__init__(self, factorial(expr.value))self.child = exprdef __str__(self):if isinstance(self.child, BinaryExpr):return '({})!'.format(str(self.child))else:return str(self.child) + '!'class SqrtExpr(Expr):def __init__(self, expr: Expr):Expr.__init__(self, expr.value ** 0.5)self.child = exprdef __str__(self):if isinstance(self.child, LiteralExpr):return '√{}'.format(str(self.child))else:return '√({})'.format(str(self.child))class BinaryExpr(Expr):def __init__(self, oper: str, left: Expr, right: Expr, value):Expr.__init__(self, value)self.oper = operself.left = leftself.right = rightdef __str__(self):format_str = '({})' if isinstance(self.left, BinaryExpr) else '{}'format_str += ' {} 'format_str += '({})' if isinstance(self.right, BinaryExpr) else '{}'return format_str.format(str(self.left), self.oper, str(self.right))class AddExpr(BinaryExpr):def __init__(self, left: Expr, right: Expr):BinaryExpr.__init__(self, '+', left, right, left.value + right.value)class SubExpr(BinaryExpr):def __init__(self, left: Expr, right: Expr):BinaryExpr.__init__(self, '-', left, right, left.value - right.value)class MulExpr(BinaryExpr):def __init__(self, left: Expr, right: Expr):BinaryExpr.__init__(self, '*', left, right, left.value * right.value)class DivExpr(BinaryExpr):def __init__(self, left: Expr, right: Expr):BinaryExpr.__init__(self, '/', left, right, left.value / right.value)class PowExpr(BinaryExpr):def __init__(self, left: Expr, right: Expr):BinaryExpr.__init__(self, '^', left, right, left.value ** right.value)class TchislaSolver:value_limit = 10 ** 8power_limit = 30factorial_limit = 15class Found(BaseException):passdef __init__(self, target: int, seed: int):self.target = targetself.seed = seedself.all_candidates = set()self.current_candidates = []self.generations = []self.result = Nonedef solve(self, search_depth=10):try:while search_depth > 0:begin, end = 0, len(self.generations) - 1while begin <= end:self.cross_candidates(self.generations[begin], self.generations[end])begin += 1end -= 1self.add_literal(len(self.generations) + 1)self.next_generation()search_depth -= 1except TchislaSolver.Found:passreturn self.resultdef cross_candidates(self, c1, c2):for expr1 in c1:for expr2 in c2:self.add_addition(expr1, expr2)self.add_subtraction(expr1, expr2)self.add_multiplication(expr1, expr2)self.add_division(expr1, expr2)self.add_power(expr1, expr2)def add_candidate(self, expr):if expr.value == self.target:self.result = exprraise TchislaSolver.Found()if expr.value > TchislaSolver.value_limit:returnif expr.value not in self.all_candidates:self.all_candidates.add(expr.value)self.current_candidates.append(expr)self.add_factorial(expr)self.add_square_root(expr)def next_generation(self):self.generations.append(self.current_candidates)self.current_candidates = []def add_literal(self, repeats: int):self.add_candidate(LiteralExpr(int(str(self.seed) * repeats)))def add_addition(self, expr1: Expr, expr2: Expr):self.add_candidate(AddExpr(expr1, expr2))def add_subtraction(self, expr1: Expr, expr2: Expr):if expr1.value > expr2.value:self.add_candidate(SubExpr(expr1, expr2))else:self.add_candidate(SubExpr(expr2, expr1))def add_multiplication(self, expr1: Expr, expr2: Expr):self.add_candidate(MulExpr(expr1, expr2))def add_division(self, expr1: Expr, expr2: Expr):if expr1.value == 0 or expr2.value == 0:returnself.add_candidate(DivExpr(expr1, expr2))self.add_candidate(DivExpr(expr2, expr1))def add_power(self, expr1: Expr, expr2: Expr):if isinstance(expr2.value, int) and expr2.value <= TchislaSolver.power_limit:self.add_candidate(PowExpr(expr1, expr2))if isinstance(expr1.value, int) and expr1.value <= TchislaSolver.power_limit:self.add_candidate(PowExpr(expr2, expr1))def add_factorial(self, expr: Expr):if isinstance(expr.value, int) and expr.value <= TchislaSolver.factorial_limit:self.add_candidate(FactorialExpr(expr))def add_square_root(self, expr: Expr):if isinstance(expr.value, int) and expr.value > 0:self.add_candidate(SqrtExpr(expr))測試
這個求解器用起來很簡單，可以編寫一個簡單的例子進行測試，計算2016 # 1~9的最優解：
for i in range(1, 10):ts = TchislaSolver(2016, i)print('2016 = ' + str(ts.solve()))
結果如下：
代碼中對搜索和運算是有一些限制的，默認搜索10代，可達值最大只接受10^8，冪指數最大30，階乘數最大15，這些限制可以加快搜索速度，一般是夠用的，如果沒搜索到最優解，也可以嘗試修改以下值來調整并重新搜索：
value_limit = 10 ** 8power_limit = 30factorial_limit = 15
從上面的結果圖里還可以發現表達式系統還有優化的空間，有些括號是多余的，不過懶得搞了，能用就行~
)
＞)
