Developer

競技プログラミング風 C++問題集【第7回】
2021.01.29
Lv3

競技プログラミング風 C++問題集【第7回】

目次

数独(難易度:★★★☆☆)

問題

9×9の通常サイズの数独(「数独」は株式会社ニコリの登録商標です)の盤面情報を持つ1次元配列と、マス目位置(x, y)を引数で渡され、 指定された箇所にどの数字が配置可能かを返す関数 short getCanPlacedNums(const short board[], int x, int y) を実装しなさい。

ただし、各マスの値は、空欄は0, 数値: 1を「数値-1」回左にシフトした値とする (1: 0x0001, 2: 0x0002, 3: 0x0004, 4: 0x0008, … 9: 0x0100)。
関数が返す値も上記のビット値のビット和とする。例えば、3と5が配置可能な場合は 0x0004 | 0x0010 = 0x0014 を返す。

また、x, y は 0 ~ 8 の範囲とし、左上が原点(0, 0)とする。

例えば、盤面が下図の場合、(2, 1) には、3, 5, 8, 9 を入れることができるので、getCanPlacedNums(board, 2, 1) は 0x0004 | 0x0010 | 0x0080 | 0x0100 = 0x0194 を返す。

競技プログラミング風C++問題集【第7回】_01

1次元配列中のデータの順序は、左から右、上から下の順序とする。

なお、知っている人がほとんだだとは思うが、念の為に数独ルールを以下に示しておく。

・各マスには数字 ‘1’~’9′ を入れる。
・横9マス・縦9マス・(上図の太線部分の)3×3ブロック内には同じ数字を入れない。

#include <iostream>       //  標準入出力ライブラリ
using namespace std;    //  std 名前空間使用
#define DO_TEST(exp)    do_test(exp, __LINE__)
void do_test(bool b, int line) {
    if( b ) return;     //  OK
    cout << "\nNG at line " << line << "\n";
    exit(1);
}
#define     EMPTY       0
#define     NUM_1       0x0001
#define     NUM_2       0x0002
#define     NUM_3       0x0004
#define     NUM_4       0x0008
#define     NUM_5       0x0010
#define     NUM_6       0x0020
#define     NUM_7       0x0040
#define     NUM_8       0x0080
#define     NUM_9       0x0100
#define     WD          9
#define     BWD         (WD/3)
#define     ALL             ((1<<WD)-1)
void set(short* board, const char* ptr) {
    for (; *ptr != '\0'; ++ptr)
        *board++ = (*ptr >= '1' && *ptr <= '9') ? (1 << (*ptr - '1')) : 0;
}
short getCanPlacedNums(const short board[], int x, int y) {
    //  ToDo: ここに str で指定された地形に貯まる水の面積を返すコードを記述
    return 0;
}
int main() {
    short board[WD*WD];       //  数独盤面
    set(board, "1.28.59.47...6...2...4.9...6.1...5.9.7.....6.8.4...2.1...6.8...4...5...65.61.74.3");
    DO_TEST( getCanPlacedNums(board, 0, 0) == 0 );
    DO_TEST( getCanPlacedNums(board, 1, 1) == (NUM_3|NUM_4|NUM_5|NUM_8|NUM_9) );
    DO_TEST( getCanPlacedNums(board, 2, 4) == (NUM_3|NUM_5|NUM_9) );
    DO_TEST( getCanPlacedNums(board, 8, 4) == (NUM_8) );
    cout << "\nGood Job!\n";
    return 0;
}
ヒント

・x, y 座標を1次元配列添字に変換するには x + y * WD とすればいいぞ。
・最初に (x, y) 位置に数字が入っているかどうかをチェックし、既に入っていれば 0 を返すんだぞ。
・配置済み数字をビット列で表す bits を用意し、これを 0 で初期化するぞ。
・x 列、y 行の各数字のビットを bits にビット論理加算(bits |= b)していく。
・3×3 ブロックについては、左上点をもとめ、そこから for文を2重に回し、各数字のビットを bits にビット論理加算していくといいぞ。
・関数が返すのは、使用済み数字ではなく使用可能数字なので、1~9 のビット部分を反転するといいぞ。

解答例
short getCanPlacedNums(const short board[], int x, int y) {
    if (board[x + y * WD] != EMPTY) return 0;   //  空欄でない場合
    short bits = 0;     //  配置済み数字ビット
    for (int i = 0; i != WD; ++i)   //  縦横方向配について
        bits |= board[i + y * WD] | board[x + i * WD];  //  配置済み数字ビット更新
    int x0 = x - x % BWD;   //  3x3ブロック左端位置
    int y0 = y - y % BWD;   //  3x3ブロック上端位置
    for (int v = 0; v != BWD; ++v) {    //  3x3ブロック内の各位置について
        for (int h = 0; h != BWD; ++h)
            bits |= board[x0 + h + (y0 + v) * WD];  //  ブロック内数字  配置済み数字ビット更新
    }
    return ALL ^ bits;  //  配置済み数字を反転することで配置可能数字ビットを返す
}
解説

x, y 座標を配列添字に変換するには x + y * WD とするとよい。 なので、最初に board[x + y * WD] が空欄(EMPTY)かどうかをチェックし、空欄でなければ数値を配置できないので 0 を返す。
次に、縦・横・3×3ブロック内に配置済み数字をビット列で表す bits を用意し、これを 0 で初期化しておく。 3 が配置済みであれば 0x004 を、4 が配置済みであれば 0x008 のビットが立っているものとする。 したがって、配置済みビットが 0x00c であれば、数字3と4が配置済みであることを表す。 ビット演算に慣れていない人にはちょっと難しいことかもしれないが、ビット列を使えば、 このように複数の状態をひとつの変数で表すことが可能になり、メモリ効率・実行効率ともに優れたものになる。
次にfor文で行・列を回して、縦横方向のマスで使用している数字のビットを bits に論理加算する(bits |= board[ix])。 通常の加算であれば、同じ数字を2回加えると値が倍になってしまうが、 論理加算であれば何回加算しても、そのビットにしか影響を与えない。
getCanPlacedNums() 関数は配置可能なビット列を返さないといけないが、bits には使用済みビット列が入っているので、 1~9 のビット部分を反転する必要がある。そのためには ALL ^ bits を返せばよい。 これは、反転したいビット部分が1の値と排他的論理和(XOR)を取ると、その部分だけ反転するというテクニックだ。

関連記事

投稿が見つかりません。

筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。