朝日新聞2006年10月6日のパズル横丁問題

問題

「あかさたなは」の6文字を6x6の矩形に以下のルールで配置する。

• どの行を取っても6種類の文字が一つずつ含まれる。
• どの列を取っても6種類の文字が一つずつ含まれる。
• 3x2の大きさになるように6分割したとき，どの分割にも6種類の文字が一つずつ含まれる。
• 2x3の大きさになるように6分割したとき，どの分割にも6種類の文字が一つずつ含まれる。
• 初期状態は以下の通り。

解答への道(ヒント)

ありゃ，先週と似ているぞ。先週は最初にヒューリスティックに行こうと思って大失敗したから今週は再帰でサクッと行きます。

変形の数独って感じかな。初期状態は以下のように定義する。

cstring food[] = {              // 食材
  "??",                         // dummy
  "あ",                         // 1:あわび
  "か",                         // 2:かに
  "さ",                         // 3:さけ
  "た",                         // 4:たい
  "な",                         // 5:なっとう
  "は",                         // 6:はまぐり
};
const int M = 6;
int mat[M][M] = {
  { 0, 0, 3, 0, 0, 0},
  { 0, 2, 0, 4, 0, 0},
  { 1, 0, 0, 0, 5, 0},
  { 0, 5, 0, 0, 0, 6},
  { 0, 0, 5, 0, 1, 0},
  { 0, 0, 0, 3, 0, 0}
};

後は普通に左上から順番に探すだけ。

void find( int pos)             // 矩形の左上から探す
{
  int           row = pos / M;
  int           col = pos % M;
  if( pos >= M*M) {             // 見つかった?
    dump();                     // 見つかったよ
    return;
  }
  if( mat[row][col]) {          // 初期状態の数字?
    find( pos+1);               // 初期状態の数字はチェックせず次へ
    return;
  }
  for( int val=1; val<= M; val++) { // [row][col]に1からMの数字を設定してみる
    if( check_ok( row, col, val)) { // 置けるか?
      mat[row][col] = val;      // 置けた
      find( pos+1);             // 次は右隣に数字を置く
    }
    mat[row][col]   = 0;        // [row][col]に数字は置けなかった
  }
}

int main( int argc, cstring argv[])
{
  find( 0/*pos*/); // 左上から数字を置き始める
  return    0;
}

答えは1件出力されました。

国土交通省のリアルタイムレーダーは良い。私は天気予報は見ないけど，出かける前にはこれを見るようにしている。

天気予報よりずっと判りやすい。人間の脳ってすばらしいな。

太平洋側の海上の雨雲も表示してくれるともっと良いと思う。

解速度

即