朝日新聞2004年12月11日パズルパーク解答

プログラムの出力結果は以下の通り。

Find
1 * 2 - 3 / 4 - 5 - 6 * 7 / 8 + 9 = 0/32
cnt:1680

プログラムのソースは以下の通り。

#include "puzutl.h"

int cnt[8] ;                    // ＋，−，×，÷の利用回数
int num[4] = { 1, 3, 2, 2};     // ＋，−，×，÷の最大出現可能回数

struct struct_number {          // 数字を通分して記録する
  int m;                        // 分子
  int n;                        // 分母
  struct_number() { m=n=0;}
  struct_number( int x) { m=x; n=1;}
} dig[9];
int idig = 0;
int op[8];                      // 0:+, 1:-, 2:*, 3:/
int iop = 0;
void push( int n)
{
  dig[idig++] = n;
}
void calc( int p) {
  if( idig < 2) { pe( "Stack short\n"); exit(16);}
  int m1 = dig[idig-2].m, n1 = dig[idig-2].n;
  int m2 = dig[idig-1].m, n2 = dig[idig-1].n;
  idig--;
  int m, n;
  switch( p) {
  case 0:                       // ＋
    n = n1*n2; m = m1*n2 + n1*m2;
    dig[idig-1].m = m; dig[idig-1].n = n;
    //ps( "%d/%d + %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
    break;
  case 1:                       // −
    n = n1*n2; m = m1*n2 - n1*m2;
    dig[idig-1].m = m; dig[idig-1].n = n;
    //ps( "%d/%d - %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
    break;
  case 2:                       // ×
    n = n1*n2; m = m1*m2;
    dig[idig-1].m = m; dig[idig-1].n = n;
    //ps( "%d/%d * %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
    break;
  case 3:                       // ÷
    n = n1*m2; m = m1*n2;
    dig[idig-1].m = m; dig[idig-1].n = n;
    //ps( "%d/%d / %d/%d = %d/%d\n", m1, n1, m2, n2, m, n);
    break;
  default:
    pe( "unknown calc(%d)\n", p);
    exit(16);
  }
}
void ope( int p) {
  if( p == 2 || p == 3) {
    // ×，÷は出現したら即実行する
    calc( p);
  }
  else {
    // ＋または−は計算せずに取っておく
    if( p == 1) { dig[idig-1].m = -dig[idig-1].m; p = 0;}// −は+負数に変換する
    op[iop++] = p;
  }
} 
cstring opestr( int o) {
  cstring s[] = { "+", "-", "*", "/" };
  if( o >= 0 && o <= 3) return s[o];
  return "?";
}
void print( int a,int b,int c,int d,int e,int f,int g,int h)
{
  ps( "1 %s 2 %s 3 %s 4 %s 5 %s 6 %s 7 %s 8 %s 9 = %d/%d\n", opestr(a),opestr(b),opestr(c),opestr(d),opestr(e),opestr(f),opestr(g),opestr(h), dig[0].m, dig[0].n);
}
int main( int argc, cstring argv[])
{
  int           lcnt = 0;
  for( int a=0; a< 4; a++) {
    cnt[a]++;
    for( int b=0; b< 4; b++) {
      if( cnt[b] >= num[b]) continue;
      cnt[b]++;
      for( int c=0; c< 4; c++) {
        if( cnt[c] >= num[c]) continue;
        cnt[c]++;
        for( int d=0; d< 4; d++) {
          if( cnt[d] >= num[d]) continue;
          cnt[d]++;
          for( int e=0; e< 4; e++) {
            if( cnt[e] >= num[e]) continue;
            cnt[e]++;
            for( int f=0; f< 4; f++) {
              if( cnt[f] >= num[f]) continue;
              cnt[f]++;
              for( int g=0; g< 4; g++) {
                if( cnt[g] >= num[g]) continue;
                cnt[g]++;
                for( int h=0; h< 4; h++) {
                  if( cnt[h] >= num[h]) continue;
                  cnt[h]++;
                  iop = idig = 0;
                  push(1);push(2);ope(a);push(3);ope(b);push(4);ope(c);push(5);ope(d);push(6);ope(e);push(7);ope(f);push(8);ope(g);push(9);ope(h);
                  while( iop--> 0) {
                    calc(op[iop]);
                  }
                  if( dig[0].m == 0) { ps( "Find\n"); print(a,b,c,d,e,f,g,h);}
                  lcnt++; // ここに制約処理を書く
                  cnt[h]--;
                }
                cnt[g]--;
              }
              cnt[f]--;
            }
            cnt[e]--;
          }
          cnt[d]--;
        }
        cnt[c]--;
      }
      cnt[b]--;
    }
    cnt[a]--;
  }
  ps( "cnt:%d\n", lcnt);
  return    0;
}