【Ruby】make 10 パズルを解くプログラムを書いてみる

2023年5月21日Ruby

こんにちは、しきゆらです。
今回は、make10パズルを解くためのプログラムを雑に書いてみたのでおいておきます。

make10パズルとは

make 10パズルは、4つの数字を四則演算を使って10を作るパズルです。 テンパズル・10パズルとも呼ばれるようです。

今もあるのかわかりませんが、以前東急線内で広告として利用されていたこともあるので 見たことがある方は多いのではないかと思います。

このようなmake10パズルですが、個人的にはだいぶ得意だと思っていました。 そんな中、たまたま見かけたパズルが解けず悔しかったので、どうせならプログラムを書いてみようと思ってやってみました。

今回は、その記録としてメモしておきます。

make10パズルを解くプログラムを書いてみる

諸々確認して、いわゆる難問といわれるものも答えを導いてくれるようになったものをいかにおいておきます。

# math_formula: 例: [1, :+, 3, :-, 4, :quo, 5]
def calc_head(math_formula)
    formula = Marshal.load(Marshal.dump(math_formula))

    result = formula.shift
    while formula.size != 0
        tmp_formula = formula.slice!(0, 2)
        next if tmp_formula.last == 0
        result = result.send(*tmp_formula) 
    end

    return result
end

# math_formula: 例: [1, :+, 3, :-, 4, :quo, 5]
def calc_tail(math_formula)
    formula = Marshal.load(Marshal.dump(math_formula))
    
    result = formula.pop
    while formula.size != 0
        tmp_formula = [formula.slice!(-2, 2), result].flatten
        next if tmp_formula.last == 0
        result = tmp_formula.first.send(*tmp_formula.slice(-2, 2))
    end

    return result
end

# str: 数字4桁の文字列(例: 1234)
def make_formula(str)
    raise StandardError.new("'#{str}'は処理できません") if str.length != 4 || str.to_i <= 0

    str.split("").map(&:to_i).permutation(4)
end

# main部分
nums_permutation = make_formula(gets.strip)
opts_permutation = %i[+ - * quo].repeated_permutation(3)

results = []

nums_permutation.each do |nums|
    opts_permutation.each do |opts|
        math_formula = nums.zip(opts).flatten.compact

        if calc_head(math_formula) == 10 || calc_tail(math_formula) == 10
            results << math_formula
        end
    end
end

results.uniq!
results.each {|result| p result}
p results.size

上記を使って、いわゆる難問といわれる問題を解くと以下のように回答が返ってきます。

$ > ruby solver.rb
3478 # 入力値
[8, :*, 3, :-, 7, :quo, 4]

$ > ruby solver.rb
1337
[3, :*, 1, :+, 7, :quo, 3]
[7, :quo, 3, :+, 1, :*, 3]

以下で、思考の流れを置いておきます。

思考の流れ

上記のウィキペディアを見ると、指数関数や並んだ2つの数をまとめて二桁の数と考える場合など、いくつか特殊ルールがあるようですが、まずは基本となる四則演算に絞って考えてみます。

数字が4つと四則演算の組み合わせで考えればよいだろう、というところまでは想像がついたので 単純に0～9の10個の数と+、-、×、÷の4つの演算の組み合わせをまずは全部出そう、というのがスタート地点でした。

たとえば、ウィキペディアにあった例である1358をもとに考えてみます。

1358の場合、数と数の間に演算子を挟めばよいので1+3+5+8、1+3+5-8 ～ 1÷3÷5×8、1÷3÷5÷8のように全パターンを網羅できればよいわけです。 もっと一般化すると、1桁の数a、b、c、dについて、数と数の3つの間に+、-、×、÷の4つの演算子から1つを選んで並べればよいはずです。

a、b、c、dもそれぞれ0～9の10個の数からそれぞれ1つ選ぶので、 組み合わせ全体としては、数が10の4乗の並び方、演算子が3か所に対して4つから1つ選ぶので4の3乗の並び方があるわけです。

思った通りに書いてみる

ざっくり書いたプログラムはこんな感じです。 簡単に解説してみます。

nums_permutation = (1..9).to_a.permutation(4).to_a
opts_permutation = %w[+ - * /].permutation(3).to_a

p nums.size
p opts
results = []

nums_permutation.each do |nums|
    opts_permutation.each do |opts|
        math_formula = nums.zip(opts).flatten.compact
        result = eval(math_formula.join(" "))

        if result == 10
            results << math_formula
            p "#{math_formula.join(" ")} is #{result}"
        end
    end
end

Array#permitationは引数nを受けて、サイズnの順列を生成するメソッドになります。 まさに、今回必要としているメソッドになります。

Array#permutation (Ruby 3.2 リファレンスマニュアル)

irbで動きを見てみます。 数学でいう所の4P2の一覧を生成してくれるわけですね。

irb(main):001:0> [1,2,3,4].permutation(2).to_a
=> [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4], [3, 1], [3, 2], [3, 4], [4, 1], [4, 2], [4, 3]]

なお、同様に4C2のように順列ではなく組み合わせ一覧を生成してくれるメソッドもあります。

irb(main):002:0> [1,2,3,4].combination(2).to_a
=> [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

本題に戻って、4つの数と3か所の演算子をそれぞれ順列として一覧を生成しているのが1～2行目になってます。 なお、後から気づきましたが、これだと足りない場合があります。

nums = (1..9).to_a.permutation(4).to_a
opts = %w[+ - * /].permutation(3).to_a

パターンを生成出来たら、それぞれを組み合わせて計算すればよいはず。 というのが、以下の部分になってます。 愚直にそれぞれのパターンをArray#zipで1つの配列にして、計算させてます。

results = []

nums.each do |list|
    opts.each do |opt|
        math_formula = list.zip(opt).flatten.compact
        result = eval(math_formula.join(" "))

        if result == 10
            results << math_formula
            p "#{math_formula.join(" ")} is #{result}"
        end
    end
end

回すと、それっぽいのもが生成されます。

> ruby solver.rb
...
 [9, "-", 8, "/", 6, "+", 2],
 [9, "*", 8, "/", 6, "-", 2],
 [9, "/", 8, "*", 6, "+", 4],
 [9, "+", 8, "-", 7, "*", 1],
 [9, "+", 8, "-", 7, "/", 1],
 [9, "+", 8, "/", 7, "*", 1],
 [9, "-", 8, "/", 7, "+", 2],
 [9, "/", 8, "*", 7, "+", 3]]

確認してみる

では、それっぽいものが出てきたので、その中から1つをピックアップして確認してみます。 例として、9, "*", 1, "/", 4, "+", 8の場合をとって、それぞれ計算してみる。

  • 9 * 1 = 9
  • 9 / 4 = 2.25
  • 2.25 + 8 = 10.25

・・・あれ、10にならないですね。

Rubyさんはなぜこれを答えとして出してきたんでしょうか。 irb上でも確認してみます。

irb(main):001:0> eval '9 * 1 / 4 + 8'
=> 10

ほう・・・。

こういう時に怪しいのは商の計算です。 9 / 4を計算してみましょう。

irb(main):002:0> 9 / 4
=> 2

なるほど、今回の場合だと/は使えないですね。

直してみる

調べてみると、Numeric#quoというよさげなメソッドを見つけました。 なるべく正確な数値を返してくれるようで、有理数も含めて計算してくれるようです。

ということで、/をquoに差し替えておきます。

また、計算をevalで行っているのでRationalが文字列としてきちんと処理してくれません。 なので、文字列にしてevalに食わせるのではなく、メソッド呼び出しに差し替えます。

eval部分をいかのように書き換えます。

# math_formula: 例: [1 + 3 - 4 quo 5]
def calc(math_formula)
    formula = Marshal.load(Marshal.dump(math_formula))

    result = formula.shift
    while formula.size != 0
        tmp_formula = formula.slice!(0, 2)
        next if tmp_formula.last == 0
        result = result.send(*tmp_formula) 
    end

    return result
end

先頭から1つ数を取得し、後は[演算子, 数]を取ってきて計算していく流れです。

これでも同様に処理してみると、前よりも精度よく出せるようになりました。

合わせて、一覧を出すよりも4つの数を与えると計算式を出してくれるようになったほうが嬉しいので、処理を変えてみます。

# math_formula: 例: [1 + 3 - 4 quo 5]
def calc(math_formula)
    formula = Marshal.load(Marshal.dump(math_formula))

    result = formula.shift
    while formula.size != 0
        tmp_formula = formula.slice!(0, 2)
        next if tmp_formula.last == 0
        result = result.send(*tmp_formula) 
    end

    return result
end

def make_formula(str)
    raise StandardError.new("'#{str}'は処理できません") if str.length != 4 || str.to_i <= 0

    str.split("").map(&:to_i).permutation(4)
end

# main部分
nums_permutation = make_formula(gets.strip)
opts_permutation = %i[+ - * quo].repeated_permutation(3)

results = []

nums_permutation.each do |nums|
    opts_permutation.each do |opts|
        math_formula = nums.zip(opts).flatten.compact

        if calc(math_formula) == 10
            results << math_formula
        end
    end
end

再度確認してみる

先ほどの例である「9148」を例に処理させてみます。

$ > ruby solver.rb
9148
[9, :-, 1, :quo, 4, :+, 8]
[9, :quo, 4, :-, 1, :*, 8]
[8, :quo, 4, :+, 9, :-, 1]
[8, :quo, 4, :-, 1, :+, 9]

9, "*", 1, "/", 4, "+", 8が結果に表示されなくなってますね、よさそうです。

では、難問といわれる問題を食わせてみてどうなるかを見てみましょう。

$ > ruby solver.rb
1337
[7, :quo, 3, :+, 1, :*, 3]

$ > ruby solver.rb
3478
0

よさそうかな、という所だったんですがいくつか回答を出してくれないものがあるようです。 考え直してみます。

3478の場合、答えが1パターンしかないようで、8 * (3 - 7 / 4)というのが解のようです。 この答えと自分の処理を見ると頭から処理させる方式なので、後ろのほうでごちゃごちゃ処理する形だとうまく見つけることができなさそうでした。

ということで、既存の処理を後ろから処理するようなものも作ってみます。

# math_formula: 例: [1, :+, 3, :-, 4, :quo, 5]
def calc_tail(math_formula)
    formula = Marshal.load(Marshal.dump(math_formula))
    
    result = formula.pop
    while formula.size != 0
        tmp_formula = [formula.slice!(-2, 2), result].flatten
        next if tmp_formula.last == 0
        result = tmp_formula.first.send(*tmp_formula.slice(-2, 2))
    end

    return result
end

これを追加して処理させると以下のようになります。

$ > ruby solver.rb
3478
[8, :*, 3, :-, 7, :quo, 4]

見つけてくれました、よさげです。 ここまでのものを反映させたのが、一番最初に記載していたものになります。

まとめ

ここまで、make10パズルを解くための方法を考えて、力技で何とかしてみました。

おそらくですが、細かく見るとおかしなものを見つけている場合や、見つけられないものもあるかもしれません。 また、書き方的にあまりよくないことをしている可能性もあります。

「もう少し考えることがあるだろう」とか、「俺がもっといいコード書いてやるぜ」とかあれば、ぜひコメント欄で教えていただければ嬉しいです。

今回、はここまで。

おわり

Posted by しきゆら