Problem Explanation

A Sudoku puzzle is a logic-based game that is played on a 9x9 grid. The purpose of the game is to fill up all the squares in the grid in such a way that every row, column, and 3x3 sub-grid includes all the digits from 1 to 9 without repetition.

In this problem, we are given a partially filled Sudoku grid and our task is to validate whether the filled cells follow the rules of Sudoku.

Example

Consider the example below:

Input: [ ["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

This is a valid Sudoku board as all the given digits in the rows, columns, and 3x3 sub-grids appear without repetition.

Approach

The solution approach is to iterate over each cell in the Sudoku board, and while doing so, check if the current number appears in the current row, current column, or current 3x3 sub-grid. We can accomplish this by using a set data structure.

We build a set of strings for identified numbers where each string represents a number's presence in the Sudoku board. The string is constructed as follows:

• For each number that is found in a column, we build a string
  • + "seen in column" + .
• For each number that is found in a row, we build a string
  • + "seen in row" + .
• For each number that is found in a sub-grid, we build a string
  • + "seen in sub-grid" + .

Since each distinct number can only appear once per row, per column and per sub-grid, we will end up with unique strings if the board configuration is valid. If we encounter a string that already exists in our set, then there is repetition, breaking the rules and hence the board is invalid.

C++

1
2
3class Solution {
4 public:
5  bool isValidSudoku(vector<vector<char>>& board) {
6    unordered_set<string> seen;
7
8    for (int i = 0; i < 9; ++i) {
9      for (int j = 0; j < 9; ++j) {
10        if (board[i][j] == '.') {
11          continue;
12        }
13        const string c(1, board[i][j]);
14        if (!seen.insert(c + " seen in row " + to_string(i)).second ||
15            !seen.insert(c + " seen in column " + to_string(j)).second ||
16            !seen.insert(c + " seen in sub-grid " + to_string(i / 3) + to_string(j / 3)).second) {
17          return false;
18        }
19      }
20    }
21
22    return true;
23  }
24};

In this C++ solution, we first create an unordered set seen to keep track of all the unique numbers we have seen so far. We iterate over all the cells in the 9x9 Sudoku board, and for each filled cell, we generate the unique strings. If we are unable to insert any of these strings into the set (because they are already there), we return false making the board invalid. If we are able to insert all the strings into the set (meaning all numbers follow the Sudoku rules), we return true.

Python

1
2 python
3class Solution:
4    def isValidSudoku(self, board) -> bool:
5        seen = set()
6        for i in range(9):
7            for j in range(9):
8                current_val = board[i][j]
9                if current_val != '.':
10                    if (current_val + " seen in row " + str(i)) in seen or \
11                       (current_val + " seen in column " + str(j)) in seen or \
12                       (current_val + " seen in sub-grid " + str(i//3) + str(j//3)) in seen:
13                        return False
14                    seen.add(current_val + " seen in row " + str(i))
15                    seen.add(current_val + " seen in column " + str(j))
16                    seen.add(current_val + " seen in sub-grid " + str(i//3) + str(j//3))
17        return True

In this Python solution, instead of trying to insert the unique strings into the set and then checking if the insertion was successful (as we were able to do in C++), we first check if the unique strings already exist in the set - in which case, we return False indicating an invalid board state. If the strings do not already exist, we add them to the set.

Java

1
2 java
3public class Solution {
4    public boolean isValidSudoku(char[][] board) {
5        Set<String> seen = new HashSet<>();
6        
7        for (int i = 0; i < 9; ++i) {
8            for (int j = 0; j < 9; ++j) {
9                char current_val = board[i][j];
10                if (current_val != '.') {
11                    if (!seen.add(current_val + " seen in row " + i) ||
12                        !seen.add(current_val + " seen in column " + j) ||
13                        !seen.add(current_val + " seen in sub-grid " + i / 3 + j / 3)) {
14                        return false;
15                    }
16                }
17            }
18        }
19        
20        return true;
21    }
22}

Java's HashSet data structure provides an add method, which inserts the value into the Set and returns true if the value did not already exist in the set. We make use of this feature to insert each unique string into our set and check simultaneously if the value was unique.

JavaScript

1
2 javascript
3var isValidSudoku = function(board) {
4    let seen = new Set();
5    
6    for (let i = 0; i < 9; ++i) {
7        for (let j = 0; j < 9; ++j) {
8            let current_val = board[i][j];
9            if (current_val !== '.') {
10                if (seen.has(current_val + " seen in row " + i) || 
11                    seen.has(current_val + " seen in column " + j) || 
12                    seen.has(current_val + " seen in sub-grid " + Math.floor(i/3) + Math.floor(j/3))) {
13                    return false;
14                }           
15                seen.add(current_val + " seen in row " + i);
16                seen.add(current_val + " seen in column " + j);
17                seen.add(current_val + " seen in sub-grid " + Math.floor(i/3) + Math.floor(j/3));
18            }
19        }
20    }
21    
22    return true;
23};

The concept behind the JavaScript solution is very similar to the Python solution. Due to unavailability of add method (like in Set data structure of Java) that returns boolean, we initially check if our string exists in the set. If yes, we return false. Otherwise, we add it into the set.

C#

1
2 csharp
3public class Solution {
4    public bool IsValidSudoku(char[][] board) {
5        ISet<string> seen = new HashSet<string>();
6        
7        for (int i = 0; i < 9; ++i) {
8            for (int j = 0; j < 9; ++j) {
9                char current_val = board[i][j];
10                if (current_val != '.') {
11                    if (!seen.Add(current_val + " seen in row " + i) ||
12                        !seen.Add(current_val + " seen in column " + j) ||
13                        !seen.Add(current_val + " seen in sub-grid " + i / 3 + j / 3)) {
14                        return false;
15                    }
16                }
17            }
18        }
19        
20        return true;
21    }
22}

This C# solution works similarly as the Java solution. C#'s HashSet data structure also provides an Add method that returns a Boolean indicating whether the item was added to the set. We use this feature in order to insert each unique string into the set while simultaneously checking if the insertion was successful. If the insertion was not successful, then the board state is invalid, and we return false. If the insertion was successful for all numbers, then the board state is valid, and we return true.# Conclusion

The use of string-set data structures to validate Sudoku boards is a highly efficient method. It offers a time complexity of O(1) for checking the presence of an item (or string in our case) in the set, making it a feasible solution even on larger boards or multiple puzzles. This solution effectively encapsulates the constraints of the Sudoku game into a set of strings that provide enough information to validate the rules.

The presented solution approach in multiple programming languages including C++, Java, Python, JavaScript, and C#, illustrates the use of core language features, libraries, and their best practices, while also emphasizing the universal applicability of the approach.

Remembering that this is a solution to check the validity of a partially/fully filled Sudoku grid according to the rules of the game, it doesn't solve an incomplete Sudoku puzzle itself. The techniques for solving a Sudoku are more complex, involving backtracking, optimizing pruning methods, and sometimes, even advanced predictive analytics. The validation of a Sudoku is merely a step in the process of solving it. Regardless, understanding this step in-depth provides a strong foundation for the next steps towards a Sudoku solving algorithm.