朝日新聞2005年8月19日パズル横丁解答

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

Find

ＤＥＡＢＣ
ＣＡＤＥＢ
ＥＣＢＡＤ
ＢＤＥＣＡ
ＡＢＣＤＥ

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

プログラムのソースは以下の通り(2005年1月29日のソースファイルからの変更点を赤字で表示)。

#include "puzutl.h"

#define M 5
int d[M+1][M+1];
cstring blockstr = 
"11112"
"13322"
"33422"
"34444"
"55555";
struct struct_block {
  int m_row[M+1];               // Block内のM個の升の位置
  int m_col[M+1];
  int m_rowidx;                 // データ構築のためのテンポラリ情報(blockstrを解釈する時だけ利用する)
  int m_colidx;
} block2rowcol[M+1];            // block => [row][col]
int rowcol2block[M+1][M+1];     // [row][col] => block
void decideblock( cstring s)
{
  // ブロック定義文字列からブロック構造体を作成する。
  int           iblock;
  for( int irow=1; irow<= M; irow++) {
    for( int icol=1; icol<= M; icol++) {
      iblock    = *s - '0';
      rowcol2block[irow][icol] = iblock;
      block2rowcol[iblock].m_row[block2rowcol[iblock].m_rowidx++] = irow;
      block2rowcol[iblock].m_col[block2rowcol[iblock].m_colidx++] = icol;     
      s++;
    }
  }
}

YesNo checkok( int row, int col, int val) 
{
  // 同じ行内に同じ値が無いか?
  for( int xcol=1; xcol<= M; xcol++) {
    if( d[row][xcol] == val) return NO;
  }
  // 同じ列内に同じ値が無いか?
  for( int xrow=1; xrow<= M; xrow++) {
    if( d[xrow][col] == val) return NO;
  }
  // 対角線上に無いか? 
  if( row == col) {
    for( int k=1; k<= M; k++) {
      if( d[k][k] == val) return NO;
    }
  }
  if( row+col == M+1) {
    for( int k=1; k<= M; k++) {
      if( d[k][M-k+1] == val) return NO;
    }
  }
  // 同じブロック内に同じ値が無いか?
  int iblock = rowcol2block[row][col];
  for( int k=0; k< M; k++) {
    int xrow = block2rowcol[iblock].m_row[k];
    int xcol = block2rowcol[iblock].m_col[k];
    if( d[xrow][xcol] == val) return NO;
  }
  return    YES;
}
void dump()
{
  cstring ss = "・ＡＢＣＤＥ６７８９1011121314151617181920212223242526272829303132333435363738394041424344454647484950";
  int numdecide = 0;
  ps( "\n");
  for( int irow=1; irow <= M; irow++) {
    for( int icol=1; icol <= M; icol++) {
      if( d[irow][icol]) numdecide++;
      ps( "%-.2s", ss+d[irow][icol]*2);
    }
    ps( "\n");
  }
  ps( "\n");
}
void find( int p)
{
  int row = p / M + 1;
  int col = p % M + 1;
  if( p >= M*M) { ps("Find\n"); dump(); return;}
  if( d[row][col]) {
    find( p+1);
  }
  else {
    for( int ival=1; ival<= M; ival++) {
      if( checkok(row,col,ival)) {
        d[row][col] = ival;
        find( p+1);
        d[row][col] = 0;
      }
    }
  }
}
int main( int argc, cstring argv[])
{
  // ブロックを決定する。
  decideblock( blockstr);
  // 問題の初期状態を設定する。
  d[5][1] = 1;
  d[5][2] = 2;
  d[5][3] = 3;
  d[5][4] = 4;
  d[5][5] = 5;
  // 解を探す。
  find( 0);
  return    0;
}