ナンプレ（数独）問題作成プログラム その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 みたいにコピーするため。
