Tiềm kiếm

Wednesday, May 16, 2007

Trích bài viết của anh Kì Phương. Nâng cao trình độ phải đọc bài này thôi.

Giải một bài sudoku cấp độ khó :
  1. Lần này ta thử giải một bài khó xem.
  2. Lấy bài sudoku trực tuyến cao thủ số 445 làm mẫu nhé.
  3. Đề bài hãy xem hình minh hoạ bên dưới.
  1. Bắt đầu giải.
  2. Trước hết hãy áp dụng kỹ thuật (1) "ô đơn hiện" hay còn gọi là "ứng viên đơn độc".
  3. Các bạn có nhận thấy là ô C3 chỉ có thể nhận được duy nhất số 6.
  4. Tương tự như vậy đối với ô C7 chỉ nhận duy nhất số 7.
  5. Còn chờ gì nữa mà không điền số 6 vào C3 và số 7 vào C7.
  6. Tiếp đó, nếu áp dụng kỹ thuật (1), ta sẽ không tìm thêm được ô nào có chứa duy nhất 1 số để điền vào, và ta phải áp dụng các kỹ thuật khác.
  1. (Các bạn có nhận thấy ở hình này số 6 trong ô C3 và số 7 trong ô C7 đã có cỡ chữ lớn hơn so với hình cũ hay không? Đó là theo nguyên tắc khi chưa xác định được chính xác số nào trong ô nào thì tạm ghi số vào ô với cỡ chữ nhỏ, còn sau khi đã xác định rõ ràng chỉ duy nhất 1 số nào đó ở trong ô thì viết lại số đó vào ô với cỡ chữ to hơn).
  2. Hãy nhìn 2 con số 3 ở ô F8 và G9. Áp dụng kỹ thuật (2) "ô đơn ẩn", ta thấy ô A7 phải chứa số 3.
  3. Hãy nhìn 2 con số 5 ở ô D2 và I1. Áp dụng kỹ thuật (2) "ô đơn ẩn", ta thấy ô A3 phải chứa số 5.
  4. Hãy nhìn 2 con số 6 ở ô D8 và H7. Áp dụng kỹ thuật (2) "ô đơn ẩn", ta thấy ô B9 phải chứa số 6.
  5. Hãy nhìn 4 con số 5 ở ô D2, E6, C9, G8. Áp dụng kỹ thuật (2), ta thấy ô F7 phải chứa số 5.
  6. Hãy nhìn 4 con số 4 ở ô A1, G2, F5, E9. Áp dụng kỹ thuật (2), ta thấy ô D3 phải chứa số 4.
  7. Hãy nhìn 4 con số 6 ở ô E1, C3, G5, H7. Áp dụng kỹ thuật (2), ta thấy ô I2 phải chứa số 6. (thực ra không cần sử dụng đến số 6 trong ô G5).
  8. Và chắc các bạn không quên viết lại các số vừa tìm ra với cỡ chữ to lên chứ!
  1. Trong tất cả các ô trống còn lại, bạn có thể điền các ứng viên (các số có thể có trong ô) vào. Hãy xem hình trên.
  2. Đến đây kỹ thuật (1) "ô đơn hiện hoặc ứng viên đơn độc" không giúp được gì. Kỹ thuật (2) "ô đơn ẩn" cũng không phát huy tác dụng.
  3. Kỹ thuật (3) "tương tác giữa khối và hàng" (với khối A7..C9 và hàng 8) sẽ cho phép loại bỏ số 9 trong ô E8 và số 1 trong các ô E8, H8, I8.
  4. Kỹ thuật (4) "tương tác giữa các khối" (với các khối A1..C3 và khối G1..I3) sẽ cho phép loại bỏ số 9 trong các ô D1, D3, E2. Có thể áp dụng một kỹ thuật khác để loại bỏ các số 1, 9 trong ô E8 và 2 số 1 trong ô H8, I8.
  5. Đó là kỹ thuật (5) "tập hợp con hiện". Hãy nhìn hàng 8 còn 5 ô cần phải giải quyết, trong đó 2 ô A8 và B8 đều chứa và chỉ chứa 2 số 1, 9; cho nên 2 số 1 và 9 nhất định chỉ nằm trong 2 ô này và kỹ thuật (5) sẽ giúp loại bỏ số 1 và 9 trong 3 ô còn lại E8, H8, I8.
  6. Đã có thể áp dụng kỹ thuật (5) thì cũng có thể áp dụng kỹ thuật (6) "tập hợp con ẩn", tất nhiên là áp dụng 1 trong 2 thôi vì kết quả cho ra là như nhau. Cụ thể cũng xét hàng 8, có 5 ô cần xử lý, 3 số 4, 7, 8 chỉ có mặt trong 3 ô E8, H8, I8; cho nên nhất định 3 số 4, 7, 8 phải nằm trong 3 ô này và kỹ thuật (6) cho phép loại bỏ tất cả số khác 4, 7, 8 có trong 3 ô E8, H8, I8.
  7. Cũng áp dụng kỹ thuật (5) hoặc kỹ thuật (6) như trên khi xét khối A4..C6, kết quả là sẽ loại bỏ được số 1 trong ô B4 và số 2 trong ô B5.
  8. Bạn có nhận xét thế nào về việc nên áp dụng kỹ thuật (5) hay kỹ thuật (6) khi giải quyết vấn đề (vì chỉ cần áp dụng 1 trong 2 (5) hay (6) đều dẫn đến kết quả như nhau). Cấi đó là tuỳ theo thói quen và con mắt nhìn của bạn. Thông thường thì nếu số lượng ô hiện <= số lượng ô ẩn thì bộ hiện dễ phát hiện hơn; còn khi số lượng ô ẩn <= số lượng ô hiện thì tuỳ. Ví dụ 6 ô trong khối A4..C6 vừa nêu trên, có khi phát hiện ra "bộ tứ hiện" sớm hơn (4 ô A4, A5, A6, B6 chứa 4 số 1, 2, 6, 7); nhưng cũng có khi phát hiện ra "bộ đôi ẩn" sớm hơn (2 số 5, 8 chỉ xuất hiện trong 2 ô B4, B5).
  9. Giờ thì thử nhìn lại cái hình sau khi đã loại bỏ các ứng viên kể trên xem. Trông vẫn còn như cái rừng ấy nhỉ? Hãy xem hình dưới.
  1. Đến đây thì các kỹ thuật (1) (2) (3) (4) (5) (6) đã hết tác dụng. Kỹ thuật (7) "cánh bướm", thì thật không may, chẳng có đất dụng võ. Hiện trạng ô số vẫn ngổn ngang như cũ. Đành phải cầu may qua các kỹ thuật (8) "chuỗi bắt buộc", (9) "Nishio" và (10) "Thử và Sai".
  2. Hãy nhìn ô G7 có 2 ứng viên 1 và 2. Ta thử cho G7=1 xem, số 1 trong E7 sẽ bị loại bỏ, và ô F9 sẽ chứa số 1. Còn nếu ta cho G7=2 thì sao, khi đó G3=1, số 1 trong E3, F3 bị loại bỏ, ô E2 chứa số 1, như vậy số 1 trong ô E7 bị loại bỏ, và cuối cùng là F9 sẽ chứa số 1. Như vậy ô G7 chỉ có thể chứa 1 trong 2 con số 1 hoặc 2 mà với G7=1 hay G7=2 thì F9 đều =1, ta có thể mạnh dạn điền số 1 vào F9. Đây chính là áp dụng kỹ thuật (8) : chuỗi bắt buộc đấy".
  3. Thực tế thì chuỗi này chỉ áp dụng trên lý thuyết hoặc khi nghiên cứu thôi, chứ thực tiễn thì hiếm khi phải dùng đến lắm và khi giải trực tiếp thì không nên quan tâm. (Ví dụ ngay như kết quả trên, sau khi phát hiện thêm số 1 nằm trong ô F9 rồi, nhưng kết quả này cũng chẳng giúp cải thiện gì lớn cả, ngoại trừ loại bỏ thêm được con số 2 trong ô D1).
  4. Giờ thì coi lại cái hình mới xem (hình ngay bên dưới).
  1. Giờ thì thử xem kỹ thuật (9) có thể dùng được không nhé.
  2. Xét ô B4 có 2 ứng viên 5, 8. Ta thử B4=8, khi đó E5=8, suy ra F4=6, F6=9; mặt khác E5=8 suy ra D7=8, E7=9, F3=9. (Chuỗi kết quả trên chắc là các bạn thông qua được chứ). Các bạn có thấy mâu thuẫn đã xuất hiện khi số 9 vừa tồn tại duy nhất ở F3 vừa tồn tại duy nhất ở F6? Cho nên phép thử trên là sai. Vậy ô B4 không thể =8 mà phải =5.
  3. Đây có thể xem là kỹ thuật (9) hay (10) cũng được. Và đối với các bài khó thuộc hàng cao thủ thì việc phải sử dụng kỹ thuật (9) (10) là thường xuyên.
  4. Trong số các ô được chọn để thử, chỉ có một ít ô đóng vai trò là ô đột phá giúp giải quyết toàn bộ bài toán nhanh chóng, còn phần lớn ô sau khi tìm ra được số trong ô đó rồi nhưng cũng không giúp đi thêm được bao nhiêu (như việc tìm ra số 1 trong ô F9 lúc nãy, cũng như số 5 trong ô B4 vừa rồi).
  5. Chỉ có kinh nghiệm chơi cộng với may mắn sẽ giúp bạn chọn được ô đầu tiên để thử mà trúng ngay ô đột phá giải quyết nhanh toàn bộ bài toán. Tiếp tục giải cho hết bài này luôn nhé.
  6. Xem lại hình vẽ bên dưới, trong đó ô B4 đã được điền số 5, ô B5=8, ô H5=5.
  1. Tôi thấy khối G1..I3 có 2 ô có số 9 là H1 và H2. Tôi chọn số 9 ở H2.
  2. Từ H2=9 tôi thu được B1=9, E2=1. B1=9 tôi được B8=1, A8=9. Còn E2=1 (hoặc B1=9) tôi được D1=3, B2=3, E5=3, I6=3.
  3. Tạm điền các số trên vào các ô để có hình mới xem cho dễ (chú ý là đang thử ước đoán thôi nhá - thử xem có sai không ý mà - cho nên các con số mới điền chỉ có cỡ chữ nhỏ xíu.) Xem hình bên dưới.
  1. Nhìn hình minh hoạ và cùng tôi đi tiếp nhé, chú ý các ô màu tím, A2=2, A5=7, I5=2, B6=2. Lẽ ra có thể đi tiếp, nhưng để sang hình mới cho dễ nhìn hơn.
  2. Xem hình dưới sau khi đã thử điền các số vừa kể vào - vẫn là cỡ chữ nhỏ.
  1. Tiếp tục, chú ý các ô màu hồng, E8=7, D9=2, H9=7, I4=7, H6=1, H4=4, D6=7, D4=8, F4=6, F6=9, A4=1, A6=6.
  2. Tạm thế đã nhé. Chuyển sang hình mới cho dễ nhìn nào. Xem hình dưới.
  1. Tiếp tục, chú ý các ô màu xanh đậm, H8=8, I8=4, D7=9, E7=8, I7=1, I3=8, H1=2, F1=8, E3=9, F3=2, G3=1, G7=2.
  2. Ui, vậy là ra hết à! Sướng thế. Nhưng để kiểm tra lại kết quả coi có đúng hay không đây - Coi chừng mừng hụt ấy chứ. Xem hình bên dưới.
  1. May mắn quá. Vậy là đúng hết rồi.
  2. Các bạn kiểm tra ra sao? Tôi thì cộng 9 số hàng ngang và 9 số cột dọc, sẽ có được 9 kết quả của 9 hàng ngang (kết quả thấy ở các ô từ J1 đến J9) và 9 kết quả của 9 cột dọc (kết quả thấy ở các ô từ A10 đến J10). Nếu cả 18 kết quả đều bằng 45 (là tổng các số từ 1 đến 9) thì tôi hài lòng.
  3. Chấm dứt chuyển giao.

No comments: