朝日新聞2004年4月24日のパズルパーク問題

問題

A〜Hの8人が一列に並んでいる。8人に「あなたの左側と右側で正直者の数は同数ですか?」と尋ねる。正直者は正直に答え，嘘つきは反対に答える。

A,C,E,Gが「はい」，B,D,F,Hが「いいえ」と答えたとき，A〜Hの誰が嘘つきで，誰が正直者か判断する。

解答への考え方

全部で8人いるので，正直者と嘘つき全ての組合せは2⁸(=256)通りしかない。全部の場合を調べるのは簡単である。よって全部の場合を調べるプログラムを作成する。

コードは以下のようになる。

for( i=0; i< 256; i++) {
  8ビットの各ビットが1:正直者,0:嘘つきとみなし問題と矛盾が無いか調べる( i); // 矛盾がなければそれが解である
}


8ビットの各ビットが1:正直者,0:嘘つきとみなし問題と矛盾が無いか調べる( int i)
{
  int man[8]; // 1:正直者,0:嘘つき
  int samenum[8]; // 1:左右で正直者が同数,0:左右で正直者が同数でない
  int res[8]; // なんと答えるか,1:はい,0:いいえ
  8ビットの各ビットが1:正直者,0:嘘つきとみなし8人が正直者,嘘つきなのか調べる(man[]を設定)。
  それぞれの人の左右で正直者の数と嘘つきの数を調べる(samenum[]を設定)。
  それぞれの人が正直なら正直に答え，嘘つきなら逆に答えたとしてどう答えるかを調べる(res[]を設定)。
  問題と答えが一致するか調べる。一致すればその時の状態が正直者と嘘つきの組合せになる。
}

解速度

即