2014-11-26

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

前回のプログラムを実行出来るように solve.c の main を変更する。

たいした変更じゃないのでMSaito/NumPl · GitHubを見て。
で、実行すると、

./solve -r "  6 31 9   9   427 7         1  6     7   8     5  2         5 143   9   8 24 61 "
quiet = 0
recursion = 1
argc = 1
??6?31?9?
??9???427
?7???????
??1??6???
??7???8??
???5??2??
???????5?
143???9??
?8?24?61?
has more than 2 solution
??6?31?9?
??9???427
?7???????
??1??6???
??7???8??
???5??2??
???????5?
143???9??
?8?24?61?
426731598
319865427
578492136
251976345
937124861
864583279
692318754
143657982
785249613

とかいう結果が出ておかしい。困ったことに、recursion_solve がおかしいという可能性と、これまでのsolveがおかしいという可能性がある。だが、上の出力をじっと見つめると、

864583279

という行があり、8が2回出てくるので間違い。つまり、recursion_solveに問題があることは間違いない。そこでいろいろ調べたりするのだが、実は今回このブログで発表するためにかっこよく変更した部分があって、そこのバグなのであった。
それは、kill_single.c の kill_line 関数である。forループを２回まわるだけで行内のsingleを消せるという部分である。その最初のforループ

    for (int i = 0; i < LINE_SIZE; i++) {
	int idx = line[i];
	if (is_single(ar[idx])) {
	    syms |= ar[idx].symbol;
	}
    }

上のプログラムだと、さっきのように行内に8が二つあるような場合でも、そのまま見過ごしてしまう。そこで次のように変更すると同じ数字が二つある場合にチェックできる。（count の使い回しが気になるが、count していることは確かなので別の変数を取る必要はないかなと思う）

    for (int i = 0; i < LINE_SIZE; i++) {
	int idx = line[i];
	if (is_single(ar[idx])) {
	    syms |= ar[idx].symbol;
	    count++;
	}
    }
    if (count != ones16(syms)) {
	return -1;
    }
    count = 0;

もうひとつの問題点は、recursion_solve が解を返さないことなので、解を返すように修正。実行すると、

$ ./solve -r "  6 31 9   9   427 7         1  6     7   8     5  2         5 143   9   8 24 61 "
quiet = 0
recursion = 1
argc = 1
??6?31?9?
??9???427
?7???????
??1??6???
??7???8??
???5??2??
???????5?
143???9??
?8?24?61?
solved
426731598
319865427
578924136
251486379
637192845
894573261
962318754
143657982
785249613

となる。これでrecursion_solveの動作は確認できた。（本当はもっとテストするべきだけど）

ヤング図形を求めるプログラムを載せようとしてやめた

いや、別のプログラムを載せると、別の人が検索してやってくるかもと思ったのだが、ヤング図形のプログラムで検索した結果、私のプログラムよりスマートらしく見えるプログラムがあったので掲載をやめたのだ。

ヤング図形のはなし (日評数学選書)

作者: 寺田至
出版社/メーカー: 日本評論社
発売日: 2002/08
メディア: 単行本
クリック: 4回
この商品を含むブログ (1件) を見る

2014-11-25

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

ナンプレ数独プログラム

バグ修正

前回のバグはつまらないところにありました。バグってのはたいていつまらないところにあるもんです。

       if ((mask & multiple) != multiple) {
            continue;
        }

これ、multiple の中に mask が含まれるかという判定をしていたのです。
もう集合演算はビット演算でばっちりだぜ！とかいい気になっていたのが悪い。
本当は、こっち。ANDじゃなくてORですよ。

       if ((mask | multiple) != multiple) {

な、情けない。

digging hole アルゴリズム

で、いよいよナンプレ問題の生成となる訳ですが、基本のアルゴリズムはdigging hole と呼ばれています。これはナンプレの完成図があれば、つまり数字が全部つまったナンプレの図があれば、そこからひとつずつ穴を開けていけば必ず解けるナンプレが作れるという考えです。
そのためにはナンプレの完成図が必要な訳ですが、これは比較的簡単に生成できます。それには、ナンプレを解くプログラム（いろいろなところにあります）でよく使われる再帰的解法を使えばよいのです。目標は人間が解く方法で解けるナンプレ問題を作ることですが、その過程で機械的な解法を使います。最初に空白の盤面に適当にバラバラに数字を置いて、それを再帰的解法で解くとdigging holeで使うためのナンプレ完成図が得られるということです。
それなので、再帰的解法のプログラムを作ります。

static const int max_simple_solvers = 2;
/** 機械的解放関数 */
static solver_t simple_solvers[] = {
    kill_single,
    kill_hidden_single,
    NULL};
/**
 * 機械的解法（kill_single, kill_hidden_single)を繰り返し
 * 使用してナンプレを解こうとする。
 * @param array ナンプレ盤面配列
 * @return -1 矛盾があって解けない
 * @return 0 これ以上機械的解法では解けない
 * @return 1 解けた
 */
int simple_solve(numpl_array * array)
{
    int r = 0;
    do {
        for (int i = 0; i < max_simple_solvers && solvers[i] != NULL; i++) {
            r = simple_solvers[i](array);
            if (r < 0) {
                return -1;
            }
            if (r > 0) {
                break;
            }
        }
    } while (r != 0);
    return r;
}

/**
 * 二つのナンプレ盤面配列が等しいか調べる
 * @param a ナンプレ盤面配列1
 * @param b ナンプレ盤面配列2
 * @return 1 等しい
 * @return 0 等しくない
 */
int equal(const numpl_array * a, const numpl_array * b)
{
    for (int i = 0; i < ARRAY_SIZE; i++) {
        if (a->ar[i].symbol != b->ar[i].symbol ||
            a->ar[i].fixed != b->ar[i].fixed ||
            is_single(a->ar[i]) != is_single(b->ar[i])) {
            return 0;
        }
    }
    return 1;
}
/**
 * 再帰的解法
 * 人間的な解法アルゴリズムは使わずに機械的解法で解く
 * 機械的解法で解けないときは、複数候補のあるマスの候補から一つ選んで解けるか試
す
 * ということを再帰的に実行する。
 * また、解が複数あるかどうかもチェックする。
 * @param array ナンプレ盤面配列
 * @param data 再帰用持ち回しデータ
 * @return -1 矛盾があって解けない
 * @return 1 解けた
 * @return 2 解が複数存在する。
 */
int recursion_solve(const numpl_array * array, recursion_solve_t *data)
{
    numpl_array work;
    work = *array;
    int solved = simple_solve(&work);
    if (solved < 0) {
        return solved;
    }
    solved = is_solved(&work);
    if (solved == 1) {
        if (!data->saved) {
            data->save = work;
            data->saved = 1;
        } else if (!equal(&data->save, &work)) {
            solved = 2;
        }
    }
    if (solved != 0) {
        return solved;
    }
    int result = -1;
    for (int i = 0; i < ARRAY_SIZE; i++) {
        if (is_single(work.ar[i])) {
            continue;
        }
        cell_t s = work.ar[i];
        for (int j = 0; j < LINE_SIZE; j++) {
            work.ar[i] = s;
            unsigned int mask = s.symbol & (1 << j);
            if (!mask) {
                continue;
            }
            work.ar[i].symbol = mask;
            solved = recursion_solve(&work, data);
            if (solved > 1) {
                return solved;
            } else if (solved == 1) {
                result = 1;
            }
        }
        break;
    }
    return result;
}

再帰はプログラミングの基本アルゴリズムだが、構造的プログラミングを先に学んでしまうとなかなかとっつきが悪かったりする。しかし、パズルファンなら再帰的な思考法には慣れているはずだ。ナンプレの用語でいえば仮定法。ひとつの手を仮定してその先の盤面を考える。そしてダメなら仮定を棄却する。ということを一つ先の盤面でもやるのである。
ここで少しだけ注意する必要があるのは、ナンプレの問題は一つの問題にひつだけの解があるように作らなければならないということである。単純に再帰的な方法を使うと複数の解が存在することがある。（ただし、digging holeで使う分には問題ない）このrecursion_solveでは複数解があるかどうかも判定している。

連休はゲームしてた

ゲーム理論の概略はブルーバックスでいいんじゃないの。

ゲームの理論入門―チェスから核戦略まで (ブルーバックス)

作者: モートン.D・デービス,桐谷維,森克美
出版社/メーカー: 講談社
発売日: 1973/09/30
メディア: 新書
購入: 1人クリック: 4回
この商品を含むブログ (6件) を見る

2014-11-23

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

ナンプレ数独プログラム

solve.c

/** 候補を減らす関数タイプ */
typedef int (*solver_t)(numpl_array *);

/** 関数の数 */
static const int max_solvers = 5;

/** 関数 */
static solver_t solvers[] = {
    kill_single,
    kill_hidden_single,
    kill_locked_candidate,
    kill_tuple,
    kill_fish,
    NULL};

/**
 * 人間がナンプレを解くときの手法を使って解く
 * どの手法を使ったかをinfo に記録する。
 * @param array ナンプレ盤面配列
 * @param info どの解法を使ったかを記録する
 * @return 1 解けた
 * @return 0 解けていない
 * @return -1 矛盾が発生していて解けない
 */
int solve(numpl_array * array, solve_info * info)
{
    info->ks_count = 0;
    info->kh_count = 0;
    info->kt_count = 0;
    info->kl_count = 0;
    info->sf_count = 0;
    info->fx_count = 0;
    info->solved = 0;
    int c = 0;
    do {
	for (int i = 0; i < max_solvers; i++) {
	    if (solvers[i] == NULL) {
		break;
	    }
	    c = solvers[i](array);
	    if (c > 0) {
		set_info(info, c, solvers[i]);
		break;
	    }
	    if (c < 0) {
		break;
	    }
	}
    } while (c > 0);
    if (c < 0) {
	info->solved = 0;
    } else {
	if (is_solved(array)) {
	    info->solved = 1;
	} else {
	    info->solved = 0;
	}
    }
    info->fx_count = count_fixed(array);
    if (c < 0) {
	return -1;
    } else {
	return info->solved;
    }
}

ここには挙げていないset_info の中身が美しくない。make して実行する。locked candidate は大丈夫。

./solve "5 71    3 2  4   9 91  8     6 19    1     5    65 4     8  29 8   6  4 4    16 8"
solved
547196823
628345719
391278564
756419382
214783956
983652471
165834297
832967145
479521638
kill_single:213
kill_hidden:18
kill_locked:1
kill_tuple :0
max_tuple  :0
max_hidden :0
swordfish  :0
max_fish   :0
fx_count   :28
solved     :1

次は tuple

./solve "  24     1 7 3 6 4 3   1    74 8  6           5  2 98    2   9 9 3 4 826     95  "
                  1 31 31 3
 56  6[2][4] 5  56
 8  8       7 97         89

[1][9][7][8][3][2][6][5][4]


[4][3] 56 56 5 [1][2][7]
       8      9          89
 23              31 3   123
   [7][4][9][8] 5    [6] 5

 23 2            3  3  3 23
  6  6[9][1] 5  564  4   5
 8  8       7  7  7     7
  3                       3
  6[5][1]  6[2][4][9][8]
         7              7
            1     1 3   1 3
 564 6 56[2]  6[8]4  [9]
7                 7     7

[9][1][3] 5 [4] 5 [8][2][6]
         7     7
 2  2       1        1  1
  64 6  6[3]  6[9][5]4
78  8  8                7
kill_single:170
kill_hidden:9
kill_locked:3
kill_tuple :0
max_tuple  :0
max_hidden :0
swordfish  :0
max_fish   :0
fx_count   :27
solved     :0

ダメじゃん。動いているプログラムを書き直しているだけなんだけど、動作がおかしい。こういうことは珍しくないのだ。しかし１行目にNaked Pair があるからわかりやすいぞ。でも日曜だからデバッグはまたあとでやろう。

ディスガイア４

昨日今日とふと思い出してディスガイア４をやっていた。なんで急にディスガイアを思い出したのか考えてみたら、これは選挙がテーマになっていたのだな。バールソードを1から逆海賊までアイテム界で鍛え上げるだけの作業ですよ。なんという人生の無駄でしょうか。まあ、無駄でないことなどそう多くはないけど。

魔界戦記ディスガイア4(通常版)

出版社/メーカー: 日本一ソフトウェア
発売日: 2011/02/24
メディア: Video Game
購入: 3人クリック: 38回
この商品を含むブログ (23件) を見る

魔界戦記ディスガイア5 初回限定版初回限定特典ゲーム内で使用できるプロダクトコード「着せ替えセラフィーヌ(バニーガールVer.)」付

出版社/メーカー: 日本一ソフトウェア
発売日: 2015/03/26
メディア: Video Game
この商品を含むブログ (3件) を見る

2014-11-21

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

ナンプレ数独プログラム

doxygen

一度Javaをやった人間は javadoc のようなドキュメントがないとなんとなく不安になる。Doxygen: Main Pageはjavadocのようなことをいくつかの言語を対象にやってくれるソフトである。
これまでのアルゴリズムを使って問題を解くプログラム solve.c を書き、solve.c 以外の .c ファイルにdoxygenコメントをつけた。そのファイルはMSaito/NumPl · GitHubにある。コメント付けるだけで疲れ果てた。かなりいい加減なコメントなのに。いや、まだ solve.c にコメントつけてない。
doxygen のコメントはヘッダファイルの関数宣言につけるべきか、それとも.cファイルの関数定義につけるべきかと考えると、通常ならば見られる可能性の高いヘッダファイルに付けた方がよいと思う。しかし、今回はプログラムの解説をしているので、プログラムを読む人の立場を考えて .c ファイルにつけた。まだ doxygen はかけていないので、エラーもあるはず。
solve は make solve でコンパイルできる。しかし、実行していない。実行してしまうと、コメントを付けるより先にバグを取ろうとしてしまうから。そうなるといつまでたってもコメントが付けられない。

バグ

昨日書かなかったけれど、ナンプレ練習にバグがあり修正した。

解散総選挙

選挙はナンプレ（数独）に似ている。あるマスに入る候補となる数字を減らしていくことが重要。つまり、落としたい候補者を次々と選んでいくことが重要。最後に残った候補で確定。

読んでいる本

「巨獣めざめる」面白い。けどなかなか読む時間が作れない。
巨獣めざめる (上) (ハヤカワ文庫SF)
巨獣めざめる　（上）

2014-11-20

1時間程度では無理だった。

数独問題作成プログラム、これまでに作った解法を試すために問題を解くプログラムを作ろうと思ったが、既にあるプログラムが錯綜しているために１時間程度では整理できなかった。この際、コメントも入れるので、プログラムを上げるのは明日以降にする。
スパゲッティというよりも、似たようなことをする関数がいくつもあるんだよね。少し違う動作をさせたいときに、これまでの動作を壊すのがいやなので新しく作ってしまうと言う悪い癖。仕事じゃやらないけど、趣味的に急いで作るときにはついやってしまう。
まあ、このブログを書く目的の一つはそういうのを整理するというのもある。

昨日ブログを休んだのは、漫画を読んでいたから。なんと、32巻を買っていなかったことも判明した。

ベイビーステップ(33) (講談社コミックス)

作者: 勝木光
出版社/メーカー: 講談社
発売日: 2014/11/17
メディア: コミック
この商品を含むブログ (2件) を見る

ベイビーステップ(32) (講談社コミックス)

作者: 勝木光
出版社/メーカー: 講談社
発売日: 2014/08/16
メディア: コミック
この商品を含むブログ (3件) を見る

2014-11-18

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

ナンプレ数独プログラム

念のため

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

X-Wing, Sword Fish, ...

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

Sword Fish は X-Wing の三個版。ただし、ちょうど三個ならんでいる必要はなくて二個でもよい。（上の図では、紫の１が横に２，３，３個並んでいる）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を探す。２番目の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に１次元分入れることができる。この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 はパターンとして条件を満たしている時に、それよって消せる数があれば消して、消した数を返す。消せたら終了だが、消せなければ次のパターンを試す。