Các kỹ thuật phổ biến để giải Sudoku
00:00:00 24/6/2023
Có nhiều kỹ thuật và chiến lược khác nhau có thể được dùng để giải các câu đố Sudoku. Dưới đây là một số cách phổ biến:
Loại trừ ứng viên
Với mỗi ô trống trên lưới Sudoku, hãy phân tích các con số trong cùng hàng, cùng cột và cùng khối để loại bỏ những số đã xuất hiện. Các số còn lại trở thành những ứng viên khả dĩ cho ô đó.
Một chiến lược cơ bản và đơn giản có thể dùng ở giai đoạn đầu của bài toán để loại bỏ các ứng viên không hợp lệ và thu hẹp khả năng.
Có thể tốn thời gian và kém hiệu quả hơn ở những câu đố phức tạp hơn, nơi cần các chiến lược nâng cao.
Ứng viên đơn (Single Candidate)
Trong một hàng, cột hoặc khối cụ thể, nếu chỉ có một con số là ứng viên khả dĩ cho một ô nhất định, thì phải điền con số đó vào ô đó.
Một chiến lược hiệu quả để tìm và điền một con số khi chỉ có duy nhất một vị trí khả dĩ cho nó.
Bị giới hạn ở các ô riêng lẻ và không thể tự mình giải được các câu đố nâng cao hơn.
Cặp/Bộ ba/Bộ bốn trần (Naked Pairs/Triplets/Quads)
Nếu có hai hoặc nhiều ô trong cùng một hàng, cột hoặc khối chứa cùng một tập hợp ứng viên gồm hai, ba hoặc bốn số, thì tất cả các lần xuất hiện khác của các ứng viên này trong cùng hàng, cột hoặc khối đó có thể bị loại bỏ.
Loại bỏ các ứng viên có thể bằng cách nhận diện các bộ số chung trong các hàng, cột và khối liên quan.
Yêu cầu ít nhất hai ô phải chứa đúng cùng một tập hợp ứng viên, điều này khá hiếm.
Ẩn đơn (Hidden Singles)
Nếu một hàng, cột hoặc khối chỉ còn lại đúng một vị trí cho một số cụ thể, thì phải điền số đó vào vị trí đó.
Cách nhanh để tìm và điền số khi chỉ còn duy nhất một vị trí khả dĩ cho một số cụ thể.
Đòi hỏi phải quan sát kỹ từng hàng, cột và khối để tìm các ứng viên đơn lẻ.
X-Wing
Nếu có hai hàng và hai cột mà chỉ có bốn ô cụ thể chứa ứng viên cho một số nào đó, thì số đó có thể bị loại khỏi tất cả các ô khác trong những hàng và cột đó.
Loại bỏ các ứng viên có thể bằng cách nhận diện các mẫu liên quan đến hai hàng và hai cột nơi một số có thể được đặt vào.
Yêu cầu sự xuất hiện của mẫu liên quan đến hai hàng và hai cột, điều này không phải lúc nào cũng có.
Cá kiếm (Swordfish)
Là phần mở rộng của kỹ thuật X-Wing, trong đó có ba hàng và ba cột mà chỉ chín ô cụ thể chứa ứng viên cho một số nhất định. Kỹ thuật này có thể loại bỏ số đó khỏi các ô khác trong các hàng và cột đó.
Giới hạn các ứng viên bằng cách nhận diện các mẫu liên quan đến ba hàng và ba cột nơi một số có thể được đặt vào.
Khó tìm hơn X-Wing, vì cần ba hàng và ba cột chia sẻ cùng một mẫu.
Sứa (Jellyfish)
Là phần mở rộng của kỹ thuật Swordfish, trong đó có bốn hàng và bốn cột mà chỉ có mười sáu ô cụ thể chứa ứng viên cho một số nhất định. Kỹ thuật này có thể loại bỏ số đó khỏi các ô khác trong các hàng và cột đó.
Nhận diện các mẫu liên quan đến bốn hàng và bốn cột nơi một số có thể được đặt vào, giúp giảm thêm các khả năng.
Hiếm khi gặp các mẫu liên quan đến bốn hàng và bốn cột.
Quay lui (Backtracking)
Khi không thể đưa ra bất kỳ suy luận logic nào, có thể dùng quay lui. Phương pháp này bao gồm việc đoán cho một ô trống và thử giải phần còn lại của bài toán. Nếu dẫn đến đáp án sai, hãy quay lui và thử một giả đoán khác. Tiếp tục cho đến khi giải xong câu đố.
Các kỹ thuật này có thể được kết hợp để giải Sudoku với nhiều mức độ khó khác nhau. Bằng cách áp dụng logic và chiến lược, lưới có thể được điền dần cho đến khi hoàn thành đúng.
Dùng khi các suy luận logic khác không còn áp dụng và cho phép đưa ra phỏng đoán để tiến về phía trước.
Có thể tốn thời gian và cần thử nhiều giả đoán khác nhau để tìm ra đáp án đúng. Nếu một giả đoán dẫn đến kết quả sai, bạn phải quay lui và thử lại một giả đoán khác.
Tóm tắt
Khi không thể đưa ra bất kỳ suy luận logic nào, có thể dùng quay lui. Phương pháp này bao gồm việc đoán cho một ô trống và thử giải phần còn lại của bài toán. Nếu dẫn đến đáp án sai, hãy quay lui và thử một giả đoán khác.
Đây chỉ là một số kỹ thuật phổ biến dùng để giải Sudoku. Mức độ khó của một câu đố cụ thể có thể yêu cầu sử dụng các chiến lược nâng cao hơn hoặc kết hợp nhiều kỹ thuật. Cũng có thể dùng các chương trình hoặc ứng dụng máy tính có thể tự động giải Sudoku bằng cách áp dụng nhiều thuật toán và chiến lược khác nhau.
Hãy nhớ rằng các kỹ thuật khác nhau sẽ hiệu quả hơn trong những tình huống và mức độ khó khác nhau. Bằng cách kết hợp nhiều kỹ thuật, bạn có thể tăng cơ hội giải được một bài Sudoku khó.