プログラムの実行結果は以下の通り。
Find DEABC CADEB ECBAD BDECA ABCDE
これを図示すると以下のようになる。
プログラムのソースは以下の通り(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 = "・ABCDE67891011121314151617181920212223242526272829303132333435363738394041424344454647484950"; 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; }