朝日新聞2006年10月6日パズル横丁解答

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

た は さ な か あ 
な か あ た は さ 
あ さ は か な た 
か な た あ さ は 
さ た な は あ か 
は あ か さ た な 

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

#include "puzutl.h"

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}
};

YesNo check_ok( int row, int col, int val) // [row][col]に値valを設定できるか?
{
  assert( mat[row][col] == 0);  // 既に別の数字が設定されていたらプログラムに問題あり
  // 同じ行内に同じ数字が無い 
  int           xrow, xcol;
  for( xcol=0; xcol< M; xcol++) {
    if( xcol != col && mat[row][xcol] == val) return    NO;
  }
  // 同じ列内に同じ数字が無い
  for( xrow=0; xrow< M; xrow++) {
    if( xrow != row && mat[xrow][col] == val) return    NO;
  }
  // 3x2内に同じ数字が無い
  int           block_row, block_col;
  block_row     = row / 3 * 3;
  block_col     = col / 2 * 2;
  for( xrow=0; xrow < 3; xrow++) {
    for( xcol=0; xcol< 2; xcol++) {
      if( mat[block_row+xrow][block_col+xcol] == val &&
          !( block_row+xrow == row && block_col+xcol == col)) return    NO;
    }
  }
  // 2x3内に同じ数字が無い
  block_row     = row / 2 * 2;
  block_col     = col / 3 * 3;
  for( xrow=0; xrow < 2; xrow++) {
    for( xcol=0; xcol< 3; xcol++) {
      if( mat[block_row+xrow][block_col+xcol] == val &&
          !( block_row+xrow == row && block_col+xcol == col)) return    NO;
    }
  }
  return    YES;
}

void dump()                     // 結果を出力する
{
  int           row, col;
  for( row=0; row< M; row++) {
    for( col=0; col< M; col++) {
      ps( "%s ", food[mat[row][col]]); // 一応文字で出力する
    }
    ps( "\n");
  }
}

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;
}