ナンプレ（数独）問題作成プログラム　その９

tuple (二国同盟、三国同盟、裏二国同盟、……）

ひとつの行（縦、横、ブロック）に注目する。その行内に、二つの数字だけで二カ所のマスを埋めていたり、三つの数字だけで三カ所のマスを埋めていたりしたら、それ以外のマスには、その数字は入らない。
図の例でいうと34で二つのマスを使っているので、それ以外のマスの34は消せるというわけです。なお、この34は同じブロックでもあるので、中段右ブロックからも34が消せます。
裏二国同盟というのは、二つの数字が二カ所のマスにだけ存在するなら、その二つのマスにある他の数字は消せるというもの。
実は問題作成時には裏とか表とか気にしなくもいい。
プログラムは、例によって呼び出すだけの関数。

int kill_tuple(numpl_array * array)
{
    int c = 0;
    for (int i = 0; i < LINE_KINDS; i++) {
	for (int j = 0; j < LINE_SIZE; j++) {
	    c = kill_tuple_lines(all_lines[i][j], array->ar);
	    if (c > 0) {
		return 1;
	    }
	}
    }
    return 0;
}

そして、実際の処理を行うのは、

static int kill_tuple_lines(const int line[], cell_t array[])
{
    uint16_t multiple = count_multiple(line, array);
    if (ones16(multiple) <= 2) {
	return 0;
    }
    for (uint16_t mask = 3; mask < FULL_SYMBOL; mask++) {
	if ((mask & multiple) != multiple) {
	    continue;
	}
	int count = ones16(mask);
	if (count <= 1 || count >= 8) {
	    continue;
	}
	int cells = count_naked_cells(mask, line, array);
	if (cells == count) {
	    int result = kill_naked_cells(mask, line, array);
	    if (result > 0) {
		return 1;
	    }
	}
    }
    return 0;
}

ここで重要なのはfor文。1から9までの数字のすべての組み合わせを生成している。各数字が1ビットで表されているので、カウントアップすると全ての組み合わせが得られるのである。（やってはいけないこと：数字のリストを使ってそこから全ての組み合わせのリストを生成するようなことは頭がこんがらがる上に実行時間もメモリも馬鹿にならない。労多くして功少なし）
次の関数は、確定していないマスが2個以内だったら、消すものがないのでその行はスキップする。そのために空いているマスの数を数える……というつもりで作ったが、実は確定していないマスで使う数字を全部集めてくる方がいいと気づいて内容を修正したもの。
上の関数内で (mask & multiple) != multiple というのがその利用法で、生成した数字の組み合わせが、確定してないマスに残っている数字にすっぽり含まれている必要がある。そうでなければ次の組み合わせを生成する。

static uint16_t count_multiple(const int line[], cell_t array[])
{
    int mask = 0;
    for (int i = 0; i < LINE_SIZE; i++) {
	int ind = line[i];
	if (!is_single(array[ind])) {
	    mask |= array[ind].symbol;
	}
    }
    return mask;
}

あとはもう組み合わせた数字の個数とその組み合わせだけからなるマスの個数が
等しければ、残りのマスから削除するだけ。

static int count_naked_cells(uint16_t mask, const int line[], cell_t array[])
{
    int count = 0;
    for (int i = 0; i < LINE_SIZE; i++) {
	cell_t sym = array[line[i]];
	if ((sym.symbol | mask) == mask) {
	    count++;
	}
    }
    return count;
}

static int kill_naked_cells(uint16_t mask, const int line[], cell_t array[])
{
    int count = 0;
    for (int i = 0; i < LINE_SIZE; i++) {
	cell_t sym = array[line[i]];
	if ((sym.symbol | mask) != mask &&
	    (sym.symbol & mask) != 0) {
	    array[line[i]].symbol = sym.symbol & (~mask);
	    count++;
	}
    }
    return count;
}