朝日新聞2006年6月23日パズル横丁解答

プログラムの実行結果は以下の通り。

正直者の数が 5 人の場合

正直者が5人，嘘つきが5人の場合，どんな並びになっていても，他の人数の組み合わせの回答と一致する場合はない。

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

#include "puzutl.h"

map<string,int> pattern;        // 答えのパターンと正直者の数(-1の場合,正直者の数は特定できなかった)
YesNo unknown[11];              // YES:正直者の数が特定できない,NO:正直者の数は特定できている

void ans( int user)
{
  char ans[9+1/*NIL*/];         // 9人の質問の答え, Y:はい, N:いいえ
  YesNo         honest;         // 答える人は正直者?
  int           num_honest = 0; // 10人中の正直者の数
  for( int i=0; i< 9; i++) {    // 先頭から9人に答えを聞く
    honest      = user&1;       // 次に答える人は正直者?
    if( honest) num_honest++;   // 正直者の数を勘定する
    user        >>= 1;          // 次の人
    if( honest) {
      // 正直者は「次の人は嘘つきか？」に対し正しく答える
      if( user&1) ans[i] = 'N'; // 次の人は正直者
      else        ans[i] = 'Y'; // 次の人は嘘つき
    }
    else {
      // 嘘つき,逆を答える
      if( user&1) ans[i] = 'Y'; // 次の人は正直者
      else        ans[i] = 'N'; // 次の人は嘘つき
    }
  }
  if( user&1) num_honest++;     // 10番目の人は正直者?
  ans[i]        = NIL;          // 質問の答えをASCIZにする
  map<string,int>::iterator ite = pattern.find( ans);
  if( ite == pattern.end()) {
    // 初めて出現する答えのパターン
    pattern.insert( pair<string,int>(ans, num_honest));
  }
  else {
    // 既に出現した答えのパターン
    if( (*ite).second != num_honest) {
      // 前回と答えのパターンが同じなのに正直者の数が異なる。
      // ということはこのパターンでは正直者の数を確定できない。
      unknown[(*ite).second]= YES;
      unknown[num_honest]   = YES;
      (*ite).second = -1;       // 特定できない
    }
  }
}

int main( int argc, cstring argv[])
{
  // 10人分の全てのパターンを洗い出す
  for( int user=0; user< 1024; user++) {
    ans( user);
  }
  // 正直者の数が0〜10までの可能性があるので調べてみる。
  for( int i=0; i<= 10; i++) {
    if( unknown[i] == NO) ps( "正直者の数が %d 人の場合\n", i); // 正直者の数が特定できる場合
  }
  return    0;
}