0

数独パズルの行、列、およびブロックで使用されている数字を表す 3 つのビット ベクトルを 1 ～ 9 の位置から取得する関数を作成しようとしています。セルは未使用の数字のみを使用でき、関数は、すべてのベクトルの数字が 1 つの可能性を強制するか、複数の可能性があるかを返すことになっています。これは、3 つのベクトルすべてをマージし、結果のパターンのどこに「未設定」のビットがあるかを判断する必要があることを意味すると解釈しました。

ただし、この派生に触発されたにもかかわらず、私の関数は gdb で正しいマスクを返すようには見えません: http://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge

2 つのうち 1 つのセットをマージし、次に 3 つ目のセットを前のマージにマージし、最終的なマージで 1 の数を導出し、それを差し引いて 0 の数を導出しようとしています。

次に、次の関数を書きました。

   bool possibilities(unsigned short row, unsigned short col, unsigned short bloc)
   {

    unsigned int mask = (1 << col) - 1;
    unsigned int inbw = (row & ~mask) | (col & mask);

    unsigned int mask2 = (1 << bloc) - 1;
    unsigned int final = (inbw & ~mask2) | (bloc & mask2);

    int num_1s;
    while (result != 0) {
            result &= (result - 1);
            num_1s++;
    }

    int zeroes = 32 - num_1s; // 32 being the presumed number of bits in a short.

    if (zeroes == 1) return true;
    return false;
   }
4

2 に答える 2

2

この文書によると：

http://www.cplusplus.com/doc/tutorial/variables/

short は char より小さくありません。少なくとも 16 ビット。したがって、ゼロを 32 - num_1s として計算するのは間違っている可能性があります。

そうする代わりに、unsigned short を取得して 1 で埋め、最初の 9 ビットを 0 に設定することができます。

var = 0xFFFFFE00

そうすれば、ソリューションが使用する変数のサイズに大きく依存することを回避できます。

その問題の解決策は次のようになります (上記のような行、列、およびブロックを想定):

possibilities = row | col | bloc;
while (possibilities != 0) {
     num_0s += ((~possibilities)&1);
     possibilities = (possibilities >> 1);
}
于 2014-07-21T12:25:07.717 に答える
0

row、col、およびbloc(sic)のそれぞれが、1 ～ 9 の数字の存在を表す個々のビット (おそらくビット 0 ～ 8) を持つビット マスクであることを正しく理解していれば、マスクは間違っています (実際にはまったく無意味です)。たとえば、colビット 8 が設定されている場合、 mask = (1 << col) - 11 を 256 だけ左にシフトします。幅が 256 ビットを超える可能性は非常に低いためunsigned short、シフト後に 0 になり、次にすべてのビットが設定されたマスクになります。 1. この後は is 0から(row & ~mask) | (col & mask)のみになります。col~mask

いくつかの簡単なオプションが思い浮かびます。

1) まったくマージしないでください。単純に、3 つの変数のそれぞれで個別に popcount を実行します。最近の一部のプロセッサには popcount の命令があるため、たとえばコンパイラの組み込み関数 (たとえば__builtin_popcount) を使用して使用を管理すると、さらに高速になります。

2) 各変数のビットを個別にマスクし、位置にシフトします。例:

const unsigned int mask = 0x1FF;
unsigned int final = (col & mask) | ((row & mask) << 9) | ((bloc & mask) << 18);

また、32 から 1 の数を引かないでください。27 (= 3×9) から引きます。これは、3 つの変数のそれぞれに最大 9 ビットを設定できる場合の 1 ビットの最大数です。

編集：あなたがマージしようとしていることを誤解している可能性があります。3 つの変数のすべての 1 ビットの単純な結合を意味する場合は、unsigned int final = col | row | blocマスクする必要はありません。次に、9 から popcount (1 ビットの数) を引きます。

于 2014-07-21T12:27:32.000 に答える