メニエスの名のもとに

プログラミング関係を中心としたぐだぐだブログ

ナンプレ(数独)問題作成プログラム その7

昨日のプログラムには間違いがあった。

昨日の記事も修正したけどMSaito/NumPl · GitHubの方がたぶん正しい。

矛盾のチェック

昨日の記事でも言っていた矛盾のチェックは、行単位ではない方がいいという件。

static int check_array(sudoku_array * array)
{
    cell_t *ar = array->ar;
    for (int i = 0; i < ARRAY_SIZE; i++) {
        if (ar[i].symbol == 0) {
            return -1;
        }
        set_single_flag(ar[i]);
    }
    return 0;
}

array に対して実行すれば、同じことを3回繰り返さなくて済む。check_arrayは名前が悪いと指摘されそうだが気にしないことにして、kill_single.c のstatic 関数としておく。なお、謎の関数 set_flagはinline_functions.h のis_singleの次の行に空の定義を入れておく。is_singleをフラグを見るように直したら、こっちも中身を書く。

    static inline void set_single_flag(cell_t cell)
    {
    }

Hidden Single

Hidden Single というのは、ひとつの行(縦、横、ブロック)内で、ある数字がひとつのマスにしかないとき、そのマスの他の数字は消せるという解法。
kill_hidden_single は前と同様単に下位の関数を呼び出すだけ。

int kill_hidden_single(sudoku_array * array)
{
    int result = 0;
    for (int i = 0; i < LINE_KINDS; i++) {
        for (int j = 0; j < LINE_SIZE; j++) {
            result += kill_hidden_line(all_lines[i][j], array->ar);
        }
    }
    return result;
}

そして、kill_hidden_line で実務を行う。

static int kill_hidden_line(const int line[], cell_t * ar)
{
    int pos = 0;
    for (uint16_t sym = 1; sym <= MAX_SYMBOL; sym <<= 1) {
	int count = 0;
	for (int i = 0; i < LINE_SIZE; i++) {
	    int idx = line[i];
	    if (ar[idx].symbol == sym) {
		count = 0;
		break;
	    }
	    if (ar[idx].symbol & sym) {
		pos = idx;
		count++;
	    }
	}
	if (count == 1) {
	    ar[pos].symbol = sym;
	    return 1;
	}
    }
    return 0;
}

最初に、数字1は1, 数字2は2,数字3は4,数字4は8というように決めたのであった。従って最初のfor loop は数字を1から9まで変えてループするということ。そして最初のif 文はその数字1個だけのマスだったら次の数字にいく。is_singleで判断するのと同じことだけど。その次のif文はそのマスの候補がその数字を含んでいるなら、場所を覚えてカウンタを上げる。posは次々と更新されるけど、posを参照する時は count が 1の時だけだから、大丈夫。
含むとか含まれないとかいう集合演算をビット演算で出来るというのがポイント。実のところ、問題作成プログラムをC言語で作る理由のひとつがそれなのだ。

アフィ

集合論入門 (ちくま学芸文庫)

集合論入門 (ちくま学芸文庫)

赤 攝也って名前も格好いいけど、年齢もすごい。不死の一族なのか。