ナンプレ(数独)問題作成プログラム その6
わかってたまるかポインター
ナンプレの問題を解くために rows, cols, blocks という配列を constants.c に定義したのだが、これらの配列をまとめて扱いたい時がある。そのために all_lines[] = { rows, cols, blocks}; というように定義したい。どう書いたらいいのか?
ちなみに、constants.h における rows, cols, blocks の宣言は以下のとおり
extern const int rows[LINE_SIZE][LINE_SIZE]; extern const int cols[LINE_SIZE][LINE_SIZE]; extern const int blocks[LINE_SIZE][LINE_SIZE];
つまり今したいことは、const の二次元配列へのポインタの配列である。ごめんなさい、C言語全然わからん。っていうか、こんなの分かってたまるか! 分かる奴は宇宙人だろ。(きっとよく使うから覚えたんだろう)
ロベールのC++教室 - 第10章 続・ポインタ天国 -
を参照してなんとか書きました。
const int (* const all_lines[3])[9] = {rows, cols, blocks};
二番目のconst を入れなくてもgccでwarning 出なかったんだけど、それじゃ const が一個足りないと思ったので追加した。こっちでもwarning 出ない。ぬるいな gcc。(追記:実は間違っていたので修正。)
殺し屋たち その1 kill_single
ナンプレの問題を作成する時であっても、解法アルゴリズムは必要である。特に再帰をしないで(仮定法を使わないで)解ける問題を作るなら。というわけで、解法アルゴリズムを書いていく。一番最初は単純にして必須の関数 kill_single である。候補を減らすという意味でkill_xx とつけた。英語としてはおかしい。kill_by_single とするべきか。要は数字が一個だけのマスがあったら、その行(縦、横、ブロックを含む)内にあるその他のマスからその数字を消すという解法である。ついでにその他の解法もみんなkillで初めて、ヘッダファイル killers.h にプロトタイプ宣言を入れることにした。
int kill_single(sudoku_array * array) { int r; int result = 0; for (int i = 0; i < LINE_KINDS; i++) { for (int j = 0; j < LINE_SIZE; j++) { r = kill_line(all_lines[i][j], array->ar); if (r < 0) { return r; } result += r; } } return result; }
LINE_KINDS は 3と定義されている。rows, cols, blocks で3。ま、kill_line を呼び出しているだけ。(追記:間違っていたので修正した。せっかく作ったall_linesを使っていなかった。)r < 0 は矛盾が発生したとき、あ、でもこれない方がいいな。明日までに取っておくか。で、kill_line はというと
static int kill_line(const int line[], cell_t * ar) { int count = 0; uint16_t syms = 0; for (int i = 0; i < LINE_SIZE; i++) { int idx = line[i]; if (is_single(ar[idx])) { syms |= ar[idx].symbol; } } for (int i = 0; i < LINE_SIZE; i++) { int idx = line[i]; if (is_single(ar[idx])) { continue; } if (ar[idx].symbol & syms) { ar[idx].symbol &= ~syms; count++; } if (ar[idx].symbol == 0) { return -1; } } return count; }
最初のループで行内の single を全部集めてしまい、次のループで行内のsingleでないところから消す。消した個数を数えることは必要。これはいろいろな解法アルゴリズムを簡単な方から適用して候補を減らしていくので、簡単なアルゴリズムで消せなかったときだけ、次のアルゴリズムで消すことになるから。二番目のループの最後のチェックは、全部消えてしまったらエラーというチェックだが、ここでチェックするのは賢くないので明日までに消します。(なぜならば、all_linesを一周すると、同じマスを3回チェックしてしまうから。
ar[idx].symbol &= ~syms;
この部分を少し解説すると、syms でビットが立っているところは、single なマスがある数字だから、それを消したい。
そのためには1のところを0にしてから and をすればいい。if 文に入っていなくても同じ効果があるが、さっきも書いたように実際に消した時だけカウントしたいから。