6x6のマトリックスがある。以下のルールで升を埋める。
久しぶりのプログラミング問題なのでちょっぴりうれしい。
いわゆる数独(ナンバープレース)の拡張版。ブロックが矩形でなく，対角線もブロックと見なすことが普通の数独と異なる点。
普通の数独の場合9x9サイズは虱潰しで簡単にプログラムできる。それ以上のサイズになると虱潰し方法では時間が掛かりすぎるので一般的な解法を用いる。
今回はサイズが小さいこともあるので虱潰しの方法でやってみる。
まずは升を定義する。配列は1オリジンで利用する。
#define M 6 int d[M+1][M+1];
初期状態は対角線上に数字が並んだ状態。
d[1][1] = 1; d[2][2] = 2; d[3][3] = 3; d[4][4] = 4; d[5][5] = 5; d[6][6] = 6;
肝となるfindコードは以下の通り。
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;
}
}
}
}
数字を配置できるかどうかの判断は以下のような関数を使う。
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;
}
// 対角線上に無いか? row==col の場合はここに来ないはずなので row==M-col の場合だけチェック
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;
}
ブロックと行/列の相互変換が必要になるので，そのためのテーブルを作成する。
cstring blockstr =
"112222"
"111232"
"415533"
"455663"
"445633"
"445666";
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
答えは1件出力された。対角線のチェックをサボると5件出力されてしまう。
解速度
即