一般化テンパズルを解くコードをC++で書いてみた

概要

テンパズルとは4つの数字を四則演算 (+,-,×,÷)でつなげて10にする遊びである。
ナンバープレートの数字を使って遊ぶあのパズルゲームで、渋滞中に周囲の車のプレートを見て遊んだ人は多いのではないだろうか？
この記事では、そのテンパズルを一般化して$n$個の数字で$k$を作るパズルの解を出力するC++のプログラムを公開する。

プログラムの使い方

標準入力で一行目に数字の数、目標の数値を与える。
二行目では数字のリストを与える。

(例) 4つの数3,4,7,8を使って10を作るとき(解が除算を必ず含む)

• sample_input

4 10
3 4 7 8

• sample_output

(3-(7/4))*8
8*(3-(7/4))
end

プログラムの解説

まず除算について、すべて整数なので計算結果は0除算の時を除き有理数になることが保証される。したがってpairで分母分子を保存しておけば除算が誤差なく計算できる。

数式(文字列)をkey / 評価値(pair<int, int>)をvalueとするmapを用意しすべての可能なパターンを格納する。効率的に探索するために、再帰式を用いる。最後に値が$k$に一致する数式を表示させている。

イメージしたのは算術式におけるインストラクションと評価文脈で、分割のやり方によってこれらを表現しているつもり。なお愚直に全探索しているため空間・時間ともに計算量は$O(n^2n!)$。手元のノートPCだと$n=8$程度でかなり時間がかかったが、重複の除外・枝刈り等すればもう少し効率的に探索できるだろう。

Snippet

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> Pll;

map<string, Pll> generate(vector<ll> v)
{
  map<string, Pll> T;
  if(v.size() == 1) {
    string key = (v[0] < 0) ? "("+to_string(v[0])+")": to_string(v[0]);
    T[key] = make_pair(v[0], 1);
    return T;
  }
  else {
    REP(i, v.size() - 1) {
      vector<ll> a,b;
      map<string, Pll>  s,t;
      FOR(j, 0, i) a.push_back(v[j]);
      FOR(j, i+1, v.size()-1) b.push_back(v[j]);
      s = generate(a);
      t = generate(b);
      for(auto m : s) for(auto n : t) {
        ll n1 = m.second.first;
        ll d1 = m.second.second;
        ll n2 = n.second.first;
        ll d2 = n.second.second;
        T["("+m.first+"*"+n.first+")"] = make_pair(n1*n2, d1*d2);
        T["("+m.first+"/"+n.first+")"] = make_pair(n1*d2, d1*n2);
        T["("+m.first+"+"+n.first+")"] = make_pair(n1*d2+n2*d1, d1*d2);
        T["("+m.first+"-"+n.first+")"] = make_pair(n1*d2-n2*d1, d1*d2);
      }
    }
    return T;
  }
}

void solve(vector<ll> v, ll k)
{
  do {
    map<string, Pll> T = generate(v);
    for(auto a : T) {
      if(a.second.second != 0 && a.second.first == k * a.second.second) {
        printf("%s\n", a.first.substr(1, a.first.length() - 2).c_str());
      }
    }
  } while(next_permutation(v.begin(), v.end()));
  printf("end\n\n");
}

int main()
{
  ll n = 0, k = 0, i = 0;
  cin >> n >> k;
  vector<ll> a(n);
  REP(i, n) cin >> a[i];
  sort(a.begin(), a.end());
  solve(a, k);
  return 0;
}