Skip to main content

[M] Valid Sudoku

Đề bài

Hãy xét xem một bảng Sudoku 9x9 có hợp lệ hay không. Chỉ những ô đã được điền cần được đánh giá theo các quy tắc sau:

  • Mỗi hàng phải chứa các chữ số từ 1-9 mà không có chữ số nào lặp lại.
  • Mỗi cột phải chứa các chữ số từ 1-9 mà không có chữ số nào lặp lại.
  • Mỗi ô 3x3 phải chứa các chữ số từ 1-9 mà không có chữ số nào lặp lại.

Lưu ý:

  • Một bảng Sudoku hợp lệ không nhất thiết phải là một bảng có thể giải được.
  • Chỉ cần xác định xem các ô đã điền hợp lệ hay không.

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

Constraints

  • board.length == 9
  • board[i].length == 9
  • board\[i\]\[j\] is a digit 1-9 or '.'.

Phân tích

Đối với bài toán kiểm tra tính lặp lại thì ta thường dùng map/set để lưu trữ các giá trị đã xuất hiện vì có thể kiểm tra nhanh chóng với độ phức tạp O(1).

Vì board có kích thước cố định là 9x9 nên ta cần 9 map/set để kiểm tra cho hàng, 9 map/set cho cột và 9 map/set cho ô 3x3.

Và điểm mấu chốt là cần xác định được ô đang xét thuộc map/set nào.

Pseudocode

Function is_valid_sudolu(board):
rows = Array(9).fill(new Set())
cols = Array(9).fill(new Set())
boxes = Array(9).fill(new Set())

For i = 0 to 8:
For j = 0 to 8:
If board[i][j] != '.':
num = board[i][j]
boxIndex = Math.floor(i / 3) * 3 + Math.floor(j / 3)
If rows[i].has(num) OR cols[j].has(num) OR boxes[boxIndex].has(num):
Return false
rows[i].add(num)
cols[j].add(num)
boxes[boxIndex].add(num)
Return true

Solution

class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<unordered_set<char>> rows(9);
vector<unordered_set<char>> cols(9);
vector<unordered_set<char>> boxes(9);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
char num = board[i][j];
int boxIndex = (i / 3) * 3 + j / 3;
if (rows[i].count(num) || cols[j].count(num) || boxes[boxIndex].count(num)) {
return false;
}
rows[i].insert(num);
cols[j].insert(num);
boxes[boxIndex].insert(num);
}
}
}
return true;
}
};