朝日新聞2006年2月17日パズル横丁解答

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

Find
S1 C4 H3 D2 
H2 D3 S4 C1 
D4 H1 C2 S3 
C3 S2 D1 H4 

これを図示すると以下のようになる。

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

#include "puzutl.h"

int type_mask[] = { 0x000F, 0x00F0, 0x0F00, 0xF000};
#define D       0               // ダイヤ
#define H       1               // ハート
#define S       2               // スペード
#define C       3               // クラブ
int no_mask[] = { 1, 2, 4, 8};
#define N1      0               // 1
#define N2      1               // 2
#define N3      2               // 3
#define N4      3               // 4

const int M = 4;
struct mat {                    // structにして関数の引数に指定したときコピーが作成されるようにする
  int m[M][M];
} ma;
int typeno2bit( int type, int no) // カードの種類と数字がどのビットに対応するか?
{
  int bit = no_mask[no];
  bit <<= type*4;
  return bit;
}
int bit2type( int bit)          // ビットがどの種類を示すものか?
{
  for( int i=0; i< 4; i++) {
    if( bit & type_mask[i]) return i;
  }
  pe( "Program Error\n");
  return 0;                     // コンパイルエラーを避けるため適当な値
}
int bit2no( int bit)            // ビットがどの数字を示すものか?
{
  int no = bit | (bit>>4) | (bit>>8) | (bit>>12); // 1ビットしか立っていないことが大前提
  for( int i=0; i< 4; i++) {
    if( no & no_mask[i]) return i; // ビット位置が数字になる
  }
  pe( "Program Error\n");
  return 0;                     // コンパイルエラーを避けるため適当な値
}
void mask_type( mat& m, int Row, int Col, int type) // この位置にこのカードを置けない
{
  m.m[Row][Col] = m.m[Row][Col] & ~type_mask[type];
}
void mask_no( mat& m, int Row, int Col, int no) // この位置にこの数字を置けない
{
  int n = no_mask[no], nomask;
  nomask = (n<<0) | (n<<4) | (n<<8) | (n<<12);
  m.m[Row][Col] = m.m[Row][Col] & ~nomask;
}
YesNo decide1( mat& m, int Row, int Col, int type, int no) // この位置のカードを確定する
{
  int bit = typeno2bit(type,no);
  if( m.m[Row][Col] & bit) {    // この位置に候補としてあるので配置できる
    m.m[Row][Col] = bit;        // この位置のカードをこのカードで確定する,他の候補は消去される
    return    YES;              // 配置できた
  }
  return    NO;                 // 配置できない
}
YesNo decide( mat& m, int Row, int Col, int type, int no) // カードを配置する
{
  // 同じ行,列に同じ種類のカード,同じ値のカードを置けなくする。
  // 対角線上も同じ。
  int irow, icol, i;
  if( !decide1( m, Row, Col, type, no)) { // この位置のカードは確定
    return    NO;               // この位置にカードを配置できなかった。
  }
  for( icol=0; icol< M; icol++) { // 同じ行に置けない
    if( icol != Col) {
      mask_type( m, Row, icol, type);
      mask_no( m, Row, icol, no);
    }
  }
  for( irow=0; irow< M; irow++) { // 同じ列に置けない
    if( irow != Row) {
      mask_type( m, irow, Col, type);
      mask_no( m, irow, Col, no);
    }
  }
  if( Row == Col) {             // 対角上に置けない
    for( i=0; i< M; i++) {
      if( i != Row) {
        mask_type( m, i, i, type);
        mask_no( m, i, i, no);
      }
    }
  }
  if( Row == (M-1-Col)) {         // 対角上に置けない
    for( i=0; i< M; i++) {
      if( i != Row) {
        mask_type( m, i, M-1-i, type);
        mask_no( m, i, M-1-i, no);
      }
    }
  }
  return    YES;
}
void dump( const mat& m)        // 結果を出力する
{
  int irow, icol;
  cstring str_type[] = { "D", "H", "S", "C"};
  for( irow=0; irow< M; irow++) {
    for( icol=0; icol< M; icol++) {
      //ps( "%04x ", m.m[irow][icol]);
      int type = bit2type(m.m[irow][icol]);
      int no = bit2no(m.m[irow][icol]);
      ps( "%s%d ", str_type[type], no+1);
    }
    ps( "\n");
  }
}
void find( mat m, int level)
{
  if( level >= M*M) {
    ps( "Find\n");
    dump(m);
    return;
  }
  int irow, icol;
  irow = level / M;
  icol = level % M;
  int v = m.m[irow][icol];
  int bit = 1;
  for( int i=0; i< 16; i++) {   // 全てのカードをこの位置に配置できるか調べる
    if( v&bit) {                // カードを配置できる
      mat mm = m;
      int type = bit2type(bit);
      int no = bit2no(bit);
      if( decide( mm, irow, icol, type, no)) { // この位置にカードを配置できれば配置する
        find( mm, level+1);
      }
    }
    bit <<= 1;
  }
}
int main( int argc, cstring argv[])
{
  int irow, icol;
  mat ma;
  for( irow=0; irow< M; irow++) {
    for( icol=0; icol< M; icol++) {
      ma.m[irow][icol] = 0xFFFF;    // 全てのカードを配置できる可能性がある。
    }
  }
  decide( ma, 0, 0, S, N1);         // [0,0]にスペードの1を配置
  decide( ma, 0, 3, D, N2);         // [0,3]にダイヤの2を配置
  decide( ma, 2, 2, C, N2);         // [2,2]にクラブの2を配置
  decide( ma, 3, 0, C, N3);         // [3,0]にクラブの3を配置
  find( ma, 0/*探索開始位置*/);
  return    0;
}