19

ここに投稿された質問を読んでいました: C# の数独アルゴリズム

投稿されたソリューションの 1 つがこのコードでした。

public static bool IsValid(int[] values) {
        int flag = 0;
        foreach (int value in values) {
                if (value != 0) {
                        int bit = 1 << value;
                        if ((flag & bit) != 0) return false;
                        flag |= bit;
                }
        }
        return true;
}

アイデアは、値の配列で重複を検出することです。しかし、知らないことが多くて困っています。誰かが私にこれを説明できますか？

編集：みんなありがとう。素晴らしい回答が多すぎて、どれを選べばよいかわかりません。今では完全に理にかなっています。

4

6 に答える 6

22

本当にいいアイデアです。

基本的に、intフラグ（最初はゼロに設定）を「ビット配列」として使用します。値ごとに、フラグの対応するビットが設定されているかどうかを確認し、設定されていない場合は設定します。

代わりに、そのビット位置がすでに設定されている場合、対応する値がすでに表示されていることがわかっているため、数独は無効です。

詳細：

public static bool IsValid(int[] values)
{
    // bit field (set to zero => no values processed yet)
    int flag = 0;
    foreach (int value in values)
    {
        // value == 0 => reserved for still not filled cells, not to be processed
        if (value != 0)
        {
            // prepares the bit mask left-shifting 1 of value positions
            int bit = 1 << value; 
            // checks if the bit is already set, and if so the Sudoku is invalid
            if ((flag & bit) != 0)
                return false;
            // otherwise sets the bit ("value seen")
            flag |= bit;
        }
    }
    // if we didn't exit before, there are no problems with the given values
    return true;
}
于 2011-02-24T22:43:19.840 に答える
5

それをやり遂げましょう。 values = 1,2,3,2,5

反復 1:

bit = 1 << 1 bit = 10

if(00 & 10 != 00) false

flag |= bit flag = 10

反復 2:

bit = 1 << 2 bit = 100

if(010 & 100 != 000) false

flag |= bit flag = 110

反復 3:

bit = 1 << 3 bit = 1000

if(0110 & 1000 != 0000) false

flag |= bit flag = 1110

反復 4:

bit = 1 << 2 bit = 100

if(1110 & 0100 != 0000) TRUEこれは true と評価され、double が見つかったことを意味し、false を返します。

于 2011-02-24T22:53:54.400 に答える
3

アイデアはnth、数値のビットを設定することです。ここnで、はセルの値です。数独の値の範囲は1〜9であるため、すべてのビットは0〜512の範囲に収まります。それぞれの値で、nthビットがすでに設定されているかどうかを確認します。設定されている場合は、重複が見つかりました。そうでない場合は、nthチェック番号（この場合は）のビットを設定しflagて、すでに使用されている番号を累積します。配列よりもはるかに高速にデータを保存できます。

于 2011-02-24T22:43:33.863 に答える
2

面白い。そのビットをフラグ整数に設定することにより、すでに見つかった数値を格納します。例：

  • 4が見つかりました
  • 番号 1 を 4 ビットずつシフトすると、ビット配列 00010000b になります。
  • または、flag-int (以前は 0) に入れると、flag-int は 00010000b になります。
  • 2が見つかりました
  • 番号 1 を 2 ビットずつシフトすると、ビット配列 00000100b になります。
  • または、flag-int (以前は 00010000b でした) に入れると、flag-int は 00010100b になります。

また、そのビットが flag-int ですでに設定されているかどうか、各数値についてもテストします。

于 2011-02-24T22:47:25.927 に答える
2

配列内の値が一意であるかどうかを確認します。これを行うには、整数 (フラグ) を作成し、値の配列の値に従ってフラグにビットを設定します。特定のビットがすでに設定されているかどうかを確認します。そうである場合、重複があり、失敗します。それ以外の場合は、ビットを設定します。

内訳は次のとおりです。

public static bool IsValid(int[] values) {
        int flag = 0; // <-- Initialize your flags; all of them are set to 0000
        foreach (int value in values) { // <-- Loop through the values
                if (value != 0) { // <-- Ignore values of 0
                        int bit = 1 << value; // <-- Left-shift 1 by the current value
// Say for example, the current value is 4, this will shift the bit in the value of 1
// 4 places to the left. So if the 1 looks like 000001 internally, after shifting 4 to the 
// left, it will look like 010000; this is how we choose a specific bit to set/inspect
                        if ((flag & bit) != 0) return false; // <-- Compare the bit at the
// position specified by bit with the corresponding position in flag. If both are 1 then
// & will return a value greater than 0; if either is not 1, then & will return 0. E.g.
// if flag = 01000 and bit = 01000, then the result will be 01000. If flag = 01000 and 
//bit = 00010 then the result will be 0; this is how we check to see if the bit 
// is already set. If it is, then we've already seen this value, so return false, i.e. not
// a valid solution
                        flag |= bit; // <-- We haven't seen this value before, so set the 
// corresponding bit in the flag to say we've seen it now. e.g. if flag = 1000 
// and bit = 0100, after this operation, flag = 1100
                }
        }
        return true; // <-- If we get this far, all values were unique, so it's a valid
// answer.
}
于 2011-02-24T22:50:55.360 に答える
1 
 int bit = 1 << value; //left bit shift - selects the bit that corresponds to value
 if ((flag & bit) != 0) return false; //bitwise AND - checks the flag to see whether bit is already set
 flag |= bit; // bitwise OR - sets the bit in the flag
于 2011-02-24T22:49:30.463 に答える