

wikipediaより

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

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

[code]

    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
    
[/code]


CC BY-SA 4.0
2022-06-17T22:47:18.873
89452
2022-06-19T03:47:09.923
2022-06-18T02:27:30.063
19110
53121
question
python python3 アルゴリズム
テンパズルをpythonで解くプログラム


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

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

(左から順: 画像では逆になってるが)  
[![左から順](https://i.stack.imgur.com/zG0pC.png)](https://i.stack.imgur.com/zG0pC.png)  
(左端と右端から)  
[![左右から](https://i.stack.imgur.com/NeY3Q.png)](https://i.stack.imgur.com/NeY3Q.png)

[code]

    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
    
[/code]

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

[code]

    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 
    
[/code]

* * *

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

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

[code]

    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]))
    
[/code]


CC BY-SA 4.0
2022-06-19T02:44:13.230
89466
2022-06-19T02:44:13.230
43025
89452
answer


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

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

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

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

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

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

[code]

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

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

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

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

[code]

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

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

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

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

今回くらいの計算だとそこまで影響は無いのですが、一応、浮動小数点数が含まれる演算をするときには[誤差](https://ja.wikipedia.org/wiki/%E6%B5%AE%E5%8B%95%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0#%E3%82%A8%E3%83%A9%E3%83%BC%EF%BC%88%E8%AA%A4%E5%B7%AE%EF%BC%89)の考慮をしておくのが良いでしょう。

つまり、`10`
とそのままイコールかどうかでチェックをするのではなくて少しだけ誤差を許すようにチェックをすると良いです。あるいは、[fractions](https://docs.python.org/ja/3/library/fractions.html)
を使って浮動小数点数ではなく分数として扱うようにするのも良いでしょう。


CC BY-SA 4.0
2022-06-19T03:47:09.923
89468
2022-06-19T03:47:09.923
19110
89452
answer