सुडोकू वैधता जांच एल्गोरिदम - यह कोड कैसे काम करता है?

Question

मैं यहां पोस्ट किया गया एक प्रश्न पढ़ रहा था: Sudoku algorithm in C#

और पोस्ट किए गए समाधानों में से एक कोड का यह टुकड़ा था।

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; 
} 

विचार यह है कि यह मूल्यों की सरणी में डुप्लिकेट का पता लगाएगा; लेकिन मैं कितना नहीं जानता उससे अभिभूत हूं। क्या कोई मुझे ये समझा सकता है?

संपादित करें: सभी को धन्यवाद। इतने सारे महान जवाब, मुझे नहीं पता कि कैसे एक का चयन करें। यह अब सही समझ में आता है।

Answer 1

वास्तव में एक अच्छा विचार है।

असल में, यह एक "बिट सरणी" के रूप में 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; 
} 

Answer 2

विचार एक नंबर है, जहां n सेल मूल्य है की nth बिट स्थापित करने के लिए है। चूंकि सुडोकू मान 1-9 से हैं, इसलिए सभी बिट 0-512 की सीमा के भीतर फिट होते हैं। प्रत्येक मान के साथ, जांचें कि nth बिट पहले से सेट है या नहीं, और यदि ऐसा है, तो हमें एक डुप्लिकेट मिला है। यदि नहीं, तो हमारे चेक नंबर पर nth बिट सेट करें, इस मामले में flag, पहले से उपयोग किए गए नंबरों को जमा करने के लिए। यह सरणी से डेटा स्टोर करने का एक तेज़ तरीका है।

Answer 3

दिलचस्प। यह ध्वज-पूर्णांक में उस बिट को सेट करके पहले से मिली संख्याओं को संग्रहीत करता है। उदाहरण:

• यह एक 4
• शिफ्ट पाया तो 4 बिट सरणी में जिसके परिणामस्वरूप बिट्स से नंबर 1 झंडा पूर्णांक में 00010000b
• या यह परिणाम flag- में (जो पहले 0) था int 00010000b
• किया जा रहा है यह पाया एक 2
• शिफ्ट तो थोड़ा-सरणी में जिसके परिणामस्वरूप 2 बिट्स से नंबर 1 00000100b
• या यह झंडा पूर्णांक में (जो पहले 00010000b था) झंडा पूर्णांक से किया जा रहा में परिणाम 00010100b

यह प्रत्येक नंबर के लिए भी परीक्षण करता है यदि वह बिट पहले से ही ध्वज-int में सेट है।

Answer 4

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 

Answer 5

यह जांचता है कि सरणी में मान अद्वितीय हैं या नहीं। ऐसा करने के लिए, यह एक पूर्णांक बनाता है - ध्वज - और यह मानों की सरणी में मानों के अनुसार ध्वज में बिट्स सेट करता है। यह देखने के लिए जांच करता है कि कोई विशेष बिट पहले से सेट है या नहीं; यदि यह है, तो एक डुप्लिकेट है और यह विफल रहता है। अन्यथा, यह थोड़ा सेट करता है।

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. 
} 

Answer 6

के माध्यम से यह काम करने देता है:

यहाँ एक टूटने है। values = 1,2,3,2,5

पुनरावृत्ति 1:

bit = 1 << 1bit = 10

if(00 & 10 != 00)false

flag |= bitflag = 10

पुनरावृत्ति 2:

bit = 1 << 2bit = 100

if(010 & 100 != 000)false

flag |= bitflag = 110

पुनरावृत्ति 3:

bit = 1 << 3bit = 1000

if(0110 & 1000 != 0000)false

flag |= bitflag = 1110

पुनरावृत्ति 4:

bit = 1 << 2bit = 100

if(1110 & 0100 != 0000)TRUE यह सही का आकलन है, जिसका अर्थ है कि हम एक डबल पाया, और झूठे लौट