Tập con trần

Tập con trần trong Sudoku là gì?

Một tập hợp trần là một nhóm gồm N ô trong cùng một nhà (hàng, cột hoặc khối) mà các ứng cử viên kết hợp chứa đúng N chữ số khác nhau. Vì N chữ số này phải điền vào N ô đó, nên chúng không thể xuất hiện trong bất kỳ ô nào khác Ô trong nhà đó. Điều này cho phép bạn loại bỏ an toàn các chữ số đó khỏi các ô còn lại. Từ "trần" có nghĩa là các ứng cử viên được hiển thị rõ ràng và trực tiếp. Bạn không cần phải tìm kiếm các chữ số bị ẩn giữa các ứng cử viên khác. Tập hợp này tự công khai bản chất của nó thông qua các ghi chú chì trong các ô đó. Có bốn kỹ thuật tập hợp trần, một cho mỗi kích thước nhóm khả dĩ: - Số đơn trần (N=1) -- một ô có một ứng cử viên - Cặp trần (N=2) -- hai ô mà các ứng cử viên kết hợp đúng bằng hai chữ số - Ba số trần (N=3) -- ba ô mà các ứng cử viên kết hợp đúng bằng ba chữ số - Tứ giác trần (N=4) -- bốn ô mà các ứng cử viên kết hợp đúng bằng bốn chữ số Bốn kỹ thuật này tạo thành một gia đình. Chúng chia sẻ cùng một nguyên lý nền tảng và chỉ khác nhau ở số lượng ô tham gia. Một khi bạn hiểu được nguyên lý cốt lõi, các tập hợp lớn hơn sẽ trở thành sự mở rộng tự nhiên của các tập hợp đơn giản hơn.

Nguyên tắc cốt lõi: Tại sao các tập con trần hoạt động

Lý do đằng sau các tập hợp trần nằm ở một lập luận đếm cơ bản nào đó được gọi là nguyên lý chuồng bồ câu. Nói một cách đơn giản: nếu bạn có N ô trống và đúng N đối tượng để điền vào chúng, mỗi đối tượng sẽ đi vào đúng một ô, và không có đối tượng nào khác có thể chiếm các ô đó. Xét một hàng gồm chín ô. Mỗi ô chưa giải có một tập hợp các chữ số khả dĩ, những ghi chú chì có thể điền hợp lệ vào ô đó. Giả sử bạn tìm thấy hai ô trong hàng này mà các chữ số khả dĩ đều được lấy từ cùng một tập hai chữ số, ví dụ {4, 6}. Một trong hai ô này phải chứa số 4 và ô kia phải chứa số 6. Không còn chỗ nào cho bất kỳ cách sắp xếp nào khác. Điều này có nghĩa là không ô nào khác trong hàng có thể chứa số 4 hoặc 6, vì cả hai chữ số này đã được xác định hoàn toàn bởi hai ô này. Lập luận này có thể mở rộng. Ba ô có tổng số chữ số khả dĩ đúng bằng ba chữ số sẽ khóa ba chữ số này vào ba ô đó. Bốn ô với bốn chữ số khả dĩ tổng cộng sẽ khóa cả bốn chữ số. Trong mọi Ô, các chữ số bị khóa có thể được loại bỏ khỏi tất cả các ô khác trong cùng một nhà chung. Nguyên lý này áp dụng giống nhau dù nhà là hàng, cột hay khối 3x3. Yêu cầu duy nhất là tất cả N ô phải thuộc cùng một nhà.

Số đơn trần: Nền tảng của việc giải Sudoku

Một Số đơn trần là tập con trần đơn giản nhất. Nó xảy ra khi một Ô chỉ còn lại một lựa chọn khả dĩ trong các ghi chú chì. Vì chỉ có một chữ số hợp lệ có thể đi vào Ô này, chữ số đó chính là lời giải cho Ô. Mọi người chơi Sudoku, dù con người hay thuật toán, đều dựa vào các chữ số trần đơn. Chúng là bước cuối cùng trong chuỗi loại bỏ: sau khi tất cả các ràng buộc từ hàng, cột và khối đã loại bỏ các chữ số không thể, lựa chọn còn lại cuối cùng chính là câu trả lời. Việc tìm ra một Số đơn trần đòi hỏi bạn phải theo dõi cẩn thận các ghi chú chì cho từng Ô. Một Ô ban đầu có tối đa chín lựa chọn khả dĩ. Khi bạn đặt các chữ số ở các vị trí khác trên bảng, các lựa chọn sẽ bị loại bỏ: - Nếu một chữ số được đặt ở bất kỳ vị trí nào trong cùng hàng, hãy loại nó khỏi các lựa chọn của Ô. - Nếu một chữ số được đặt ở bất kỳ vị trí nào trong cùng cột, hãy loại nó khỏi các lựa chọn của Ô. - Nếu một chữ số được đặt ở bất kỳ vị trí nào trong cùng khối 3x3, hãy loại nó khỏi các lựa chọn của Ô. Khi các loại bỏ này làm giảm một Ô xuống còn một lựa chọn duy nhất, bạn đã tìm thấy một Số đơn trần. Xét Ô R5C3 trong một bảng đã được giải một phần. Các ràng buộc từ hàng, cột và khối loại bỏ các chữ số sau: - Hàng 5 đã chứa: 1, 3, 5, 8 - Cột 3 đã chứa: 2, 6, 9 - Khối 4 (khối giữa trái) đã chứa: 7 Kết hợp lại, các chữ số 1, 2, 3, 5, 6, 7, 8 và 9 đều bị loại bỏ. Chữ số duy còn lại là 4. Ô R5C3 phải là 4. Đây là một Số đơn trần. Các chữ số trần đơn nên là bước kiểm tra đầu tiên sau mỗi nước đi. Mỗi lần bạn đặt một chữ số, nó có thể làm giảm các ô kề cận xuống còn một lựa chọn duy nhất. Trong các bảng dễ, chuỗi các chữ số trần đơn có thể giải được một phần lớn bảng mà không cần đến bất kỳ kỹ thuật nào khác. Ngay cả trong các bảng khó, các chữ số trần đơn cũng giúp làm sạch bảng sau khi các kỹ thuật nâng cao đã loại bỏ các lựa chọn.

Cặp trần: Hai ô, hai ứng viên, loại bỏ mạnh mẽ

Một cặp trần xảy ra khi hai ô trong cùng một nhà mỗi ô chỉ chứa đúng hai lựa chọn giống nhau và không có lựa chọn nào khác. Vì hai chữ số này phải đi vào hai ô này, bạn có thể loại bỏ cả hai chữ số này khỏi mọi ô khác trong nhà đó. Cặp trần là một trong những chiến lược trung cấp thường được áp dụng nhất. Chúng xuất hiện thường xuyên và thường giúp tiến bộ đáng kể bằng cách loại bỏ các lựa chọn cản trở các kỹ thuật khác. Giả sử hai ô trong hàng 1 đều chứa các lựa chọn {4, 6} và không có lựa chọn nào khác: - R1C2 có các lựa chọn: {4, 6} - R1C7 có các lựa chọn: {4, 6} Một trong hai ô này sẽ là 4 và ô kia sẽ là 6. Chúng ta chưa biết cái nào là cái nào, nhưng chắc chắn rằng 4 và 6 đã được sử dụng hết bởi hai ô này. Do đó, không ô nào khác trong hàng 1 có thể chứa 4 hoặc 6. Nếu R1C4 có các lựa chọn {3, 4, 6, 9}, nó có thể được giảm xuống thành {3, 9} bằng cách loại bỏ 4 và 6. Nếu R1C8 có các lựa chọn {2, 6}, nó có thể được giảm xuống thành {2}. Việc giảm xuống còn một lựa chọn duy nhất chính là một kỹ thuật Số đơn trần, giúp giải ngay ô đó. Duyệt qua từng nhà để tìm các ô chỉ có đúng hai lựa chọn. Khi bạn tìm thấy hai ô trong cùng một nhà có cùng tập hợp hai lựa chọn, bạn đã tìm thấy một cặp trần. Vì các ô chỉ có hai ghi chú chì nổi bật về mặt thị giác, cặp trần là một trong những kỹ thuật trung cấp dễ nhận biết nhất. Một thói quen hữu ích: mỗi khi bạn nhận thấy một ô có chỉ hai lựa chọn, hãy ngay lập tức kiểm tra xem có ô nào khác trong cùng hàng, cột hoặc khối có cùng cặp lựa chọn hay không.

Ba số trần: Ba ô, ba ứng viên, một mẹo tinh tế

Một Ba số trần xảy ra khi ba ô trong cùng một nhà có các ứng cử viên được chọn hoàn toàn từ cùng một tập hợp gồm đúng ba chữ số. Tập hợp hợp của tất cả các ứng cử viên trên ba ô này chứa đúng ba chữ số phân biệt. Đây là chìa khóa giúp nhiều người chơi bị bất ngờ: mỗi Ô riêng lẻ không cần phải chứa đủ ba chữ số. Một Ba số trần hợp lệ có thể bao gồm các ô chỉ chứa hai trong ba chữ số. Điều quan trọng là hợp của tất cả các ứng cử viên trên ba ô phải đúng bằng ba giá trị phân biệt. Nhiều người chơi học cặp trần trước, rồi cho rằng bộ ba trần cần ba ô mỗi ô chứa cùng ba ứng cử viên, như {1, 3, 7} ở cả ba ô. Dù điều đó là một dạng hợp lệ của Ba số trần, nhưng không phải là dạng duy nhất, và cũng không phải dạng phổ biến nhất. Xem xét ba ô này trong cột 5: - R2C5: {1, 3} - R4C5: {1, 7} - R8C5: {3, 7} Các ứng cử viên hợp lại là {1, 3, 7}, đúng bằng ba chữ số trong ba ô. Đây là một Ba số trần hợp lệ, dù không có ô nào trong ba ô này chứa đủ ba chữ số. Lý luận tương tự như cặp trần. Ba chữ số này phải điền vào ba ô này theo một thứ tự nào đó. Một Ô sẽ nhận 1, một ô nhận 3, một ô nhận 7. Do đó, 1, 3 và 7 có thể bị loại khỏi mọi Ô khác trong cột 5. Bắt đầu bằng cách xác định các ô có hai hoặc ba ứng cử viên. Trong một nhà nhất định, nếu bạn tìm thấy ba ô mà tập hợp ứng cử viên của chúng tạo thành một tập hợp đúng ba chữ số, bạn đã tìm thấy một Ba số trần. Một cách tiếp cận thực tế: 1. Trong mỗi nhà, liệt kê tất cả các ô chưa giải có ba ứng cử viên hoặc ít hơn. 2. Chọn bất kỳ tổ hợp nào gồm ba ô như vậy. 3. Lấy hợp của các ứng cử viên. Nếu hợp có đúng ba chữ số, thì đó là một Ba số trần. Vì có nhiều tổ hợp khả dĩ, bộ ba trần đòi hỏi quan sát cẩn thận hơn cặp trần. Đây là một phần lý do vì sao đây là kỹ thuật khó hơn.

Tứ giác trần: Bốn ô, bốn ứng viên, độ phức tạp tối đa

Một Tứ giác trần là tập con trần lớn nhất thường được sử dụng. Hiện tượng này xảy ra khi bốn ô trong một nhà có các ứng cử viên được chọn hoàn toàn từ cùng một tập hợp đúng bốn chữ số. Giống như bộ ba, từng ô riêng lẻ không cần phải chứa đủ bốn chữ số. Điều kiện then chốt là hợp của các ứng cử viên trên cả bốn ô phải đúng bằng bốn giá trị phân biệt. Lập luận là giống hệt như các tập con trần nhỏ hơn. Bốn chữ số phải điền vào bốn ô. Những chữ số này không thể xuất hiện ở bất kỳ đâu khác trong nhà. Các bộ bốn trần rất hiếm khi được phát hiện qua quan sát thông thường. Với bốn ô và bốn chữ số, có rất nhiều tổ hợp cần kiểm tra. Trong một nhà có sáu ô chưa giải, có 15 cách chọn bốn ô. Việc kiểm tra từng tổ hợp trong đầu là rất nhàm chán. Hầu hết người giải thường tìm thấy bộ bốn trần bằng cách kiểm tra hệ thống hoặc trước tiên nhận ra rằng các ô còn lại tạo thành một tập con ẩn bổ sung. Mặc dù hiếm, bộ bốn trần vẫn xuất hiện trong các bài toán thực tế, đặc biệt là những bài có độ khó trung bình đến khó. Việc có kỹ thuật này trong bộ công cụ sẽ giúp bạn không bị kẹt khi các kỹ thuật đơn giản đã được loại bỏ.

Làm thế nào để phát hiện các tập con trần: Mẹo quét thực tế

Việc tìm kiếm các tập con trần hiệu quả đòi hỏi một cách tiếp cận có cấu trúc thay vì quét ngẫu nhiên. Dưới đây là các kỹ thuật mà những người giải chuyên nghiệp thường sử dụng: Bắt đầu với số lượng ứng viên nhỏ: Các ô có ít ứng viên hơn thường có khả năng tham gia vào các tập con trần. Một ô có hai ứng viên có thể là một cặp, bộ ba hoặc bộ bốn. Một ô có năm ứng viên ít hữu ích hơn vì nó góp phần quá nhiều chữ số vào tập hợp. Hãy quét từng nhà để tìm các ô có hai ứng viên trước. Kiểm tra các cặp trùng khớp. Sau đó, xem xét các ô có hai hoặc ba ứng viên cùng nhau để tìm bộ ba. Làm theo từng nhà: Chọn một hàng, cột hoặc khối và xem xét tất cả các ô chưa giải cùng nhau. Liệt kê các ứng viên của chúng. Tìm các cụm ô mà các ứng viên của chúng giao nhau trong một tập nhỏ các chữ số. Sử dụng kiểm tra đếm: Với bất kỳ nhóm N ô nào bạn nghi ngờ có thể tạo thành một tập con trần, hãy đếm số chữ số khác nhau trong tập hợp các ứng viên. Nếu số đếm bằng N, bạn đã tìm thấy một tập con trần. Nếu số đếm vượt quá N, những ô này không phải là một tập con trần. Kiểm tra sau mỗi lần loại bỏ: Khi một kỹ thuật khác loại bỏ các ứng viên khỏi một ô, hãy kiểm tra lại nhà của ô đó. Việc loại bỏ có thể đã tạo ra một tập con trần mới mà trước đó chưa thấy. Nhiều cặp trần xuất hiện như một hệ quả phụ của các loại bỏ trước đó. Tìm tập hợp bù: Nếu một nhà có K ô chưa giải và bạn nghi ngờ một tập con trần tồn tại nhưng không thể tìm thấy trực tiếp, hãy thử tìm tập hợp bù. Việc tìm thấy một tập con ẩn có kích thước M sẽ ngầm chỉ ra một tập con trần có kích thước K - M.

Mối quan hệ giữa các tập hợp trần và các tập hợp ẩn

Các tập con trần và các tập con ẩn là hai mặt của cùng một đồng xu. Hiểu được sự đối xứng này sẽ giúp bạn nắm vững sâu sắc hơn về logic Sudoku và có thể giúp bạn phát hiện ra các mẫu mà có thể bạn sẽ bỏ lỡ. Một tập con ẩn xảy ra khi N chữ số trong một nhà chỉ xuất hiện trong đúng N ô nhất định. Các chữ số này bị "ẩn" vì những ô đó có thể chứa thêm các lựa chọn khác. Việc loại bỏ sẽ loại bỏ các lựa chọn thừa khỏi N ô đó, chỉ để lại các chữ số ẩn. Trong bất kỳ nhà nào có K ô chưa giải, nếu có một tập con trần kích thước N, thì sẽ tự động tồn tại một tập con ẩn kích thước K - N. Hai tập con này bổ sung cho nhau: chúng chia tách các ô chưa giải và các chữ số còn lại thành hai nhóm không giao nhau. Ví dụ, xét một hàng có 6 ô chưa giải. Nếu hai trong số các ô đó tạo thành một Cặp trần, thì bốn ô còn lại sẽ tạo thành một Bốn ẩn (hoặc tương đương, một Tứ giác trần tồn tại trong các chữ số bị loại khỏi bốn ô này). Bạn có thể tìm thấy một trong hai và áp dụng các loại bỏ tương ứng. Sự đối xứng này có nghĩa là bạn có hai con đường dẫn đến cùng một loại bỏ. Nếu một nhà có nhiều ô chưa giải, một tập con trần nhỏ (cặp hoặc bộ ba) sẽ dễ nhìn thấy hơn so với một tập con ẩn lớn. Ngược lại, nếu một nhà chỉ có ít ô chưa giải, một Cặp ẩn có thể dễ tìm hơn là phải tìm tập con Tứ giác trần bổ sung. Những người chơi có kinh nghiệm thường chuyển đổi giữa quan điểm trần và quan điểm ẩn tùy theo tình huống nào thực tế hơn. Khả năng nhìn thấy cả hai mặt sẽ mang lại cho bạn một lợi thế đáng kể.

Mức độ khó tăng dần: Từ người mới bắt đầu đến nâng cao

Bốn kỹ thuật tập hợp trần bao gồm nhiều cấp độ khó khác nhau, phản ánh mức độ khó hơn khi kích thước nhóm tăng lên: Số đơn trần (N=1): Cấp độ 2, Dễ Cặp trần (N=2): Cấp độ 3, Dễ Ba số trần (N=3): Cấp độ 4, Trung bình Tứ giác trần (N=4): Cấp độ 5, Khó Sự gia tăng độ khó không liên quan đến logic, vốn giống nhau trong mọi Ô, mà liên quan đến độ phức tạp khi tìm kiếm: Số đơn trần: Bạn chỉ cần kiểm tra một Ô. Nếu nó có một ứng viên, bạn đã xong. Không cần tìm tổ hợp. Cặp trần: Bạn cần tìm hai ô có cùng các ứng viên. Trong một nhà với sáu ô chưa giải, có 15 cặp khả dĩ để kiểm tra. Nhưng vì bạn đang tìm các ô có đúng hai ứng viên giống nhau, mẫu hình thị giác là đặc trưng và dễ nhận biết. Ba số trần: Bạn cần tìm ba ô có tổng các ứng viên là ba chữ số. Trong một nhà với sáu ô chưa giải, có 20 bộ ba khả dĩ. Việc tìm kiếm khó hơn vì các ô không cần có tập ứng viên giống nhau. Tứ giác trần: Bạn cần tìm bốn ô từ số lượng ô chưa giải có thể rất lớn. Số lượng tổ hợp tăng lên, và việc tính toán hợp tập bốn chữ số trở nên khó hơn khi thực hiện trong đầu. Hầu hết các bộ bốn được phát hiện gián tiếp, thông qua đếm ứng viên hệ thống hoặc nhận diện bộ bù Cặp ẩn. Xếp hạng độ khó của các bài toán thường phụ thuộc vào kỹ thuật nào được yêu cầu để giải. Một bài toán chỉ cần các kỹ thuật đơn giản như số trần đơn và cặp trần được xếp là dễ. Một bài toán yêu cầu bộ ba trần thuộc vùng trung bình. Một bài toán đòi hỏi một Tứ giác trần là ít nhất ở mức khó.

Những sai lầm phổ biến và cách tránh chúng

Lỗi 1: Mong đợi tất cả các ô chứa tất cả các chữ số Sai lầm phổ biến nhất với các bộ ba và bộ bốn trần là giả định rằng mọi Ô trong tập con phải chứa đủ N chữ số. Điều này là sai. Một Ba số trần với các ô {1,3}, {1,7}, và {3,7} là hoàn toàn hợp lệ ngay cả khi không có Ô nào chứa đủ cả 1, 3 và 7. Cách tránh: Luôn kiểm tra hợp của các chữ số khả dụng, chứ không phải từng ô riêng lẻ. Đếm số chữ số khác nhau trong toàn bộ các ô của nhóm. Nếu số lượng này bằng số lượng ô, thì đó là một tập con trần, bất kể cách phân bố các chữ số trong từng ô. Lỗi 2: Nhầm lẫn giữa tập con trần và tập con ẩn Một Cặp trần có N ô với các chữ số khả dụng giới hạn trong N chữ số. Một Cặp ẩn có N chữ số bị giới hạn trong N ô, nhưng các ô này có thể chứa thêm các chữ số khả dụng khác. Với một Cặp trần, bạn loại bỏ các chữ số cặp khỏi các ô khác trong cùng nhà. Với một Cặp ẩn, bạn loại bỏ các chữ số không phải cặp khỏi chính các ô của cặp. Cách tránh: Hãy tự hỏi bản thân: "Tôi đang xem xét các ô có chữ số khả dụng bị giới hạn (trần) hay các chữ số có vị trí bị giới hạn (ẩn)?" Hướng của sự giới hạn sẽ xác định loại tập con bạn đang tìm. Lỗi 3: Loại bỏ từ các ô sai Khi bạn tìm thấy một Cặp trần {4, 6} ở các ô R1C2 và R1C7, bạn loại bỏ 4 và 6 khỏi các ô khác trong hàng 1. Bạn không loại bỏ các chữ số khác khỏi chính R1C2 và R1C7. Các chữ số khả dụng của Cặp trần vẫn giữ nguyên trong chính các ô của tập con. Cách tránh: Hãy nhớ quy tắc: tập con trần loại bỏ các chữ số của nó khỏi các ô bên ngoài tập con. Tập con ẩn loại bỏ các chữ số không thuộc tập con khỏi các ô bên trong tập con. Lỗi 4: Quên kiểm tra tất cả các nhà chung Hai ô có thể chung nhiều nhà. Ví dụ, R1C1 và R1C3 chung cả hàng 1 và khối 1. Nếu chúng tạo thành một Cặp trần, bạn có thể loại bỏ các chữ số cặp khỏi các ô khác trong hàng 1 và khỏi các ô khác trong khối 1. Đừng giới hạn loại bỏ chỉ trong một nhà. Cách tránh: Với mỗi tập con trần bạn tìm thấy, hãy kiểm tra xem các ô của tập con chung nhà nào. Áp dụng loại bỏ trong từng nhà chung.

Khi nào nên sử dụng các tập con trần trong quy trình giải của bạn

Các tập con trần nên được kiểm tra theo thứ tự từ nhỏ nhất đến lớn nhất: 1. Trước hết là các số đơn trần. Sau mỗi lần điền, hãy quét lại để tìm các số đơn trần mới. Chúng miễn phí và tức thì. 2. Thứ hai là các cặp trần. Khi không còn số đơn trần nào, hãy quét tìm các cặp trần trong mọi hàng, cột và khối. Đây là kỹ thuật trung gian phổ biến nhất và thường mở ra các số đơn trần tiếp theo. 3. Thứ ba là các bộ ba trần. Khi cặp trần không đủ, hãy mở rộng tìm kiếm sang bộ ba. Tập trung vào các nhà (hàng, cột, khối) mà nhiều ô có hai hoặc ba khả năng. 4. Cuối cùng là các bộ bốn trần. Chỉ tìm kiếm bộ bốn khi đã loại bỏ hoàn toàn các tập con nhỏ hơn và các kỹ thuật khác. Do độ khó cao, hãy cân nhắc kiểm tra các cặp hoặc bộ ba ẩn trước, vì chúng có thể dễ tìm hơn và cung cấp cùng thông tin nhờ nguyên lý đối ngẫu. Bằng cách tuân theo trình tự này, bạn áp dụng các kỹ thuật dễ nhất và hiệu quả nhất trước, tiết kiệm sức não cho những lúc thực sự cần thiết.

Tóm tắt

Các tập con trần là một họ bốn kỹ thuật Sudoku được thống nhất bởi một nguyên lý thanh lịch duy nhất: N ô trong một nhà với đúng N ứng cử viên kết hợp sẽ khóa các chữ số đó lại, cho phép bạn loại bỏ chúng khỏi tất cả các ô khác trong nhà. Từ Số đơn trần khiêm tốn giúp giải một Ô ngay lập tức, qua các cặp và bộ ba trần loại bỏ các ứng cử viên, đến Tứ giác trần khó nắm bắt đòi hỏi tìm kiếm có hệ thống cẩn thận, các kỹ thuật này tạo thành nền tảng cho việc giải logic Sudoku. Nắm vững chúng sẽ mang lại cho bạn những công cụ đáng tin cậy áp dụng cho các bài toán ở mọi cấp độ khó và xây dựng nền tảng để tiếp cận các chiến lược nâng cao hơn như tập con ẩn, mẫu cá, và chuỗi.