ナンプレ（数独）問題作成プログラム　その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では複数解があるかどうかも判定している。