# Tại sao cần 17 manh mối? Câu đố Sudoku mà bạn không thể làm nhỏ hơn Tại sao một Sudoku cổ điển cần ít nhất 17 ô bắt đầu để có đúng một lời giải? Khám phá giới hạn, chứng minh và ý nghĩa đối với người chơi. Xóa đi một con số trong Sudoku, bạn có thể khiến nó trở nên khó hơn. Xóa nhầm con số, bạn có thể làm hỏng câu đố—mất đi đáp án duy nhất của nó. Nằm đâu đó giữa một lưới đầy đủ và một trang trắng, có một giới hạn khó: **17 manh mối ban đầu**. Tại sao Sudoku lại dừng ở đó? Câu trả lời bắt đầu bằng một câu hỏi dễ bị bỏ qua: câu đố của bạn có **chính xác một** lời giải không? ## Một lưới hoàn chỉnh, một đáp án Trong Sudoku cổ điển 9×9, mỗi hàng, mỗi cột và mỗi ô vuông 3×3 phải chứa các chữ số từ 1 đến 9 **đúng một lần**. Đây là các [quy tắc chuẩn do Nikoli công bố](https://www.nikoli.co.jp/en/puzzles/sudoku/). Những con số đã được in sẵn trong lưới được gọi là _số cho sẵn_ (givens), hay các manh mối. Một lưới đã hoàn thành có thể tuân thủ tất cả các quy tắc đó mà vẫn **không phải** là đáp án duy nhất khớp với các manh mối ban đầu. Nếu có hai cách hoàn thành khác nhau đều phù hợp, người chơi sẽ không có cách nào suy ra người ra đề thực sự muốn phương án nào. Vì thế, tính duy nhất rất quan trọng. Một Sudoku cổ điển được đặt đúng cách sẽ cung cấp đủ thông tin để xác định **chính xác một** lưới hoàn chỉnh. Nếu bạn mới học luật, bài [hướng dẫn chơi Sudoku](/en/blog/how-to-play-sudoku) của chúng tôi là một nơi tốt để bắt đầu. ## Theo dõi một manh mối thay đổi mọi thứ Đây là một câu đố được cố tình “gần xong”. Dấu chấm đánh dấu một ô trống. ```text 5 3 4 | 6 . 8 | 9 1 2 6 7 2 | 1 9 5 | 3 4 8 1 9 8 | 3 4 2 | 5 6 7 ------+-------+------ 8 5 9 | . . 1 | 4 2 3 4 2 6 | 8 5 3 | 7 9 1 7 1 3 | 9 2 4 | 8 5 6 ------+-------+------ 9 6 1 | 5 3 7 | 2 8 4 2 8 7 | 4 1 9 | 6 3 5 3 4 5 | 2 8 6 | 1 7 9 ``` Câu đố này có 78 manh mối và đúng một lời giải. Hàng trên cùng cần một số 7. Rồi hàng thứ tư cần một số 7 ở cột bốn và một số 6 ở cột năm. Giờ hãy xóa **số 6 ở hàng một, cột bốn**. Khi đó có bốn ô trống, và có **hai** cách sắp xếp phù hợp: | Ô | Phương án A | Phương án B | | ------------- | ----------- | ----------- | | Hàng 1, cột 4 | 6 | 7 | | Hàng 1, cột 5 | 7 | 6 | | Hàng 4, cột 4 | 7 | 6 | | Hàng 4, cột 5 | 6 | 7 | Mọi số còn lại giữ nguyên. Cả hai phương án đều thỏa mãn mọi hàng, mọi cột, từng ô vuông 3×3 và tất cả các manh mối còn lại. Bốn ô đó tạo thành một hình chữ nhật, trong đó các số 6 và 7 có thể đổi chỗ cho nhau mà không vi phạm bất kỳ quy tắc nào. Chúng tôi đã kiểm tra số lượng lời giải: câu đố ban đầu có đúng một cách hoàn thành; sau khi xóa, nó có đúng hai cách. Việc xóa một manh mối không thể làm “hỏng” một lời giải vốn đã đúng: lời giải đó vẫn thỏa mãn tất cả các manh mối còn lại. Điều mà việc xóa có thể làm là mở ra một đáp án khác. Ngay cả câu đố này—với 77 số cho sẵn—vẫn mơ hồ, nên chỉ riêng số lượng manh mối nhiều vẫn không thể đảm bảo tính duy nhất. ## Tại sao 17 là mức tối thiểu Gary McGuire, Bastian Tugemann và Gilles Civario đã chứng minh rằng **không có** Sudoku cổ điển 9×9 nào với **16 manh mối** mà lại có **đúng một** lời giải. Bài [nghiên cứu gốc của họ](https://arxiv.org/abs/1201.0749) mô tả việc tìm kiếm toàn diện bằng máy tính. Có những câu đố 17 manh mối có thể giải duy nhất, vì vậy 17 chính là mức tối thiểu. Điều này không có nghĩa là mọi cách sắp xếp của 17 con số đều tạo thành một câu đố hợp lệ. Vị trí và giá trị của chúng quan trọng. Kết quả cũng chỉ nói về Sudoku cổ điển; các quy tắc bổ sung trong biến thể sẽ làm thay đổi bài toán. Tại sao loại bỏ trường hợp 16 cũng loại bỏ luôn các số nhỏ hơn? Nếu một câu đố nhỏ hơn có một lời giải duy nhất, bạn có thể thêm các manh mối đúng từ lời giải đó cho đến khi nó có 16. Việc thêm các manh mối đó sẽ giữ nguyên đáp án duy nhất, mâu thuẫn với kết quả đã nêu. ## Làm sao để chứng minh rằng không tồn tại câu đố nhỏ hơn? Tìm được một câu đố 17 manh mối cho thấy điều gì là có thể. Chứng minh rằng 16 không thể xảy ra nghĩa là phải loại trừ mọi khả năng. Các nhà nghiên cứu đã tìm kiếm có hệ thống các lưới đã hoàn thành, tính đến các lưới tương đương. Phương pháp của họ dùng _các tập không thể tránh khỏi_ (_unavoidable sets_): các nhóm ô bắt buộc phải chứa một manh mối để ngăn một lời hoàn thành khác. Họ phát triển một thuật toán hiệu quả để liệt kê _hitting sets_—những cách chọn cắt qua (chạm vào) các nhóm đó—rồi kiểm tra các tập manh mối ứng viên xem có tính duy nhất hay không. [Bài báo giải thích phương pháp](https://arxiv.org/html/1201.0749v2). Hình chữ nhật ở trên minh họa nhỏ cho ý tưởng đó. Hãy để cả bốn ô không có manh mối và hai cách sắp xếp vẫn tồn tại. Chỉ cần cố định ít nhất một trong các ô đó là bạn chặn ngay phép đổi chỗ cụ thể ấy. Trong một câu đố thưa, có rất nhiều phương án thay thế tiềm năng—và chúng phải bị chặn đồng thời. ## Số manh mối tối thiểu không đồng nghĩa với độ khó tối đa Số lượng manh mối trả lời câu hỏi “thông tin được in ra nhiều đến mức nào?”. Nó không cho bạn biết suy luận tiếp theo bạn sẽ nhận ra là gì. Việc đếm các số cho sẵn không nói rằng nước đi tiếp theo là một bước “chỉ có một lựa chọn” hiển nhiên hay một kiểu mẫu mà bạn chưa từng học. Có một phân biệt khác cũng rất hữu ích: _minimum_ và _minimal_. _Minimum_ là số manh mối ít nhất có thể trong Sudoku cổ điển. Một câu đố _minimal_ là câu đố mà khi xóa bất kỳ manh mối nào, tính duy nhất sẽ mất. Gọi một câu đố là minimal không có nghĩa là nó có 17 manh mối. Với ván tiếp theo của bạn, hãy thử giải thích từng phép đặt trước khi điền: “Đây là ô duy nhất trong ô vuông đó có thể chứa số 4.” Nếu bạn chưa thể giải thích một nước đi, hãy kiểm tra các ứng viên hoặc thử một kỹ thuật từ [hướng dẫn giải Sudoku](/en/blog/common-techniques-for-solving-sudoku) của chúng tôi. Lần tới khi bạn gặp một Sudoku thưa, hãy đếm các manh mối—rồi tìm hiểu vì sao mỗi manh mối đó lại quan trọng.