ナンプレ（数独）問題作成プログラム その18 convert
ケチケチ作戦
digging hole をやった結果からも分かるように、難しいナンプレの問題はなかなか生成できないのである。貴重な存在なのである。そこで、もし見つかったなら、それを大切にしたいと思うわけだ。貴重なものは大切にしよう。
そういうわけで、問題を変換することにする。同じ解法で解けるが、見た目が違うような問題にするのである。
「ナンプレ練習」製品版では、Locked Candidate は50問、Tuple, X-Wing, Sword Fishは60問、自由練習は100問が組み込まれているが、組み込まれている問題を全部解き終わると以前の問題を変換して再度出題するようになっている。なあに、人間は50問も前の問題は覚えていないはずだ。その上に数字や配置を変更していたら、分からないはずだ。いや、記憶のいい人っているから気づかれるかも。
convert
static void random_symbol(numpl_array * array) これは数字を入れ替える。
static void reverse_change(numpl_array * array, int mode) これは盤面を上下左右対称に変える。（元の盤面は点対称）
static void block_reverse(numpl_array * array, int mode);これはブロックを入れ替える。
static void line_change(numpl_array * array, int mode);これは行、列を入れ替える。
ということをやるわけだ。もうプログラムは面倒だから、GitHubを見てもらう。
で実行すると、
$ ./convert "5 71 3 2 4 9 91 8 6 19 1 5 65 4 8 29 8 6 4 4 16 8" " 56 1 9 7 11 74 9 9 27 2 4 54 7 8 43 25 9 6 1 45 "
こんな風に変換されて全然違う問題に見えるわけである。
念のためにsolveをやってみる。同じ解法で解けるはずである。
$ ./solve -s "5 71 3 2 4 9 91 8 6 19 1 5 65 4 8 29 8 6 4 4 16 8" 213,18,1,0,0,0,0,0,28,1,"5 71 3 2 4 9 91 8 6 19 1 5 65 4 8 29 8 6 4 4 16 8"
変換後は
$ ./solve -s " 56 1 9 7 11 74 9 9 27 2 4 54 7 8 43 25 9 6 1 45 " 216,16,2,0,0,0,0,0,28,1," 56 1 9 7 11 74 9 9 27 2 4 54 7 8 43 25 9 6 1 45 "
違うじゃないか。バグだ。solve のバグか、convertのバグか。なお、このブログはデバッグの過程を眺めて楽しめるようになっています。
たぶん solve のバグだと思う。convert のバグなら解けなくなる可能性が高い。解けている（引用符の前の1が解けたという印）ので solve のバグが疑われる。もし、convert のバグであって、かつ解ける問題が解ける問題に変換されるなんてことがあったら、これは嬉しいことなのである。
白票とランダム投票と部分ランダム投票
白票を投じることと、白票を投じるように他人に勧めること
日本の選挙制度では白票を投じることは無意味だが、白票を投じるように他人に勧めることは無意味ではない。多くの人が白票を投じるならば有利になる政党があるからである。だからこそ、白票を投じることを勧めることは棄権を勧めること同様に問題である。
ランダム投票
そういう言葉があるかどうか知らないけど、要するにサイコロを振って出た目によって候補者を決めて投票する。これは意味がある。しかし、出た目を見た結果、どうしてもこの候補者には投票できない思うことがあるだろう。そうなったら、もう一度サイコロを振ればよいのである。それはインチキでもなんでもなく、極めて正当な候補者選びである。この候補者ならまあ投票してやってもいいという候補者が出るまで、何度でもサイコロを振り直せばよい。これを部分ランダム投票ということにしよう。
白票を投じることを他人に勧めることによって特定の政党・候補者に有利になるから、その行為には問題があると言った。同様に完全にランダムな投票を他人に勧めることによっても、特定の政党・候補者に有利になるはずだ。しかし、部分ランダム投票を他人に勧めることによって、特定の政党・候補者に有利になることはないはずだ。それは除外される候補者が誰になるかは、部分ランダム投票を勧める人には分からないからである。
追記：有利不利
実際には、部分ランダム投票も何らかの意味で有利不利はある。小選挙区制で多数の政党があるなら、票がばらけることによって第一党に有利だとも言える。また、不支持率を反映することになるので不支持率の高い政党に不利となるはずである。
しかし特定の政党や候補者に断固として投票する人は、この投票方法の対象外なので、ここで対称となっている人にとって明らかに不利となる白票を勧めることよりは、部分ランダム投票を勧める方がよいであろう。
ナンプレ（数独）問題作成プログラム その17 digging hole
作ったけど機能してない
digging_hole_recursion 関数を作ったけど、機能していない。つまり、穴を増やせていない。可能性としては、(1)バグ、(2)この関数で穴を増やせる確率が低い、たくさん生成すれば穴を増やせる場合もある、(3)対称性を捨てないといけない。ということだけれど、穴を増やせないなら再帰した意味がないなぁ。
とりあえず、digging_hole_recursion 関数
/** * digging hole アルゴリズムを再帰的に使い問題を作成する * 点対称な問題を作成する。 * 人間的解法で解ける盤面を生成する。 * @param array ナンプレ盤面（入出力） * @return 1: 作成できた * @return それ以外: 作成できなかった */ static int digging_hole_recursion(numpl_array * array, int pos, solve_info * info, int symmetric) { fixed_only(array, FULL_SYMBOL); int r = solve(array, info); if (r != 1) { return r; } numpl_array best = *array; numpl_array save = *array; int min_fixed = ARRAY_SIZE + 1; int loop_size = ARRAY_SIZE; if (symmetric) { loop_size = ARRAY_SIZE / 2; } for (int i = pos; i < loop_size; i++) { int idx1 = i; int idx2 = get_counter(idx1); if (array->ar[idx1].fixed == 0) { continue; } array->ar[idx1].fixed = 0; array->ar[idx1].symbol = FULL_SYMBOL; if (symmetric) { array->ar[idx2].fixed = 0; array->ar[idx2].symbol = FULL_SYMBOL; } r = digging_hole_recursion(array, i + 1, info, symmetric); if (r <= 0) { *array = save; continue; } else if (r == 1) { if (info->fx_count < min_fixed) { min_fixed = info->fx_count; best = *array; } *array = save; } } *array = save; if (min_fixed == ARRAY_SIZE + 1) { return -1; } else { return 1; } }
まあ、頑張ってもそんなには良くならないので、見切りを付けて次に進むべきだろうな。
ナンプレ（数独）問題作成プログラム その16 digging hole
debug
バグはdigging_hole 関数の中の次の行にありました。
int r = solve(&work, &info);
本来は work ではなく array を指定するべきだった。これは workという変数名が悪いので save に変更しました。さらにそれだけでなく、このままだと前回解いた後の状態では開けた所に解が入っているので、新しくあけた穴二つ分だけ解くことになり、必ず解けてしまいます。なので穴は全部穴らしくする必要がある。それがfixed_only、従って上の行を次のように直しました。(work -> save はdigging_hole 関数内で全部置換)
fixed_only(array, FULL_SYMBOL);
int r = solve(array, &info);
これで実行すると、次のような結果になります。
$ ./digging_hole
kill_single:134
kill_hidden:0
kill_locked:0
kill_tuple :0
max_tuple :0
max_hidden :0
swordfish :0
max_fish :0
fx_count :42
solved :1
[1] [3][4][9][6]
[4][5] [2] [9]
[7] [2][5] [4][6]
[2][1][4][7] [9]
[7][6] [9][4]
[9] [2][7][1][3]
[3][4] [7][5] [1]
[8] [1] [5][7]
[8][6][1][3] [4]間違ってはいないんですが、穴が少ないというか数字が多い。なので次の段階としてここから更に穴を掘ることを考えます。ランダムに穴を開けて、解けなかったら終了していたのですが、そうではなく数字があるところ全部について、そこを穴にしても解けるかという判定をすればまだ穴が開けられるはずです。
でも日曜だから頑張らないで次回にまわすのであった。
ナンプレ（数独）問題作成プログラム その15 digging hole
digging hole
まず、完成形の盤面を用意する prepare_array
/** * ナンプレ盤面の完成形を得る。 * ランダムに数字をセットし、再帰的に解く * @param array ナンプレ盤面（出力） * @return 1: 作成できた * @return それ以外: 作成できなかった */ static int prepare_array(numpl_array * array) { for (int i = 0; i < ARRAY_SIZE; i++) { array->ar[i].symbol = FULL_SYMBOL; array->ar[i].fixed = 0; } for (int i = 0; i < 10; i++) { int idx = get_random(ARRAY_SIZE); uint16_t sym = array->ar[idx].symbol; sym = random_one_symbol(sym); if (sym == 0) { continue; } array->ar[idx].symbol = sym; int r = kill_single(array); if (r < 0) { return r; } } return recursion_solve(array); }
random_one_symbol は引数として与えられたビットパターンからひとつだけ1の立っているビットパターンをランダムに返す。ナンプレ的に言うと、与えられた候補数字の中からひとつの候補をランダムに選び出す。先日必要そうなランダム関係関数を作ったのに、その中になかったので追加した。
で、digging holeは
/** * digging hole アルゴリズムにより問題を作成する * 点対称な問題を作成する。 * 人間的解法で解ける盤面を生成する。 * @param array ナンプレ盤面（入出力） * @return 1: 作成できた * @return それ以外: 作成できなかった */ static int digging_hole(numpl_array * array) { for (int i = 0; i < ARRAY_SIZE; i++) { array->ar[i].fixed = 1; } numpl_array work = *array; for (int i = 0; i < ARRAY_SIZE / 2; i++) { int idx1 = get_random(ARRAY_SIZE); int idx2 = get_counter(idx1); if (array->ar[idx1].fixed == 0) { continue; } array->ar[idx1].fixed = 0; array->ar[idx2].fixed = 0; array->ar[idx1].symbol = FULL_SYMBOL; array->ar[idx2].symbol = FULL_SYMBOL; solve_info info; int r = solve(&work, &info); if (r == 0) { *array = work; return 1; } else if (r == 1) { work = *array; } else { *array = work; } } return -1; }
全部fixedにしてから、対称な二点ずつ穴を開けていく。解けなくなったら、一個前の解けたところを盤面として返す。っていう関数なんだけど、どうもバグがあるようだ。solve 呼んで r = 1なら解けたので、その状態を保存し、解けないなら保存された状態を戻してリターンだから、この関数から1が返ったら解ける盤面のはずなんだけどそうならない。
とりあえず、main
#if defined(MAIN) #include <stdio.h> #include <time.h> int main(int argc, char * argv[]) { uint32_t seed = (uint32_t)clock(); xsadd_init(&xsadd, seed); // これを忘れてはならない numpl_array array; int r = 0; do { r = prepare_array(&array); } while (r != 1); #if defined(DEBUG) printf("after prepare_array r = %d", r); output_detail(&array); #endif numpl_array save = array; do { array = save; r = digging_hole(&array); } while (r != 1); #if defined(DEBUG) printf("after digging_hole r = %d", r); output_detail(&array); #endif fixed_only(&array, FULL_SYMBOL); solve_info info; r = solve(&array, &info); print_solve_info(&info, 1); if (r == 1) { fixed_only(&array, 0); output_detail(&array); } else { printf("failure¥n"); output_detail(&array); return -1; } return 0; } #endif
xsadd は最初に呼ばれたときに初期化するとかいう洒落た機能は入っていないので、必ずmainの最初でseedを与えるのだ。
これを実行すると
kill_single:184
kill_hidden:0
kill_locked:0
kill_tuple :0
max_tuple :0
max_hidden :0
swordfish :0
max_fish :0
fx_count :35
solved :0
failure
[1][3][4][2][5][6][7][8][9]
3 3
[5][2][7][8] [1][4][6]
9 9
[6][8][9][1][4][7][2][5][3]
3 3
[2][1][5][4] [6][7][8]
9 9
[4][7][6][5][8][1][9][3][2]
[3][9][8][7][6][2][4][1][5]
[8][6][1][9][7][5][3][2][4]
[7][4][3][6][2][8][5][9][1]
[9][5][2][3][1][4][8][6][7]これは解けてない。デバッグ文入れたけど、今のところバグは取れていない。なお、バグが取れたとしてもまだ問題があるのだがそれは次のステップ。
このブログはデバッグの過程も記述していくという、実践的なプログラミングブログなのである。バグは恥じゃないよ。
そうそう、numpl_array が配列を一個入れただけの構造体になっているのは、save = *array みたいにコピーするため。
ナンプレ（数独）問題作成プログラム その14 疑似乱数
疑似乱数
これから digging hole アルゴリズムでナンプレの問題を作りたいわけだが、そのために疑似乱数を使う。だいたい何でもいいんだけど、比較的新しい（のでお気に入りの）xsadd を使ってみる。小さいし、速いし、MITライセンスだし。
元のソースはXORSHIFT-ADD (XSadd)
にある。
ナンプレで使いそうな疑似乱数関係関数をcommon.cに追加する。また今回は状態空間をグローバルに置く。
xsadd_t xsadd;
あとは関数
/** * 0 から n (含まない) までの数をランダムに生成する * @param n 範囲 * @return 0 から n(含まない)までの数を返す */ int get_random(unsigned int n) { return n * xsadd_float(&xsadd); } /** * ナンプレで使う数字をランダムに生成する * @param symbols ナンプレで使う数字が重複なくランダムな順番でセットされる */ void get_random_symbol(uint16_t symbols[LINE_SIZE]) { uint16_t mask = 1; for (int i = 0; i < LINE_SIZE; i++) { symbols[i] = mask; mask = mask << 1; } for (int i = 0; i < LINE_SIZE; i++) { int r = get_random(LINE_SIZE); uint16_t tmp = symbols[i]; symbols[i] = symbols[r]; symbols[r] = tmp; } } /** * 0 から LINE_SIZE -1までの数をランダムに生成する。 * @param numbers 0 からLINE_SIZE -1 までの数が重複なくセットされる。 */ void get_random_number(uint16_t numbers[LINE_SIZE]) { get_random_number_size(numbers, LINE_SIZE); } /** * 0 から size -1までの数をランダムに生成する。 * @param numbers 0 からsize -1 までの数が重複なくセットされる。 * @param size numbers 配列の大きさ */ void get_random_number_size(uint16_t numbers[], int size) { for (int i = 0; i < size; i++) { numbers[i] = i; } for (int i = 0; i < size; i++) { int r = get_random(size); uint16_t tmp = numbers[i]; numbers[i] = numbers[r]; numbers[r] = tmp; } } /** * 0 から size - 1までの数をランダムに生成する。 * get_random_number_size と同じだが配列の型が違う * @param numbers 0 からsize -1 までの数が重複なくセットされる。 * @param size numbers 配列の大きさ */ void shuffle_int(int array[], int size) { for (int i = 0; i < size; i++) { int r = get_random(size); int tmp = array[i]; array[i] = array[r]; array[r] = tmp; } }
同じような関数がいくつもあって美しくないが、使いやすいということで勘弁。
短いけどこんなもんで。
疑似乱数といえば旧約聖書と言われるコレ
疑似乱数生成器をちょいちょいと作って、卒論や修論にしようと考える情報系の学生ならこれは必読ですよ。凶器にもなるし。
- 作者: Donald E.Knuth,有沢誠,和田英一,斎藤博昭,長尾高弘,松井祥悟,松井孝雄,山内斉
- 出版社/メーカー: アスキー
- 発売日: 2004/10
- メディア: 単行本
- 購入: 1人 クリック: 80回
- この商品を含むブログ (44件) を見る
MSaito/MTToolBox · GitHub
MTToolBox: メインページ
