So there is a problem called Valid Sudoku on LeetCode, problem number 36. Let’s go through the problem. Also, good to note, I will write this is C#.
Determine if a
9 x 9Sudoku board is valid. Only the filled cells need to be validated according to the following rules:Each row must contain the digits
1-9without repetition.Each column must contain the digits
1-9without repetition.Each of the nine
3 x 3sub-boxes of the grid must contain the digits1-9without repetition.Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
LeetCode
Input
Input: board = [[“5″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”] ,[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”] ,[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”] ,[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″] ,[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″] ,[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″] ,[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”] ,[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″] ,[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]]
Output: true
There is a few approaches for a solution provided, for me personally I think the one with the use of HashSet is the most easy understanding. There are three approaches explained on LeetCode and all of them have the same time complexity so it should be fine.
First initialization of variables
const int N = 9;
// Rows
List<HashSet<char>> rows = new List<HashSet<char>>() { new HashSet<char> (N)};
// Columns
List<HashSet<char>> columns = new List<HashSet<char>>() { new HashSet<char> (N)};
// Squares
List<HashSet<char>> squares = new List<HashSet<char>>() { new HashSet<char> (N)};So what we are doing here is first setting a constant named N with the the value of 9 which represents the size of each of our Lists. Each List will contain its own HashSet which holds all numbers is for each row, for each column, and for each square (3*3). That way we can go through each row and column and square and check if the same number already exists. Now we have only set the Capacity of each List, we need to actually initalize each element with a new HashSet, instead of writing that in the curcle brackets 9 times for each HashSet constructor, we can Add a HashSet for each element with a loop, using the N variable again.
// Fill our rows, columns and square Lists with empty char HashSets
for (int i = 0; i < N-1; i++)
{
rows.Add(new HashSet<char>());
columns.Add(new HashSet<char>());
squares.Add(new HashSet<char>());
}Since N represents the length of the array, we will do -1 to actually only Add 9 new elements with empty HashSets instead of 10.
Then we will actually go through the board and add each character from the board for each row if it doesn’t exists, and same for columns, and same for our square List.
// Rows
for (int r = 0; r < N; r++)
{
// Cols
for (int c = 0; c < N; c++)
{
if (board[r][c] == '.')
{
continue;
}
// Rows contains value
if (rows[r].Contains(board[r][c]))
{
return false;
}
if (columns[c].Contains(board[r][c]))
{
return false;
}
int squareNum = (r / 3) * 3 + c / 3;
if (squares[squareNum].Contains(board[r][c]))
{
return false;
}
rows[r].Add(board[r][c]);
columns[c].Add(board[r][c]);
squares[squareNum].Add(board[r][c]);
}
}As you can see from the comments, will go through the 9 rows (N) and then continue with the columns for each row (N^2), and while we are inside looping through each column, we will add that character to our HashSet for this column and for this row we are currently at. The current row is r and the current column is c. Since we have a list of precisely 9 row elements we can access that element through row[r]. Same for columns, we have 9 columns ready to be accessed and inserted with characters to the HashList, which we will add. Also, before adding anything to our HashSets, we check if we doesn’t already have the character, if we do, the Sudoko is not valid so we return false!
If we doesn’t have the same character in the rows hashset, or the columns hashset, or the square’s hashset we have a valid Suduko and we return true.
Full code solution
public class Solution {
public bool IsValidSudoku(char[][] board) {
const int N = 9;
// Rows
List<HashSet<char>> rows = new List<HashSet<char>>() { new HashSet<char> (N)};
// Columns
List<HashSet<char>> columns = new List<HashSet<char>>() { new HashSet<char> (N)};
// Squares
List<HashSet<char>> squares = new List<HashSet<char>>() { new HashSet<char> (N)};
// Fill our rows with empty char arrays
for (int i = 0; i < N-1; i++)
{
rows.Add(new HashSet<char>());
columns.Add(new HashSet<char>());
squares.Add(new HashSet<char>());
}
// Rows
for (int r = 0; r < N; r++)
{
// Cols
for (int c = 0; c < N; c++)
{
if (board[r][c] == '.')
{
continue;
}
// Rows contains value
if (rows[r].Contains(board[r][c]))
{
return false;
}
if (columns[c].Contains(board[r][c]))
{
return false;
}
int squareNum = (r / 3) * 3 + c / 3;
if (squares[squareNum].Contains(board[r][c]))
{
return false;
}
rows[r].Add(board[r][c]);
columns[c].Add(board[r][c]);
squares[squareNum].Add(board[r][c]);
}
}
return true;
}
}