メニエスの名のもとに

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

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

念のため

このブログはナンプレ練習 - Google Play の Android アプリ,ナンプレ練習お試し版 - Google Play の Android アプリの問題作成プログラムについて説明しています。
これまでのプログラムはMSaito/NumPl · GitHubにあります。

X-Wing, Sword Fish, ...


X-Wing というのは上の図のようなもの。日本語の数独解説webなどでは四角の対角という名前で解説されていることもあります。ある数字に着目して、それが縦でも横でもいいから二個ならんでいるところが二組あってちょうど四角になっているとする(図では紫の1が縦に2個ずつ並んでいる)。そうすると対角となる二組(左上と右下または左下と右上)どちらかがかならずその数字になるので、はさまれている部分(図では赤の1)が消せるという解法。


Sword Fish は X-Wing の三個版。ただし、ちょうど三個ならんでいる必要はなくて二個でもよい。(上の図では、紫の1が横に2,3,3個並んでいる)Sword Fish で終わりではなく、四個版、五個版というのもあり得るので、あれば発見できるようにプログラムを作る。

int kill_fish(sudoku_array * array)
{
    for (int i = 2; i < 8; i++) {
	for (uint16_t mask = 1; mask <= 0x100; mask = mask << 1) {
	    int count = fishsub(i, mask, rows, array);
	    if (count > 0) {
		return count;
	    }
	    count = fishsub(i, mask, cols, array);
	    if (count > 0) {
		return count;
	    }
	}
    }
    return 0;
}

まず、kill_fishという名前だが、X-Wing よりも Sword Fish に重点を置いて考えるとこういう名前になった。Sword Fish 以後にも魚みたいな名前がついているし。それに、解法があるのは知っているがまだプログラムにしていないものに finned-swordfish とか刺身とかあるので魚なのです。
で、プログラムの最初のループのi=2;i<8というのがその魚の種類で、2ならx-wing,
3ならsword fishを探す。2番目のforループのmask =1; mask <= 0x100というのは
数字を1から9まで変えている。二重ループでは結果的に最初は1のx-wingを、次は2のx-wingを探すということになる。
fishsub が実際の探索をする部分だが、最初のfishsub は横に見て条件成立を探す。二番目のfishsubは縦に見て条件成立を探す。

static int fishsub(int fish_count, uint16_t mask,
		 const int rows[LINE_SIZE][LINE_SIZE],
		 numpl_array * array)
{
    uint16_t mat[LINE_SIZE];
    make_mat(mask, mat, rows, array);
    int count1 = 0;
    int count2 = 0;
    uint16_t patterns[LINE_SIZE * LINE_SIZE];
    int p = 0;
    for (int i = 0; i < LINE_SIZE; i++) {
	int c1 = 0;
	int c2 = 0;
	for (int j = 0; j < LINE_SIZE; j++) {
	    c1 += (mat[i] >> j) & 1;
	    c2 += (mat[j] >> i) & 1;
	}
	if (c1 >= 2 && c1 <= fish_count) {
	    count1++;
	    patterns[p++] = mat[i];
	}
	if (c2 >= 2) {
	    count2++;
	}
    }
    if (count1 < fish_count) {
	return 0;
    }
    if (count2 < fish_count) {
	return 0;
    }
    adjust_patterns(fish_count, patterns, p, LINE_SIZE * LINE_SIZE);
    for (int i = 0; i < LINE_SIZE * LINE_SIZE; i++) {
	uint16_t pat = patterns[i];
	if (pat == UINT16_C(0xffff)) {
	    continue;
	}
	int count = 0;
	for (int j = 0; j < LINE_SIZE; j++) {
	    if ((mat[j] | pat) == pat) {
		count++;
	    }
	}
	if (count == fish_count) {
	    int result = kill_fish_cells(mask, pat, mat, rows, array);
	    if (result > 0) {
		return 1;
	    }
	}
    }
    return 0;
}

長くてややこしい。make_mat というのはビットマトリクスを作る関数である。
このfishsubに来たときは探す数字が決まっているので、その数字のあるところだけを1にしたビットマトリクスを作っている。ビットの二次元配列だがuint16_tに1次元分入れることができる。このmatという配列の中からx-wingやらsword fishやらを探すわけだ。
この最初のループはいくつかのことを同時にやっているので、説明が面倒だ。というか、思い出せない。該当しそうな列はpatternに入る。count1, count2は縦とか横とかに数えて明らかに該当しない時に終了している。
そうするとpatternに部分パターンも含めて入る。それを調整するのがadjust_patterns。例えば前のsword fish の図だとハイライト行の紫の1のパターンは左からだとすると 101000000, 101000010, 101000010がpatternに入るが、これを 101000010 のパターンと見なしたい。組み合わせが増えることもある。101000000, 001000010, 100000010, なんていう風に並んでいるときもある。これも上と同じように101000010というパターンとして見なしたい。
kill_fish_cells はパターンとして条件を満たしている時に、それよって消せる数があれば消して、消した数を返す。消せたら終了だが、消せなければ次のパターンを試す。

今日の音楽

音楽というか、STEINS;GATEはいい。オカリンのキャラがいい。

Hacking to the Gate

Hacking to the Gate

STEINS;GATE

STEINS;GATE