I got this problem today has part of a conversation that I was having and thought I was interesting. Basically how can you in O( n ) validate that a 9×9 soduku is valid.
There are 3 rules that need to be followed for a validation to return true:
- For each row there can only be and instance of each numbers.
- For each column there can only be and instance of each numbers.
- For each cluster of 9 there can only be and instance of the set of numbers.
The trivial solution that comes to mine is to go and count for each of this different conditions but that would require at least 3 passes tru the grid. For my solution i decided to just store a hashset for each of the conditions that need to be valid and stop on a negative. We use the numbers has distinct markers and not has numbers in particular since being number has no properties that help us. Solution is below:
public SudokuPuzzleValidator():this(newint[9, 9])
public SudokuPuzzleValidator(int[,] board)
_board = board;
public bool Validate()
for (var row = 0; row < integersInGame; row++)
private static void InitializeSet(int integersInGame, HashSet<int> rowSet)
private static int FigureOutSubGrid(int row, int column)