数式パズルを解くpythonプログラム
下のような算数のパズルを一度は見たことがあると思います。
1 1 5 8 の4つの数字で答えが10になる式を作れ。
※使用可能なのはカッコと+-×÷のみ
答えは後述しますが、この手の問題は簡単に解けるものもあればとんでもなく難しいものもあります(上の問題は後者)。また、こういう問題は特別な知識が必要なわけでもなく、そして解説のしようもないので答えが載っていることは少ないです。答えが載っていないと解けないときにどうしてもモヤモヤしてしまいますよね。ここではその悩み(?)を解決する、上のようなパズルを解いてくれるpythonプログラムを紹介します。
1. パズルのいくつかの "定型"
さて、このパズルにはいくつかの計算の"定型"のようなものがあります。定型は、大きく分けて5つあります。
※定型で示す演算子はあくまで一例です。
(1) ((〇+〇)+〇)+〇 型
まずは一番わかりやすい、ただ前から計算していくだけのパターンです。
+だけなら簡単に解けるのですが、4489 → ((9-4)×8)÷4=10 などのように乗算、除算が入っているとちょっと面倒です。
(2) (〇+〇)×(〇+〇) 型
これもまあまあよくあります。この型だと断定できれば超簡単に解けますが、(1)の型とよく迷います。例えば 4678 → (6×7)-(4×8)=10 などです。
(3) (〇-(〇×〇))+〇 型
たまにある難問の形です。この型は計算の途中で分数が出てくることもよくあります。例えば 2348 → (2-(3÷4))×8 = 10 などです(しかし2348に関しては定型(1)で ((2×3)-4)+8=10 と解けます)。
(4) 〇-((〇+〇)×〇) 型
これも(3)と同じで難問型です。(3)と分ける理由は1項目と2項目の間にマイナスがあるだけです(マイナスがいるせいで符号が反転しやがるので分けています)。
(5) 〇-(〇-(〇×〇)) 型
これも(3)(4)と同じ難問型です。冒頭に出した問題もこの形です。
冒頭のものは 1158 → 8÷(1-(1÷5))=10 です(割と有名な難問です)。
2. 実装の方針
(1) 5パターンの判断
実装の方針ですが、5パターンある中からプログラムに「お前、適切なやつ選べ」と言ってもコンピューターにそんなことはほぼ無理です。なので、諦めて全探索を使います。全探索とはざっくりいうと「(起こりうる)すべてのパターンをすべて試す」というやり方です。文字通り非常に非効率ですが5パターン程度なら一瞬で終わります。ちなみに性能にもよりますが10,000～100,000パターンくらいまでなら一番簡単で速いと思います。具体的には以下の方法で実装します。
$${\displaystyle①パターン1を試す\\ 成功→終了、それ以外→②へ\\②パターン2を試す\\ 成功→終了、それ以外→③へ\\③パターン3を試す\\ 成功→終了、それ以外→④へ\\④パターン4を試す\\ 成功→終了、それ以外→⑤へ\\⑤パターン5を試す\\ 成功→終了、それ以外→エラー出力}$$
エラー出力というのは「10を作る方法が見つかりませんでした」という簡単なものなので$${\verb|try-except|}$$で実装します。
(2) 数字の順番
さて、パターンの判断以上に大事なものがあります。それは数字の順番で、ただ足すだけなら順番などどうでもいいんですが、かけ算などが入ってくると答えが変わってしまいます。
例として4678→(6×7)-(4×8)=10ですが、順番を変えれば(4×6)-(7×8)=-32となって答えが変わります(まあ当然といえば当然ですが)。しかし、単に入力のまま4678の順で5パターン当てはめていくだけでは本来は正解のはずの(〇×〇)-(〇×〇)でも正解にならないのでエラーを吐くだけです。そこで、4個の並び替えはすべて網羅して全探索する必要があります。
※4個の並び替えは$${4!=4\cdot3\cdot2\cdot1=24}$$通りなので、全探索しても$${24×5_{[パターン]} = 120}$$通りだけなので圧倒的に全探索のほうが良いです。
pythonの全探索は、$${\verb|itertools|}$$という素晴らしいモジュールがあるので簡単です。今回は中で順列のパターンを全て生成するのに使っています。
3. プログラムコード
import itertools
def calc(m1,m2,si):
try:
if si == 0:
return m1 + m2
elif si == 1:
return m1 - m2
elif si == 2:
return m1 * m2
elif si == 3:
return m1 / m2
else:
return None
except:
return None
def sign(sig):
if sig == 0:
return "+"
elif sig == 1:
return "-"
elif sig == 2:
return "×"
elif sig == 3:
return "÷"
else:
return None
def solve(n1,n2,n3,n4,num=10):
nlist = [n1,n2,n3,n4]
flag = False
ans1 = None
ans2 = None
for l in itertools.permutations(nlist):
for s in itertools.product([0,1,2,3],repeat=3):
n = l[0]
for m in range(3):
n = calc(n,l[m+1],s[m])
if n == num:
flag = True
ans1 = l
ans2 = s
if flag == True:
break
if flag == True:
print("((%s %s %s) %s %s) %s %s = %s"
% (ans1[0],sign(ans2[0]),ans1[1],sign(ans2[1]),
ans1[2],sign(ans2[2]),ans1[3],num))
else:
for k in itertools.permutations(nlist):
for t in itertools.product([0,1,2,3],repeat=3):
nu1 = calc(k[0],k[1],t[0])
nu2 = calc(k[2],k[3],t[2])
n = calc(nu1,nu2,t[1])
if n == num:
flag = True
ans1 = k
ans2 = t
if flag == True:
break
if flag == True:
print("(%s %s %s) %s (%s %s %s) = %s"
% (ans1[0],sign(ans2[0]),ans1[1],sign(ans2[1]),
ans1[2],sign(ans2[2]),ans1[3],num))
else:
for k in itertools.permutations(nlist):
for t in itertools.product([0,1,2,3],repeat=3):
nu1 = calc(k[1],k[2],t[1])
nu2 = calc(k[0],nu1,t[0])
n = calc(nu2,k[3],t[2])
if n == num:
flag = True
ans1 = k
ans2 = t
if flag == True:
break
if flag == True:
print("(%s %s (%s %s %s)) %s %s = %s"
% (ans1[0],sign(ans2[0]),ans1[1],sign(ans2[1]),
ans1[2],sign(ans2[2]),ans1[3],num))
else:
for k in itertools.permutations(nlist):
for t in itertools.product([0,1,2,3],repeat=3):
nu1 = calc(k[1],k[2],t[1])
nu2 = calc(nu1,k[3],t[2])
n = calc(k[0],nu2,t[0])
if n == num:
flag = True
ans1 = k
ans2 = t
if flag == True:
break
if flag == True:
print("%s %s ((%s %s %s) %s %s) = %s"
% (ans1[0],sign(ans2[0]),ans1[1],sign(ans2[1]),
ans1[2],sign(ans2[2]),ans1[3],num))
else:
for k in itertools.permutations(nlist):
for t in itertools.product([0,1,2,3],repeat=3):
nu1 = calc(k[2],k[3],t[2])
nu2 = calc(k[1],nu1,t[1])
n = calc(k[0],nu2,t[0])
if n == num:
flag = True
ans1 = k
ans2 = t
if flag == True:
break
if flag == True:
print("%s %s (%s %s (%s %s %s)) = %s"
% (ans1[0],sign(ans2[0]),ans1[1],sign(ans2[1]),
ans1[2],sign(ans2[2]),ans1[3],num))
else:
print("%s,%s,%s,%s から四則演算のみを使い %s を作る式は見つかりませんでした。"
% (n1,n2,n3,n4,num))
※$${\verb|%s|}$$連打は自分が$${\verb|f""|}$$苦手なだけ(というかどこに変数が入ってるか分からなくなる)なので気にしないでください。
※ここでは指定した数字にすることもできるようにしました。
4. 実行方法
実行方法は、
$${\displaystyle \verb|solve(n1,n2,n3,n4)|}$$
と入れてEnterを押すだけです(n1～n4のところには解かせたい数4つを入れてください)。また、第5引数に数を入れるとその数になるように計算式を作ってくれます。
