Bài 36 Leetcode: Valid Sudoku

Đề bài:

Xác định xem một bảng Sudoku có kích thước 9 x 9 có hợp lệ hay không. Chỉ các ô đã được điền cần được kiểm tra theo các quy tắc sau đây:

1. Mỗi hàng phải chứa các chữ số từ 1-9 mà không có chữ số nào được lặp lại.
2. Mỗi cột phải chứa các chữ số từ 1-9 mà không có chữ số nào được lặp lại.
3. Mỗi trong số chín ô con có kích thước 3 x 3 trên bảng phải chứa các chữ số từ 1-9 mà không có chữ số nào được lặp lại.

Chú ý:

• Một bảng Sudoku (được điền một phần) có thể là hợp lệ nhưng không nhất thiết phải có thể giải quyết được.
• Chỉ các ô đã được điền cần được kiểm tra theo các quy tắc đã đề cập.

Ví dụ 1:

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

Ví dụ 2:

Input: board = 
[["8","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: false
Giải thích: Tương tự như Ví dụ 1, nhưng số 5 ở góc trái trên đã được thay đổi thành số 8. Vì có hai số 8 trong ô con 3x3 góc trái trên, nên nó không hợp lệ.

Ràng buộc:

• board.length == 9 (độ dài của board là 9)
• board[i].length == 9 (độ dài của mỗi hàng của board là 9)
• board[i][j] là một chữ số từ 1-9 hoặc ‘.’.

Giải thích thuật toán bằng C ++

class Solution {
 public:
  bool isValidSudoku(vector<vector<char>>& board) {
    unordered_set<string> seen;

    for (int i = 0; i < 9; ++i)
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == '.')
          continue;
        const string c(1, board[i][j]);
        if (!seen.insert(c + "@row" + to_string(i)).second ||
            !seen.insert(c + "@col" + to_string(j)).second ||
            !seen.insert(c + "@box" + to_string(i / 3) + to_string(j / 3))
                 .second)
          return false;
      }

    return true;
  }
};

Đoạn code trên là một đoạn code C++ để kiểm tra tính hợp lệ của một bảng Sudoku có kích thước 9×9. Dưới đây là giải thích về thuật toán trong đoạn code:

1. Khai báo một unordered_set (tập hợp không có thứ tự) có tên seen để lưu trữ các giá trị đã được ghi nhận.

2. Sử dụng hai vòng lặp for để duyệt qua từng ô trong bảng Sudoku:

– Nếu ô hiện tại có giá trị là ‘.’, tức là ô đó chưa được điền, ta bỏ qua và tiếp tục với ô tiếp theo.

– Nếu ô hiện tại có giá trị khác ‘.’, ta kiểm tra tính hợp lệ của ô đó theo các quy tắc của Sudoku.

+ Tạo một chuỗi c (string) gồm một ký tự là giá trị của ô hiện tại.

+ Kiểm tra xem c + “@row” + to_string(i) đã tồn tại trong tập hợp seen chưa. Nếu đã tồn tại, tức là đã có cùng giá trị c trong cùng một hàng, ta trả về false.

+ Kiểm tra xem c + “@col” + to_string(j) đã tồn tại trong tập hợp seen chưa. Nếu đã tồn tại, tức là đã có cùng giá trị c trong cùng một cột, ta trả về false.

+ Kiểm tra xem c + “@box” + to_string(i / 3) + to_string(j / 3) đã tồn tại trong tập hợp seen chưa. Nếu đã tồn tại, tức là đã có cùng giá trị c trong cùng một ô con 3×3, ta trả về false.

+ Nếu không có trường hợp trên nào xảy ra, ta thêm các chuỗi c + “@row” + to_string(i), c + “@col” + to_string(j), c + “@box” + to_string(i / 3) + to_string(j / 3) vào tập hợp seen.

3. Sau khi kiểm tra tất cả các ô trong bảng Sudoku và không có trường hợp vi phạm quy tắc, ta trả về true, tức là bảng Sudoku là hợp lệ.

Thuật toán trên kiểm tra tính hợp lệ của bảng Sudoku bằng cách kiểm tra xem có sự trùng lặp giá trị trong cùng một hàng, cùng một cột hoặc cùng một ô con 3×3 hay không. Thuật toán này có độ phức tạp thời gian O(1) vì bảng Sudoku có kích thước cố định là 9×9.

Giải thích thuật toán bằng Java

class Solution {
  public boolean isValidSudoku(char[][] board) {
    Set<String> seen = new HashSet<>();

    for (int i = 0; i < 9; ++i)
      for (int j = 0; j < 9; ++j) {
        if (board[i][j] == '.')
          continue;
        final char c = board[i][j];
        if (!seen.add(c + "@row" + i) || //
            !seen.add(c + "@col" + j) || //
            !seen.add(c + "@box" + i / 3 + j / 3))
          return false;
      }

    return true;
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def isValidSudoku(self, board: List[List[str]]) -> bool:
    seen = set()

    for i in range(9):
      for j in range(9):
        c = board[i][j]
        if c == '.':
          continue
        if c + '@row ' + str(i) in seen or \
           c + '@col ' + str(j) in seen or \
           c + '@box ' + str(i // 3) + str(j // 3) in seen:
          return False
        seen.add(c + '@row ' + str(i))
        seen.add(c + '@col ' + str(j))
        seen.add(c + '@box ' + str(i // 3) + str(j // 3))

    return True