ナンプレ(数独)問題作成プログラム　その４

SIMD Within A Register の実際のプログラムは、16ビットにしてそれ以外は前回の説明の通りにプログラムすると

    static inline uint16_t ones16(uint16_t x)
    {
	x = (x & UINT16_C(0x5555)) + ((x >> 1) & UINT16_C(0x5555));
	x = (x & UINT16_C(0x3333)) + ((x >> 2) & UINT16_C(0x3333));
	x = (x & UINT16_C(0x0f0f)) + ((x >> 4) & UINT16_C(0x0f0f));
	x = (x & UINT16_C(0x00ff)) + ((x >> 8) & UINT16_C(0x00ff));
	return x;
    }

これ0x5555がマジックナンバーだと思って#defineしたりすると、あとでソースを見たときに分からなくなるから、十六進表記の数字のままにして置いた方がいい。二進表記が使えれば、二進表記の方がいいが、それだけのためにバージョンを上げたりC++にしたりするのは考え物だ。0x5555が二進表記で 0101010101010101 になることを確かめるのはそれほど面倒ではないが、define された記号だと面倒ですよ。
しかし、The Aggregate Magic Algorithmsに紹介されているプログラムはもう少しテクニックを使ったり、不要な処理を減らして以下のようになっている。

    static inline uint16_t ones16(uint16_t x)
    {
	x -= ((x >> 1) & UINT16_C(0x5555));
	x = (((x >> 2) & UINT16_C(0x3333)) + (x & UINT16_C(0x3333)));
	x = (((x >> 4) + x) & UINT16_C(0x0f0f));
	x += (x >> 8);
	return(x & 0x0000001f);
    }

というわけで、SWARを使用することによって高速に1の数を数えられるので、フラグを持たないと決めたわけだが、しかし、やっぱり気が変わってフラグを持つことにしようと思うかも知れないので、アクセス関数を作っておく。優柔不断対策。

    static inline int is_single(cell_t * cell)
    {
	return ones16(cell->symbol) == 1;
    }

static inline とついているように、これらの関数はヘッダファイルに入れる。numpl.h としようか。
そしたら、9x9のナンプレの盤面を表すのは

#define LINE_SIZE 9
#define ARRAY_SIZE (LINE_SIZE * LINE_SIZE)
    typedef struct {
	cell_t ar[ARRAY_SIZE];
    } numpl_array;

次は、行・列・ブロックの定義だが、これらは同じように扱える必要がある。行はrow, 列はcol,ブロックはblockとして列は line とする。cell の実態は一次元配列におく。rows, cols, blocks にあるのは一次元配列のインデックスである。これはconstants というファイルに入れる。constants.h は

    extern const int rows[LINE_SIZE][LINE_SIZE];
    extern const int cols[LINE_SIZE][LINE_SIZE];
    extern const int blocks[LINE_SIZE][LINE_SIZE];

こんな感じで、constants.c は

const int rows[9][9] = {
    {0, 1, 2, 3, 4, 5, 6, 7, 8},
    {9, 10, 11, 12, 13, 14, 15, 16, 17},
    {18, 19, 20, 21, 22, 23, 24, 25, 26},
    {27, 28, 29, 30, 31, 32, 33, 34, 35},
    {36, 37, 38, 39, 40, 41, 42, 43, 44},
    {45, 46, 47, 48, 49, 50, 51, 52, 53},
    {54, 55, 56, 57, 58, 59, 60, 61, 62},
    {63, 64, 65, 66, 67, 68, 69, 70, 71},
    {72, 73, 74, 75, 76, 77, 78, 79, 80}
};

const int cols[9][9] = {
    {0, 9, 18, 27, 36, 45, 54, 63, 72},
    {1, 10, 19, 28, 37, 46, 55, 64, 73},
    {2, 11, 20, 29, 38, 47, 56, 65, 74},
    {3, 12, 21, 30, 39, 48, 57, 66, 75},
    {4, 13, 22, 31, 40, 49, 58, 67, 76},
    {5, 14, 23, 32, 41, 50, 59, 68, 77},
    {6, 15, 24, 33, 42, 51, 60, 69, 78},
    {7, 16, 25, 34, 43, 52, 61, 70, 79},
    {8, 17, 26, 35, 44, 53, 62, 71, 80}
};

const int blocks[9][9] = {
    {0, 1, 2, 9, 10, 11, 18, 19, 20},
    {3, 4, 5, 12, 13, 14, 21, 22, 23},
    {6, 7, 8, 15, 16, 17, 24, 25, 26},
    {27, 28, 29, 36, 37, 38, 45, 46, 47},
    {30, 31, 32, 39, 40, 41, 48, 49, 50},
    {33, 34, 35, 42, 43, 44, 51, 52, 53},
    {54, 55, 56, 63, 64, 65, 72, 73, 74},
    {57, 58, 59, 66, 67, 68, 75, 76, 77},
    {60, 61, 62, 69, 70, 71, 78, 79, 80}
};

手で表を書いて書き写してもいいし、LibreOffice Calc などの表計算ソフトを使ってもいい。ただし、ブログに書くときは、当然スクリプトで生成ましたよ、というような顔をしておく方がいい。
Microsoft Office Excel 2013 通常版 [プロダクトキーのみ] [パッケージ] (PC2台/1ライセンス)

予定していたより随分時間がかかって進まない。まあ、読者もいないから気長に行こう。