/* ---------------------------------------------------------------
  ○×ゲーム全探索
 -----------------------------------------------------------------
  並ぶ順番は
    ２１０
    ５４３
    ８７６
  とし、ビット列で保持している。
 ----------------------------------------------------------------- */
#include <stdio.h>

int numEnd[11];

// -------------------------------------------------------------------
// judge : 引数のビット列が列を成すかどうか判定する
// int ox (Input) ○または×が置かれている場所を示すビット列
// 返り値 : 列を成していれば1、成してなければ0
// -------------------------------------------------------------------
int judge(int ox)
{
  // 並ぶラインの定義
  static int line[] = {0111, 0222, 0444, 0700, 0070, 0007, 0124, 0421};
  int i;
  for( i = 0 ; i < 8 ; i++ ) {
    if( (line[i] & ox) == line[i] ) return 1;
  }

  return 0;
}

// -------------------------------------------------------------------
// search : 端から置いていってひたすら探索する
// int emp  (Input) まだ○も×も置かれていない場所を表す
// int me   (Input) 自分の手(奇数手目なら○)が置かれている(ry
// int you  (Input) 相手の手(奇数手目なら×)が(ry
// int step (Input) 何手目かを表す
// 返り値 : 勝負がついた時点で numEnd[step] をインクリメントして数える
//          ついていない場合は相手側に変えて次の手を探索
// -------------------------------------------------------------------
void search(int emp, int me, int you, int step)
{
  int i;

  if( step == 10 ) numEnd[10]++;
  for( i = 1 ; i < 01000 ; i <<= 1 ) {
    if( !(emp & i) ) continue; // マスが空いてなければ次
    me |= i; // 新しく○(×)を置く
    if( judge(me) ) { // 勝負がついた
      numEnd[step]++;
    } else { // まだ終わらない
      search(emp ^ i, you, me, step + 1); // 次の手を探索
    }
    me ^= i; // 置いた○(×)を除く
  }
}

int main(void)
{
  int i;

  // ゲーム数を数える準備
  for( i = 0 ; i < 10 ; i++ ) numEnd[i] = 0;
  // ひたすら探索
  search(0777, 0, 0, 1);
  // 結果表示(0〜4は実は無用)
  for( i = 0 ; i < 11 ; i++ ) {
    printf("%2d:%7d\n", i, numEnd[i]);
  }

  return 0;
}