Sudoku validity check algorithm - how does this code works?

Question

I was reading a question posted here: Sudoku algorithm in C#

And one of the solutions posted was this piece of code.

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

The idea is that it will detect duplicates in the array of values; but I'm overwhelmed by how much I don't know. Can someone explain this to me?

EDIT: Thanks everyone. So many great answers, I don't know how to select one. It now makes perfect sense.

Sapphirine

Wouldn't checking that the sum of the values equals the sum of unique possible digits (for 9x9 game it would be 45) be more efficient for a high-level language? – Hydrodynamics

Answer 1

Really a nice idea.

Basically, it uses an int flag (initially set to zero) as a "bit array"; for each value, it checks if the corresponding bit in the flag is set, and if it's not, it sets it.

If, instead, that bit position is already set, it knows that the corresponding value has already been seen, so the piece of Sudoku is invalid.

More in detail:

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

Gherardo

Answer 2

Lets work through it. values = 1,2,3,2,5

Iteration 1:

bit = 1 << 1 bit = 10

if(00 & 10 != 00) false

flag |= bit flag = 10

Iteration 2:

bit = 1 << 2 bit = 100

if(010 & 100 != 000) false

flag |= bit flag = 110

Iteration 3:

bit = 1 << 3 bit = 1000

if(0110 & 1000 != 0000) false

flag |= bit flag = 1110

Iteration 4:

bit = 1 << 2 bit = 100

if(1110 & 0100 != 0000) TRUE This evaluates to true, meaning we found a double, and return false

Fado

Answer 3

The idea is to set the nth bit of a number, where n is the cell value. Since sudoku values range from 1-9, all the bits fit within a range of 0-512. With each value, check if the nth bit is already set, and if so, we've found a duplicate. If not, set the nth bit on our check number, in this case flag, to accumulate numbers that have already been used. It's a much faster way to store data than an array.

Lewie

While it is a much smaller way to store data, I would argue that it is not a much "faster" way to store data. The reason is that .NET is usually running on PCs, which are usually optimized for dealing with data that is much larger than one bit (e.g. 4 bytes for a Boolean, which is what the BitArray (msdn.microsoft.com/en-us/library/…) type uses internally). More info: #295405 – Popham

@Pat: Good point. I guess I meant it is faster than the next obvious choice of using an array of 9 values, in terms of allocating, initializing, and deallocating the array, not necessarily in the actual foreach loop itself. – Lewie

BitVector is more approptiated storage container – Stadiometer

Answer 4

Interesting. It stores the numbers it already found by setting that bit in the flag-integer. Example:

• It found a 4
• Shift then number 1 by 4 bits resulting in the bit-array 00010000b
• Or it into the flag-int (which was previously 0) results in the flag-int being 00010000b
• It found a 2
• Shift then number 1 by 2 bits resulting in the bit-array 00000100b
• Or it into the flag-int (which was previously 00010000b) results in the flag-int being 00010100b

It also tests for each number if that bit is already set in the flag-int.

Kienan

Answer 5

It checks to see if values in the array are unique. To do this, it creates an integer - flag - and it sets bits in the flag according to values in the array of values. It checks to see if a particular bit is already set; if it is, then there is a duplicate and it fails. Otherwise, it sets the bit.

Here's a breakdown:

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

Bonkers

Answer 6

 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

Broncobuster