Menu
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.
488
Check if the rows and columns contain values 1-9, without repetition. If any row or column violates this condition, the Sudoku board is invalid. Check to see if each of the 9 sub-squares contains values 1-9, without repetition. If they do, the Sudoku board is valid; otherwise, it is invalid.
Valid Sudoku. Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules: Each row must contain the digits 1-9 without repetition. Each column must contain the digits 1-9 without repetition.
The solution of a Sudoku puzzle requires that every row, col- umn, and box contain all the numbers in the set [1, 2,..., 9] and that every cell be occupied by one and only one number. This definition implies that no row, column, or box will have any number repeated.
Stochastic search / optimization methods Sudoku can be solved using stochastic (random-based) algorithms. An example of this method is to: Randomly assign numbers to the blank cells in the grid.
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;
}
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
37
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
