/*
2005/4 ミスティック・エイト
coded by Isaku WADA
 ┌──────────────┬─────┬───────┐
 │コンパイラ         │ 実行時間 │ファイルサイズ│
 ├──────────────┼─────┼───────┤
 │Visual Studio C++ 6.0     │ 14.359 秒│ 49152 byte │
 │Visual Studio C++ 2003     │ 14.796 秒│ 49152 byte │
 │Borland C++ 5.5.1 for Win32 │ 24.391 秒│ 56320 byte │
 │gcc-2.953(djgpp)      │ 30.714 秒│ 113761 byte │
 │gcc-3.3.3(cygwin)      │ 24.969 秒│ 19537 byte │
 │LSI C-86 Ver 3.30 試食版  │ 32.240 秒│ 15654 byte │
 │Turbo C Ver 1.5(small model)│ 26.860 秒│ 13088 byte │
 ├──────────────┼─────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP     │
 └──────────────┴─────────────┘

 ┌─────────────────────────────┐
 │ 8個の立方体の各面に1から48までの数が書いてある。その│
 │数の配列を展開図で示したのがFig.1で、数の書かれた面が立方│
 │体の表側である。これを、Fig.2のような2×2×2の大きな立│
 │方体に組んで(図中の数は正確でない)、その外側に見えている各│
 │面の4つの数の和を6面とも同じにしたい。         │
 │ この「ミスティック・エイト」は、「1921年11月11日午前6時│
 │以降の消印がある最初の10人の正解者に、500ポンド差し上げ│
 │ます」という、イギリスで1シリングで売られていた懸賞パズル│
 │である。                         │
 │ 解の数は意外に多く、6面とも同じにする和(定和と呼ぶ)もい│
 │ろいろな値にして組むことができる。そこで今回は、この定和を│
 │指定したときに、解(組み合わせ)の数がもっとも少なくなる定和│
 │をお答えいただきたい(もちろんそのときの解の数も)。この「最│
 │少解を持つ定和」が複数ある場合はすべてあげること。なお、解│
 │の数え方として、全体を回転しただけのものは別の解としてカウ│
 │ントしない。                       │
 │                             │
 │  Fig.1 8個の立方体の展開図             │
 │                             │
 │ (a)    (b)    (c)    (d)        │
 │  13     47     4     48         │
 │25 1 3  29 15 37  6 2 42  38 14 20       │
 │  11     21     16     44         │
 │  19     43     36     30         │
 │                             │
 │ (e)    (f)    (g)    (h)        │
 │  27     17     28     46         │
 │33 5 9  23 7 35  32 8 34  24 10 26       │
 │  31     39     12     22         │
 │  41     45     18     40         │
 │                             │
 │  Fig.2 2×2×2の立方体              │
 │      /\                     │
 │     /48 \                    │
 │    /\  /\                   │
 │   /13 \/46 >                  │
 │  │\  /\ / │                  │
 │  │1\/47 /24/                  │
 │  │\│\ /│/ │                  │
 │  │5\15│37/34/                  │
 │   \│\│/│/                   │
 │    \7│35/                    │
 │     \│/                     │
 └─────────────────────────────┘

 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ まず、指定する定和の範囲を求めます。8個の立方体をそれぞ│
 │れ回転させて、表面全体に現れる数の和の最小値と最大値を求め│
 │ます。最小値は366で最大値は810となります。それぞれ6│
 │で割った61と135が解が存在する可能性のある定和の最小値│
 │と最大値になります。プログラムは61から135までを定和と│
 │して探索します。                     │
 │ 定和が決まったら、立方体を大きな立方体のどこに置くかを決│
 │めます。全体を回転しただけのものは別の解としないので、西南│
 │上に(a)を固定し、西南下の立方体が西北上と東南上の立方体よ│
 │り若いものになるようにします。8個の立方体のうち1つが固定│
 │されているため7重forループになります。どこに何を置くか│
 │1つ決まるごとに、後で使う処理を高速化するための早見表を作│
 │成します。また、枝刈りのため、置いた立方体が面を新しく完成│
 │させた後、新しい面の和が定和と等しくなる可能性があるかどう│
 │か検査して、可能性がなければスキップします。       │
 │ 次に、各立方体を24通りに回転させて置いてゆき、各面の数│
 │の和が定和と等しくなる解を探索します。具体的には8重for│
 │ループで回転させてゆきます。西、南、上、下、北、東の順に、│
 │面が完成し次第に、早見表を使って和を求めます。和が定和と異│
 │なればスキップします。全ての和が定和と等しい解を発見したら│
 │カウントします。現在の定和で解が存在し、解の数が現在の最少│
 │解の数より等しいか小さい時は、その時の定和と解の数を表示し│
 │ます。                          │
 │ 実際に実行すると、定和が62と63のときに、解の数が1な│
 │ので、他の定和で探索する時は解の数が2になった時点で、次の│
 │定和に進みます。                     │
 │ 確認として、定和が63以下のとき、解が見つかれば展開図を│
 │表示します。                       │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 24通りの回転について、面の向きを表す配列を、最初は間違│
 │っていたので、違った結果になっていました。展開図を表示する│
 │ようにした後、得られた展開図と問題文の展開図とを注意深く確│
 │認したところ、このバグに気づきました。このバグは潰すのにも│
 │苦労しました。                      │
 │ 最初は、再帰呼び出しを使っていたのですが、多重forルー│
 │プにしたところ、だいぶ速くなりました。また、早見表の効果も│
 │かなりありました。新しい面の和が定和と等しくなる可能性があ│
 │るかどうか検査して可能性がなければスキップする枝刈りは、実│
 │行時間を約3分の1にする絶大な効果がありました。     │
 └─────────────────────────────┘
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/*┌─────┐
 │定数の宣言│
 └─────┘*/
enum { NORTH,EAST,SOUTH,WEST,TOP,BOTTOM };

 /* 各立方体の数の配列 */
int Num[8][6]={
 {13, 1,11,19,25, 3},{47,15,21,43,29,37},{ 4, 2,16,36, 6,42},
 {48,14,44,30,38,20},{27, 5,31,41,33, 9},{17, 7,39,45,23,35},
 {28, 8,12,18,32,34},{46,10,22,40,24,26}
};

 /* 各頂点で表面に現れる面の方向 */
int Outside[8][3]={
 {WEST,SOUTH,TOP}, {WEST,SOUTH,BOTTOM},
 {WEST,NORTH,TOP}, {WEST,NORTH,BOTTOM},
 {EAST,SOUTH,TOP}, {EAST,SOUTH,BOTTOM},
 {EAST,NORTH,TOP}, {EAST,NORTH,BOTTOM}
};

 /* 24通りの回転の面の方向 */
int Face[24][6]={
 {NORTH,EAST,SOUTH,WEST,TOP,BOTTOM},
 {EAST,SOUTH,WEST,NORTH,TOP,BOTTOM},
 {SOUTH,WEST,NORTH,EAST,TOP,BOTTOM},
 {WEST,NORTH,EAST,SOUTH,TOP,BOTTOM},

 {NORTH,WEST,SOUTH,EAST,BOTTOM,TOP},
 {EAST,NORTH,WEST,SOUTH,BOTTOM,TOP},
 {SOUTH,EAST,NORTH,WEST,BOTTOM,TOP},
 {WEST,SOUTH,EAST,NORTH,BOTTOM,TOP},

 {TOP,NORTH,BOTTOM,SOUTH,EAST,WEST},
 {TOP,EAST,BOTTOM,WEST,SOUTH,NORTH},
 {TOP,SOUTH,BOTTOM,NORTH,WEST,EAST},
 {TOP,WEST,BOTTOM,EAST,NORTH,SOUTH},

 {BOTTOM,NORTH,TOP,SOUTH,WEST,EAST},
 {BOTTOM,EAST,TOP,WEST,NORTH,SOUTH},
 {BOTTOM,SOUTH,TOP,NORTH,EAST,WEST},
 {BOTTOM,WEST,TOP,EAST,SOUTH,NORTH},

 {NORTH,TOP,SOUTH,BOTTOM,WEST,EAST},
 {EAST,TOP,WEST,BOTTOM,NORTH,SOUTH},
 {SOUTH,TOP,NORTH,BOTTOM,EAST,WEST},
 {WEST,TOP,EAST,BOTTOM,SOUTH,NORTH},

 {NORTH,BOTTOM,SOUTH,TOP,EAST,WEST},
 {EAST,BOTTOM,WEST,TOP,SOUTH,NORTH},
 {SOUTH,BOTTOM,NORTH,TOP,WEST,EAST},
 {WEST,BOTTOM,EAST,TOP,NORTH,SOUTH}
};

/*┌─────┐
 │変数の宣言│
 └─────┘*/
int Start;     /* 探索を開始する定和 */
int End;       /* 探索を終了する定和 */
int Sum;       /* 現在探索中の定和 */
int Count;     /* 現在の定和での解の数 */
int Min=32767; /* 最少解 */

 /*
    早見表:
    例えば、WstW[]は、西南上の頂点の西の面の数字
    (West south top West の頭文字をつなげて配列名にした)
  */
int WstW[24],WstS[24],WstT[24];
int WsbW[24],WsbS[24],WsbB[24];
int WntW[24],WntN[24],WntT[24];
int WnbW[24],WnbN[24],WnbB[24];
int EstE[24],EstS[24],EstT[24];
int EsbE[24],EsbS[24],EsbB[24];
int EntE[24],EntN[24],EntT[24];
int EnbE[24],EnbN[24],EnbB[24];

/*┌────────────────────┐
 │探索を開始する定和と終了する定和を求める│
 └────────────────────┘*/
void CalcStartEnd(void)
{
 int i,j,k,x,Min,Max,min_sum=0,max_sum=0;

 for (i=0;i<8;i++) {
  Min=32767; Max=0;
  for (j=0;j<8;j++) {
   for (x=k=0;k<3;k++) x+=Num[i][Outside[j][k]];
   if (x<Min) Min=x;
   if (x>Max) Max=x;
  }
  min_sum+=Min; max_sum+=Max;
 }
 Start=(min_sum+5)/6; /* 小数点以下切り上げ */
 End=max_sum/6;       /* 小数点以下切り捨て */
}

/*┌──────────────────┐
 │解を表示する(引数は各頂点の回転番号)│
 └──────────────────┘*/
void Print(int wst,int wsb,int wnt,int wnb,
           int est,int esb,int ent,int enb)
{
 printf("       %3d%3d\n",WntN[wnt],WnbN[wnb]);
 printf("       %3d%3d\n",EntN[ent],EnbN[enb]);
 printf("%3d%3d %3d%3d %3d%3d\n",
      WntT[wnt],EntT[ent],EntE[ent],EnbE[enb],EnbB[enb],WnbB[wnb]);
 printf("%3d%3d %3d%3d %3d%3d\n",
      WstT[wst],EstT[est],EstE[est],EsbE[esb],EsbB[esb],WsbB[wsb]);
 printf("       %3d%3d\n",EstS[est],EsbS[esb]);
 printf("       %3d%3d\n",WstS[wst],WsbS[wsb]);
 printf("       %3d%3d\n",WstW[wst],WsbW[wsb]);
 printf("       %3d%3d\n",WntW[wnt],WnbW[wnb]);
 printf("\n%dを処理中\r",Sum); fflush(stdout);
}

/*┌─────────────────────┐
 │各頂点の立方体を回転させながら置いてゆき、│
 │各面の和が定和と等しければカウントする  │
 └─────────────────────┘*/
void Sub(void)
{
 int wst,wsb,wnt,wnb,est,esb,ent,enb; /* 各頂点の回転番号 */
 int north2,east2,south2,west2,top2,bottom2; /* 各面の2個の和 */
 int north3,east3,south3,west3,top3,bottom3; /* 各面の3個の和 */

 for (wst=0;wst<24;wst++) for (wsb=0;wsb<24;wsb++) {
  west2=WstW[wst]+WsbW[wsb]; south2=WstS[wst]+WsbS[wsb];
  for (wnt=0;wnt<24;wnt++) {
   west3=west2+WntW[wnt]; top2=WstT[wst]+WntT[wnt];
   for (wnb=0;wnb<24;wnb++) {
    if (Sum!=west3+WnbW[wnb]) continue;
    north2=WntN[wnt]+WnbN[wnb]; bottom2=WsbB[wsb]+WnbB[wnb];
    for (est=0;est<24;est++) {
     south3=south2+EstS[est]; top3=top2+EstT[est];
     for (esb=0;esb<24;esb++) {
      if (Sum!=south3+EsbS[esb]) continue;
      east2=EstE[est]+EsbE[esb]; bottom3=bottom2+EsbB[esb];
      for (ent=0;ent<24;ent++) {
       if (Sum!=top3+EntT[ent]) continue;
       east3=east2+EntE[ent]; north3=north2+EntN[ent];
       for (enb=0;enb<24;enb++) {
        if (Sum!=bottom3+EnbB[enb]) continue;
        if (Sum!=north3+EnbN[enb]) continue;
        if (Sum!=east3+EnbE[enb]) continue;
        if (Sum<=63) Print(wst,wsb,wnt,wnb,est,esb,ent,enb);
        if (++Count>Min) return;
       }
      }
     }
    }
   }
  }
 }
}

/*┌────────┐
 │早見表を作成する│
 └────────┘*/
void SetTbl(int x,int*t1,int d1,int*t2,int d2,int*t3,int d3)
{
 int i;

 for (i=0;i<24;i++) {
  t1[i]=Num[x][Face[i][d1]];
  t2[i]=Num[x][Face[i][d2]];
  t3[i]=Num[x][Face[i][d3]];
 }
}

/*┌──────────────────┐
 │定和になる可能性があるかどうか調べる│
 │引数は(a)〜(h)の立方体のどれかを示す│
 └──────────────────┘*/
int Fail(int p1,int p2,int p3,int p4)
{
 int a,b,c,d; /* 立方体の面の番号 */

 for (a=0;a<6;a++) for (b=0;b<6;b++)
  for (c=0;c<6;c++) for (d=0;d<6;d++)
   if (Sum==Num[p1][a]+Num[p2][b]+Num[p3][c]+Num[p4][d])
    return 0; /* 可能性がある */
 return 1; /* 可能性がない */
}

/*┌──────────────────┐
 │各頂点にどの立方体を置くか決めてゆく│
 └──────────────────┘*/
void Solve(void)
{
 int f[8]; /* (a)〜(h) の出現フラグ */

 /* 各頂点がどの立方体になったか(wstは(a)に固定) */
 int wst=0,wsb,wnt,wnb,est,esb,ent,enb;

 SetTbl(wst,WstW,WEST,WstS,SOUTH,WstT,TOP); memset(f,0,sizeof f);
 for (wsb=1;wsb<6;wsb++) {
  SetTbl(wsb,WsbW,WEST,WsbS,SOUTH,WsbB,BOTTOM); f[wsb]=1;
  for (wnt=wsb+1;wnt<8;wnt++) {
   if (f[wnt]) continue; else f[wnt]=1;
   SetTbl(wnt,WntW,WEST,WntN,NORTH,WntT,TOP);
   for (wnb=1;wnb<8;wnb++) {
    if (f[wnb]||Fail(wst,wsb,wnt,wnb)) continue; else f[wnb]=1;
    SetTbl(wnb,WnbW,WEST,WnbN,NORTH,WnbB,BOTTOM);
    for (est=wsb+1;est<8;est++) {
     if (f[est]) continue; else f[est]=1;
     SetTbl(est,EstE,EAST,EstS,SOUTH,EstT,TOP);
     for (esb=1;esb<8;esb++) {
      if (f[esb]||Fail(wst,wsb,est,esb)) continue; else f[esb]=1;
      SetTbl(esb,EsbE,EAST,EsbS,SOUTH,EsbB,BOTTOM);
      for (ent=1;ent<8;ent++) {
       if (f[ent]||Fail(wst,wnt,est,ent)) continue; else f[ent]=1;
       SetTbl(ent,EntE,EAST,EntN,NORTH,EntT,TOP);
       for (enb=1;enb<8;enb++) {
        if (f[enb]) continue;
        if (Fail(wsb,wnb,esb,enb)) continue;
        if (Fail(wnt,wnb,ent,enb)) continue;
        if (Fail(est,esb,ent,enb)) continue;
        SetTbl(enb,EnbE,EAST,EnbN,NORTH,EnbB,BOTTOM); Sub();
        if (Count>Min) return;
       }
       f[ent]=0;
      }
      f[esb]=0;
     }
     f[est]=0;
    }
    f[wnb]=0;
   }
   f[wnt]=0;
  }
  f[wsb]=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(void)
{
 double StartTime=clock();

 CalcStartEnd();
 for (Sum=Start;Sum<=End;Sum++) {
  printf("%dを処理中\r",Sum); fflush(stdout); Count=0; Solve();
  if (Count>0&&Count<=Min) {
   printf("定和=%d  解の数=%d\n",Sum,Count);
   if (Count<Min) Min=Count;
  }
 }
 printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
 return EXIT_SUCCESS;
}