朝日新聞2005年12月2日パズル横丁解答

プログラムの出力結果は以下の通り。2件出力されているが，XとYが逆になっているだけなので実質1件。

X: 2 3 6 7 
Y: 1 4 5 8 10 
X: 1 4 5 8 10 
Y: 2 3 6 7 

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

#include "puzutl.h"

YesNo ok[1024];
int bit[9] = {1,2,4,8,16,32,64,128,256};
int num[9] = {1,2,3,4, 5, 6, 7,  8, 10};

void create_okng()
{
  // 1,2,3,4,5,6,7,8,10 から任意の3個を取り出す場合の組合せと，その組合せで問題ないか事前に調べておく。
  for( int a=0; a< 9; a++) {
    for( int b=a+1; b< 9; b++) {
      for( int c=b+1; c< 9; c++) {
        int v = bit[a]|bit[b]|bit[c]; // 3個を取り出したときの数値
        if( num[c] - num[b] == num[b] - num[a]) ok[v] = NO;
        else                                    ok[v] = YES;
      }
    }
  }
}

YesNo checkOk( int x)
{
  // Boxに入っている数字から任意に3個取り出し差分に問題がないか調べる。
  // 事前にこの組合せがOKかどうか調べておく。
  for( int a=0; a< 9; a++) {
    for( int b=a+1; b< 9; b++) {
      for( int c=b+1; c< 9; c++) {
        int v = bit[a]|bit[b]|bit[c]; // 3個を取り出したときの数値
        if( (x&v) == v) {       // 3個の数値の組合せがなければ調べる意味が無い
          if( ok[v] == NO) return NO; // 事前に調べておいた3個の数字の組合せではダメである
        }
      }
    }
  }
  return YES;
}

int main( int argc, cstring argv[])
{
  create_okng();
  // Box X に入れる組合せは全部で512通りある。
  // Box Y は Box X に入れた数字以外の数字を入れる。
  int X, Y;
  for( int i=0; i< 512; i++) {
    X = i;
    Y = ~X;
    if( checkOk(X) && checkOk(Y)) {
      ps( "X: ");
      for( int i=0; i< 9; i++) {
        if( X&bit[i]) ps( "%d ", num[i]);
      }
      ps( "\nY: ");
      for( i=0; i< 9; i++) {
        if( Y&bit[i]) ps( "%d ", num[i]);
      }
      ps( "\n");
    }
  }
  return    0;
}