テンパズルをpythonで解くプログラム


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]




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

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

(左から順: 画像では逆になってるが)  
[![左から順](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]

