36. Valid Sudoku

Vui lòng đọc hiểu đề trước khi đọc bài viết này tại đây:

https://leetcode.com/problems/valid-sudoku/description/

Table of Contents

1. Cách tiếp cận vấn đề

Chắc hẳn trong chúng ta ai cũng đã từng chơi qua trò chơi Sudoku 1 lần trong đời, nhất là những thế hệ 9x đầu 2000 không thể quên được tựa game này trên những dòng điện thoại cục gạch thời xưa. Và yêu cầu của bài toán hết sức đơn giản: cho trước 1 bảng Sodoku 9x9 với các con số trên đó, và ta cần xác định xem bảng Sudoku này có hợp lệ hay không. Có 3 điều kiện để nó hợp lệ là:

• Mỗi dòng chỉ chứa các số từ 1 đến 9 và không được lặp lại
• Mỗi cột chỉ chứa các số từ 1 đến 9 và không được lặp lại
• Mỗi bảng con 3x3 chỉ chứa các số từ 1 đến 9 và không được lặp lại

Và 1 bảng sodoku được điền 1 phần cũng có thể được tính là hợp lệ mà không cần phải xét đến việc ta có thể giải tất cả con số trong bảng đó hay không và chỉ những ô có số mới được xem xét theo các điều kiện đã nêu. Ví dụ cho bảng sodoku chỉ được điền 1 phần nhưng được tính là hợp lệ:

Để giải được bài này thì chắc chắn chúng ta phải duyệt qua 81 ô (9x9) trong bảng Sudoku và chắc chắn phải sử dụng thêm bộ nhớ ngoài để lưu trữ lại các giá trị mà ta đã duyệt qua, với mỗi ô thì:

• Việc kiểm tra điều kiện cho dòng và cột khá dễ, tuy nhiên với các bảng con 3x3 thì sẽ khó hơn nhiều
• Và nếu ta phát hiện 1 ô vi phạm thì sẽ trả về false và kết thúc chương trình ngay lập tức, còn nếu như sau khi duyệt qua 81 ô mà không phát hiện ô nào vi phạm thì ta có thể trả về true và kết thúc chương trình.

2. Solution & Phân Tích

Cụ thể hơn từ ý tưởng ban đầu, ta sẽ dùng 3 mảng 2 chiều kiểu boolean, mỗi mảng lần lượt đại diện cho:

1. row[r][value]: dùng để đánh dấu lại giá trị value đã từng xuất hiện ở hàng r.
2. col[c][value]: dùng để đánh dấu lại giá trị value đã từng xuất hiện ở hàng l.
3. sub[s][value]: dùng để đánh dấu lại giá trị value đã từng xuất hiện ở bảng con 3x3 nào.

Và cụ thể hơn thì đây chính là thứ tự của các con trỏ r, c và s trong bảng Sudoku:

Vậy làm sao từ r và c, ta có thể tính ra được các index của s? Đơn giản ta chỉ cần sử dụng công thức sau: s = (r / 3) * 3 + (c / 3)

Như vậy từ 2 con trỏ r và c, ta có thể dễ dàng xác định và đánh dấu được vị trí của từng ô là thuộc về hàng nào, cột nào và bảng con 3x3 nào. Để làm được điều đó, ta sẽ dùng 2 vòng lặp với 2 con trỏ r và c để duyệt qua hết tất cả 81 ô trong bảng Sudoku này, tại mỗi ô:

• Nếu ta phát hiện giá trị của ô đó - tạm gọi là num đã tồn tại ở hàng, cột hay bảng con 3x3 có chứa ô đó, thì ta có thể kết luận ngay đây không phải là bảng Sudoku hợp lệ, trả về false và kết thúc chương trình ngay lập tức.
• Nếu chưa xuất hiện thì ta sẽ tiến hành đánh dấu vào mảng row, column, sub của num với giá trị là true, đồng nghĩa num đã được ghi nhận tồn tại với hàng, cột và bảng con 3x3 tương ứng.

Sau khi duyệt qua toàn bộ 81 ô mà không phát hiện ô nào vi phạm, ta có thể kết luận bảng Sudoku hiện tại là hợp lệ và trả về true.

Time-Complexity: O(n^2). Trong trường hợp này thì n luôn luôn bằng 9, và ta sẽ không bị phụ thuộc vào n, nên có thể rút gọn lại thành O(9^2) = O(81) = O(1)

Space-Complexity: 3xO(n^2). Tương tự như TC, vì n luôn bằng 9 nên ta sẽ không bị phụ thuộc vào n, nên có thể rút gọn lại thành 3xO(9^2) = O(81) = O(1)

3. Code

Mình sử dụng Java để minh họa cho solution trên.

Lưu ý: ch - '1' sẽ giúp biến đổi từ số ở dạng char về dạng số nguyên int. Bạn hoàn toàn có thể sử dụng các API khác để hỗ trợ làm việc này.