1

wikipediaより

テンパズル(10パズル)は、4桁の数字を一桁の数字4つとみなし、これに四則演算などを用いて10を作る遊び。メイクテン(make10)とも呼ばれる。切符の番号や車のナンバープレートなどでの短時間の遊びに利用され、日本経済新聞で渋滞時の時間の潰し方として紹介されたことがある。
一般的なルールとしては、四則演算のみの使用を許可し、数字の並べ替えも許可されるが、数字の結合は許可されない。一般的なルールの場合、全715通り中552通りの組み合わせ(並べ替えたものを数えると全10000通り中8147通り)で10を作ることができる。解き方を1つでも見つければ正解となるが、使っていない数字があった場合は正解にならない。

下記のコードでは同じ解が重複して出力されるという欠点はあるもののなんとなく答えは出ます。
しかし難問といわれる[1,1,5,8]なんかは解けません。
[1,1,5,8]なんかも解けるようにするにはどこを改良すればよろしいのでしょうか。
1日で作ったお粗末なプログラムですがよろしくお願いします。
python 3.8を使いました。
以下コードです。

import    itertools
a=["1","2","3","4"]
   
b=["+","-","*","/" ]

for  c  in   itertools.permutations(a,4):
    for  d in   itertools.permutations(b,3):  
             try:
                                           
                                                                                        
                                            
                                              
                 
                                                  s1="("+c[0]+d[0]+c[1]+")"+d[1]+"("+c[2]+d[2]+c[3]+")"       
                                                  s2=c[0]+d[0]+"("+c[1]+d[1]+"("+c[2]+d[2]+c[3]+")"+")"
                                                  s3=c[0]+d[0]+"("+"("+c[1]+d[1]+c[2]+")"+d[2]+c[3]+")"
                                                  s4="("+c[0]+d[0]+"("+c[1]+d[1]+c[2]+")"+")"+d[2]+c[3]
                                                  s5="("+"("+c[0]+d[0]+c[1]+")"+d[1]+c[2]+d[2]+c[3]+")"
                                                  s6=c[0]+d[0]+c[1]+d[1]+c[2]+d[2]+c[3]
                                                  
                                                   
                                                 
                                                       
                                                      
                                                      

                                                  sss=eval(s1)
                                                  ssss=eval(s2)
                                                  sssss=eval(s3)
                                                  ssssss=eval(s4)
                                                  sssssss=eval(s5)
                                                  
                                                      
                                                  if  sss==10   :
                                       
                                                     print( s1+ "=10")
                                                  if   ssss==10:
                                                     print(s2+"=10")
                                                 
                                                  if   sssss==10:
                                                     print(s3+"=10")
                                                  if   ssssss==10:
                                                     print(s4+"=10")
                                                  if   sssssss==10:
                                                     print(s5+"=10")
                                                  
                           
             except ValueError   :
                 pass
             except ZeroDivisionError   :
                 pass
2
  • itertools.permutationsをitertools.product(b,repeat=3)と変更すればできました。重複順列でした。
    – m.n.
    Commented 2022年6月19日 10:07
  • ご協力いただきました皆様に深く感謝します。ありがとうございました。
    – m.n.
    Commented 2022年6月19日 10:19

2 件の回答 2

1

テンパズルを解くプログラム
このスクリプトでは, 演算子の優先順位関係なしに 演算を適用する順番で行います
パターンとしては

  • 左から順に適用させていく
  • 左右を適用したのち, 両方の結果に演算適用
  • 片側から順に適用するが, 減算・除算などの被演算子の順序で値が変わるもの (加算・乗算では入れ替えても値は同じ)

(左から順: 画像では逆になってるが)
左から順
(左端と右端から)
左右から

import itertools
import numpy as np

oplist = [np.add, np.subtract, np.multiply, np.true_divide]
def calc10(nums):
    arr = np.array(list(set(itertools.permutations(nums))), dtype=np.int16) # 9*9*9*9 でもオーバーしない型
    for ops in itertools.product(oplist, repeat=3):
        with np.errstate(divide='ignore', invalid='ignore'):
            res = res2 = arr[:, 0]  # res2 = res.copy()
            for op, c in zip(ops, range(1, 4)):
                res = op(res, arr[:, c])
                res2 = op(arr[:, c], res2)
        if np.any(res == 10) or np.any(res2 == 10):
            return arr, ops, res, res2

        with np.errstate(divide='ignore', invalid='ignore'):
            res = ops[2](ops[0](arr[:, 0], arr[:, 1]), ops[1](arr[:, 2], arr[:, 3]))
        if np.any(res == 10):
            return True

    return False

🟡 解くことのできない(はずの)数字

noten_list = []
for num in range(10000):
    dec = list(format(num, '04d'))
    if dec != sorted(dec): continue
    if not calc10(map(int, dec)):
        noten_list.append(num)
print(len(noten_list))   # 解けない数字は 163 

1158 の場合, 数字の組み合わせ 12通り
結果に出てる演算手順で 10に。その時の数字順は [5, 1, 1, 8]
先に示した「パターン」の 除数, 被除数 の順番で 10になる / ならないの違いが出るもの

それ以外がうまく動いてるなら, このパターンを追加するとよいのかも?

num = 1158
dec = list(format(num, '04d'))
calc10(map(int, dec))

#(array([[1, 1, 8, 5],
#        [1, 8, 1, 5],
#        [1, 1, 5, 8],
#        [1, 5, 1, 8],
#        [5, 8, 1, 1],
#        [8, 1, 5, 1],
#        [8, 5, 1, 1],
#        [5, 1, 1, 8],
#        [1, 5, 8, 1],
#        [1, 8, 5, 1],
#        [5, 1, 8, 1],
#        [8, 1, 1, 5]], dtype=int16),
# (<ufunc 'true_divide'>, <ufunc 'subtract'>, <ufunc 'true_divide'>),
# array([-1.4  , -0.175, -0.5  , -0.1  , -0.375,  3.   ,  0.6  ,  0.5  ,
#        -7.8  , -4.875, -3.   ,  1.4  ]),
# array([ 0.71428571, -0.71428571,  2.        , -2.        , -1.66666667,
#         0.20512821,  2.66666667, 10.        ,  0.33333333, -0.33333333,
#         0.12820513,  5.71428571]))
1
  • 計算は 8/(1-1/5) == 10
    – oriri
    Commented 2022年6月19日 2:50
0

質問文のプログラムでは、与えられた数を使う順番は全探索できていますが、演算子を重複を許して並べる順番と、それらを数たちにどの順番で適用していくのかが全探索できていません。

また、割り算をするときに浮動小数点数になっているので誤差についても一応考慮が必要です。

ひとつずつ見ていきます。

演算子たちを重複を許して順列に並べる

たとえば a = [1, 2, 3, 4] のとき、1 + (2 + (3 + 4)) = 10 という答えが探索できていません。+ は多くても 1 回しか使えないからです。

今回の場合、それぞれの演算子は多くてもたかだか 3 回までしか使われないので、+-*/ を 3 回ずつ並べたリストから長さ 3 の重複なし順列を作れば良いです。

b = ["+", "-", "*", "/"] * 3

ただしこうするとその分同じ解がたくさん出てきてしまいます。これを避けるには真面目に重複あり順列を作るようにすると良いです。

数たちをどの順番で演算していくか網羅する

今回だと手で場合分けが書かれている部分ですが、漏れがあります。以下の一覧で示す最初の形がありません。s5 として定義されているものが実装ミスです。

# ★が何かしらの演算子だとして……
((a★b)★c)★d
(a★b)★(c★d)
(a★(b★c))★d
a★((b★c)★d)
a★(b★(c★d))

更に、今回のプログラムでは try ... except の書き方に問題があります。今回の書き方では s1 から s5 までのどこかひとつでもエラーが起こると s1 から s5 まですべてが無視されてしまいます。毎回エラーを確認するようにすべきです。たとえば try: eval(s) except: None をしてくれるメソッドを定義して毎回呼び出すようにするなどでラクができます。

もっと言うと、今回の問題のように数が 4 つしか無い場合は手で網羅できますが、もしもっと数が多くなるのであれば機械的に網羅する方法を考えると更にラクができます。可能な抽象構文木の形を網羅できれば良いので、葉が N 個ある二分木の形を網羅することを考えると良いです。この形で突き進めると(意図しない挙動を生みがちなため使うのが避けられがちな)eval を使わずに実装できます。

浮動小数点数の誤差を気にする

今回くらいの計算だとそこまで影響は無いのですが、一応、浮動小数点数が含まれる演算をするときには誤差の考慮をしておくのが良いでしょう。

つまり、10 とそのままイコールかどうかでチェックをするのではなくて少しだけ誤差を許すようにチェックをすると良いです。あるいは、fractions を使って浮動小数点数ではなく分数として扱うようにするのも良いでしょう。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。