朝日新聞2005年4月8日のパズル横丁問題

問題

5人の人間ABCDEがいる。正直者と嘘つきのどちらかである。ABCDEは以下のように右,左,左,正面,左を向いている。

正直者は左右どちらにでも,嘘つきのいる方向を向く。左右どちらにも嘘つきがいなければ正面を向く。嘘つきは常に嘘をつき,行動も不正直です。

正直者が向いた方向の先には少なくとも一人,嘘つきがいます。

解答への道(ヒント)

ありゃ何かやったことのあるような問題。去年の4月24日の問題が正直者と嘘つきを見分ける問題だった。去年も4月だったし,もしかしてエイプリルフール用に作成した問題なのかも知れないなー。

去年はプログラムを作って解いたので今年も迷わずプログラム作成じゃ。

5人しかいないのに問題レベルが星2つだ。

「嘘つきは常に嘘をつき,行動も不正直です」ってのがどういうことか判りにくいからかも知れない。私の感覚だと「嘘つきの言うことは信じられない」なんだけど,クイズ問題だと「嘘つきの言うことは偽(ぎ)である」という場合が殆ど。嘘つきネタはパラドックスなんかでも使われており,頭で考えると訳が判らなくなってしまうことが多い。実は問題のレベルが上がっているのは,正直者の左右に嘘つきがいる場合,正直者はどちらを向いても良いというところなのかな(プログラムで解いちゃったら頭で考えようなんて思わない,検算はするけどね)。

5人しかおらず,正直者と嘘つきの場合しかないので,全部で25で僅か32通り。

A ⇒ 0ビット目
B ⇒ 1ビット目
C ⇒ 2ビット目
D ⇒ 3ビット目
E ⇒ 4ビット目

上記の割り当てで,ビットがONの場合嘘つきと見なす。そうすると全ての場合を虱潰すには以下のようなコードになる。

  for( int sts=0; sts< 32; sts++) {
    if( check( sts)) dump(sts);
  }

check( )はstsで指定した状態が,問題の状態と矛盾がなければYESを返し,矛盾があればNOを返す。

dump( )はABCDEが嘘つきか正直者かを出力する。

これで骨格になる部分は完成。

dump( )は以下のようになる。

void dump( int sts) 
{
  for( int i=0; i< 5; i++) {
    ps( "%c : ", "ABCDE"[i]);
    if( sts&1) ps( "嘘つき"); else ps( "正直者");
    ps( "\n");
    sts >>= 1;
  }
}

check( )は以下のように5人の向きの可能性を調べ(向きは一意に決まらず複数出現する可能性がある),矛盾があればそこで終了する。

const int LEFT  = 1;
const int RIGHT = 2;
const int NONE  = 4;

int direction0[5] = { RIGHT/*A*/, LEFT/*B*/, LEFT/*C*/, NONE/*D*/, LEFT/*E*/}; // 問題文にあるA〜Eの向き

YesNo check( int sts) 
{
  // Bitが1:嘘つき,0:正直
  int direction[5];             // 5人の向き
  for( int k=0; k< 5; k++) { // 5人
    direction[k] = getdirection( sts, k);
  }
  for( k=0; k< 5; k++) {
    if( !(direction[k] & direction0[k])) return NO;
  }
  return    YES;
}

後は可能性のある向きを返すgetdirection( )を完成すれば完璧。

結果は1件出力されました。但し,問題文にある「正直者が向いた方向の先には少なくとも一人,嘘つきがいます」をコーディングしていない。この条件は何を意味するんだろう。頭で考えると何か引っかかることがあるのかな?正直者は嘘つきのいる方向を向くって書いてあるから,何もこのような記述はいらないと思うんだけど。よく判らない。

結果を見て正しいことを確認しようとしたがやはり頭で考えると判りづらい。正直者は良いけど,嘘つきの対応が...

ルールを記述してプログラムを実行すると勝手に答えが出てくるのがプログラミングの良いところ。こういう問題はプログラムに任せた方が安心。AIとか興味のある人は,こういう問題好きかも。

新聞の問題を切り取って保存するようにしているんだけど,パズルパークの時はちょうど葉書サイズで良かったけど,パズル横丁は横長で保存には向かない。だけど保存しているけどね。

解速度