/*
2002/04 小町の輪
coded by Isaku WADA
 ┌────────────────────────────┐
 │ Fig.3のように,5つ描かれた円に,1から9までの数字を│
 │1字ずつ書き入れる。よく見ると,どの円の中も合計が13に│
 │なっている。このように,1から9までの数字を1字ずつ書き│
 │入れて,5つある円の中の数字の合計がすべて同じになるもの│
 │をほかにも見つけていただきたい。例を含めて何通りあるだろ│
 │うか。ただし,全体をそっくり裏返したものは別の解とはしな│
 │い。                          │
 │                            │
 │   Fig.3 小町の輪                 │
 │     ┌──┐┌──┐┌──┐┌──┐┌─┐    │
 │   ┌─┘┌─┼┘┌─┼┘┌─┼┘┌─┼┘ │    │
 │   │ 4│9│1│3│8│2│5│6│7 │    │
 │   └─┐└─┼┐└─┼┐└─┼┐└─┼┐ │    │
 │     └──┘└──┘└──┘└──┘└─┘    │
 │                            │
 └────────────────────────────┘

 ┌─────────┐
 │解答:4通り   │
 │         │
 │ 1 13:491382567 │
 │ 2 14:592347168 │
 │ 3 13:765238149 │
 │ 4 11:837164529 │
 └─────────┘

 ┌──────────────┬─────┬───────┐
 │コンパイラ         │実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Microsoft Visual C++ 6.0  │0.00066 秒│ 36864 byte │
 │Borland C++ 5.5 for Win32  │0.00136 秒│ 53760 byte │
 │gcc-2.953(djgpp)      │0.00077 秒│ 109249 byte │
 │gcc-2.953(cygwin)      │0.00129 秒│ 372324 byte │
 │LSI C-86 Ver 3.30 試食版  │0.00087 秒│ 13346 byte │
 │Turbo C Ver 1.5(small model)│0.00087 秒│ 10790 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium!!! 550 MHz │   OS:Windows 98   │
 └──────────────┴─────────────┘
 ┌──────────────────────────────┐
 │・プログラムの説明                     │
 │                              │
 │順列の生成には9個の整数変数a,b,c,d,e,f,g,h,iで制御する9重 │
 │forループを使いました。そして、変数の値が互いに異なるように │
 │するために、既に現れた数字かどうかを即座に調べることができる│
 │フラグの配列x[]を用意しました。例えば、外側のループで変数a等│
 │が決まったならば、x[a]=1のようにフラグを立てます。そして内側│
 │で例えば変数gの値が既に現れているかどうかを、        │
 │if (x[g]) continue;                     │
 │のようにして判断をし、枝刈りします。こうすることで、9個の変│
 │数全てが互いに異なるようになります。しかも、かなり高速に実現│
 │できます。                         │
 │                              │
 │プログラムは、変数a,bが決まった時点で一番左の円の和がa+bにな│
 │るので、それを変数sに保存します。そして、内側のループで残り │
 │の円内の和(b+c+d),(d+e+f),(f+g+h),(h+i)が決まった場合、それ │
 │がsと異なった時に枝刈りします。こうすることで、得られた結果 │
 │は、円内の和が全て等しくなります。さらに、裏返しを排除するた│
 │めに、a>iならば無視します。                 │
 │                              │
 │単純な9重ループにすることにより、関数呼び出しが抑制され、高│
 │速化に貢献しました。                    │
 ├──────────────────────────────┤
 │・感想                           │
 │                              │
 │今回は、できるだけ簡単なプログラムになるように心がけました。│
 │それでも、結果のスピードには満足しています。また、インデント│
 │するかどうか迷いましたが、コンパクトになり、結果、プログラム│
 │全体の見通しが良くなるため、インデントはしませんでした。コメ│
 │ントは少ないですが、プログラム自体が小さく、比較的簡単に理解│
 │できると思います。                     │
 └──────────────────────────────┘
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

/*┌──────┐
 │パズルを解く│
 └──────┘*/
void Solve(void)
{
  int a,b,c,d,e,f,g,h,i/*数字*/,s/*和*/,t=0/*解カウンタ*/;
  static char x[10]; /*数字が出現したかどうかのフラグの配列*/

  for (a=1;a<=9;a++) {
  for (b=x[a]=1;b<=9;b++) { if (x[b]) continue; s=a+b;
  for (c=x[b]=1;c<=9;c++) { if (x[c])              continue;
  for (d=x[c]=1;d<=9;d++) { if (x[d]||b+c+d!=s)    continue;
  for (e=x[d]=1;e<=9;e++) { if (x[e])              continue;
  for (f=x[e]=1;f<=9;f++) { if (x[f]||d+e+f!=s)    continue;
  for (g=x[f]=1;g<=9;g++) { if (x[g])              continue;
  for (h=x[g]=1;h<=9;h++) { if (x[h]||f+g+h!=s)    continue;
  for (i=x[h]=1;i<=9;i++) { if (x[i]||h+i!=s||a>i) continue;
    printf("%3d%3d:%d%d%d%d%d%d%d%d%d\n",++t,s,a,b,c,d,e,f,g,h,i);
  }x[h]=0;}x[g]=0;}x[f]=0;}x[e]=0;}x[d]=0;}x[c]=0;}x[b]=0;}x[a]=0;}
}

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

/*┌───────┐
 │メインルーチン│
 └───────┘*/
int main(int argc,char**argv)
{
    double StartTime=clock(); int i,num;

    if (argc==2) num=atoi(argv[1]); else num=1;
    for (i=0;i<num;i++) Solve();
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return 0;
}