バックトラック（続き）

１２月５日水曜日、晴れ

帰宅後、昨晩書いていたバックトラックのコードを手直し。

Reorder code. · ryohji/sudoku-backtrack@ac52282

左上から順に愚直に埋めていくという流れは変えていない。
Visual Studio Code のコード整形がアグレッシブに改行を入れてくるので（開き波括弧を改行されるのは僕の美意識に反していてかなり辛い）、これに逆らってどれくらい行数を減らせるかのチャレンジ。

甲斐あって２００行切った。

また main から、利用する順に関数を並べ直した。

int main(int argn, const char **args)
{
    uint16_t cells[N];

    init("*6*41*83*"
         "7**8*****"
         "5*19*****"
         "*******7*"
         "6*9***5*4"
         "*1*******"
         "*****47*9"
         "*****8**1"
         "*78*39*6*",
         cells);
    solve(cells);

    return 0;
}

初期化して、それを解くんだな、ということが見える。（といいな……）

cells は長さ 81 の配列で、各要素は低位ビットから順に１、２、３、……と、そのマスに置くことができそうな数字の候補を記録している。数字が確定した要素はいずれか１ビットだけ立っている。

肝心の solve の定義はこう。

bool ok(uint16_t *cells);
uint16_t *next(uint16_t *cells);
void dump(const uint16_t *cells);

void solve(uint16_t *cells)
{
    if (ok(cells))
    {
        uint16_t *const p = next(cells);
        if (p != cells + N)
        {
            const uint16_t original = *p; // memory candidates
            const uint16_t *it;
            for (it = bits; it != bits + 9; it += 1)
            {
                if (original & *it)
                {
                    *p = *it; // subvert cell by candidate
                    solve(cells);
                }
            }
            *p = original; // revert to backtrack
        }
        else
        {
            dump(cells);
        }
    }
}

冒頭で制約を満たしているか確認して（ok）、
複数候補が置ける場所（＝未確定のマス）を先頭から探し（next）、
未確定のマスがあるなら（if (p != cells + N)）そのマスを仮確定して（subvert とコメントしている行）、再帰的に探索する。
再帰探索から戻ったら未確定状態に戻して呼び出し元に戻る。（これが、「メモリー消費を抑えた」バックトラックと呼ばれる処理）
未確定のマスがなければ、制約を満たしていることも確認済みのためこれが解。

ひとつには next の実装を置き換えることで探索の効率をあげられる。

もうひとつ、仮置きした数字が属する行、列、ブロックのそれぞれのマスから、仮置きした数字は候補から外せる。（外すことでいずれかのマスの候補がなくなることもある。その場合、その仮置きは間違っているから探索を省略できる）

こういった効率化を入れることで、より探索効率を上げられる。

上げられるんだけれど、後者の候補を外す実装は仮置き前の候補マスをすべて記録しておく必要が生じる。省メモリーという観点からは厳しい、気もする。（といっても、盤面ひとつ覚えるのに１６２バイト。自由度が最大としても最大の再帰回数は８０なので最大でも１５キロバイトで収まるな）（１セル９ビットでいいところ贅沢に１６ビット使っているので、その気になってケチればもっと詰められる）

Ｃ言語を使っていてマズいのは、メモリーが直に見えること。
どうしてもメモリー効率を上げるにはどうしたらいいのか、ということが気になってしまう。