Mẹo

Kỹ thuật XY-Chain: Suy luận chuỗi với ô hai giá trị

2025-06-05 · 10 phút đọc
Cơ Sở Tri Thức / Mục Lục Kỹ Thuật / XY-Chain

XY-Chain là phương pháp suy luận chuỗi mạnh mẽ trong các kỹ thuật Sudoku nâng cao. Đây là phần mở rộng của XY-Wing, sử dụng cấu trúc chuỗi được hình thành bởi nhiều ô hai giá trị (ô chỉ có hai ứng viên) để loại bỏ ứng viên.

Nguyên lý cốt lõi:
XY-Chain bao gồm một chuỗi các ô hai giá trị trong đó các ô liền kề chia sẻ một ứng viên. Đầu và cuối chuỗi mỗi bên có một ứng viên không được chia sẻ. Nếu hai số này giống nhau (gọi là Z), thì các ô có thể nhìn thấy cả đầu và cuối chuỗi có thể loại bỏ ứng viên Z. Bởi vì: theo logic chuỗi, Z phải xuất hiện ở đầu hoặc cuối chuỗi.
Hoạt Hình Nguyên Lý XY-Chain
Nguyên Lý XY-Chain: Bắt đầu{Z,A} và Kết thúc{C,Z} chia sẻ ứng viên Z, Z phải ở Bắt đầu hoặc Kết thúc, loại bỏ Z khỏi vùng chung

Trước khi đọc bài viết này, nên hiểu quy ước đặt tên Sudoku, Cặp trần và cơ bản về XY-Wing.

Cấu trúc của XY-Chain

XY-Chain chứa các yếu tố quan trọng sau:

  • Nút chuỗi: Mỗi nút là một ô hai giá trị {A,B}
  • Liên kết chuỗi: Các nút liền kề phải "nhìn thấy" nhau (cùng hàng, cột hoặc ô) và chia sẻ một ứng viên
  • Đầu và cuối chuỗi: Mỗi bên có một ứng viên không được chia sẻ với nút liền kề
  • Điều kiện loại bỏ: Khi ứng viên không được chia sẻ của đầu và cuối giống nhau, có thể loại bỏ

Ký hiệu chuỗi: A(x,y) → B(y,z) → C(z,w) → ... trong đó ngoặc chứa ứng viên, mũi tên chỉ hướng chuỗi, và các nút liền kề chia sẻ một số (như y, z).

Tại sao XY-Chain hoạt động?

1 Lan truyền chuỗi: Giả sử chuỗi là A{X,Y} → B{Y,Z} → C{Z,W}. Nếu A=X, thì B phải =Z (vì B không thể =Y), rồi C phải =W (vì C không thể =Z).
2 Hai khả năng: Đầu chuỗi có hai ứng viên {P,Q}, trong đó Q được chia sẻ với nút tiếp theo. Nếu đầu=P, suy luận kết thúc; nếu đầu=Q, logic lan truyền dọc chuỗi đến cuối.
3 Kết luận quan trọng: Nếu số không được chia sẻ P của đầu chuỗi bằng số không được chia sẻ của cuối, thì P phải xuất hiện ở đầu hoặc cuối chuỗi.
4 Mục tiêu loại bỏ: Các ô có thể nhìn thấy cả đầu và cuối chuỗi không thể chứa P (vì P phải ở đầu hoặc cuối).

Ví dụ 1: XY-Chain 4 nút

Hãy xem một ví dụ XY-Chain 4 nút đơn giản.

Ví dụ XY-Chain 1
Hình 1: XY-Chain R2C2{3,7} → R2C6{3,5} → R9C6{2,5} → R9C7{2,7}, có thể loại bỏ 7 từ R2C7
Mở ví dụ này trong bộ giải

Quy trình phân tích

1 Xác định các nút chuỗi:
  • R2C2: ứng viên {3, 7} (đầu chuỗi)
  • R2C6: ứng viên {3, 5}
  • R9C6: ứng viên {2, 5}
  • R9C7: ứng viên {2, 7} (cuối chuỗi)
2 Xác minh liên kết chuỗi:
  • R2C2 và R2C6 ở cùng hàng (Hàng 2), chia sẻ ứng viên 3
  • R2C6 và R9C6 ở cùng cột (Cột 6), chia sẻ ứng viên 5
  • R9C6 và R9C7 ở cùng hàng (Hàng 9), chia sẻ ứng viên 2
3 Xác định số loại bỏ:
  • Số không được chia sẻ của đầu R2C2{3,7} = 7 (3 được chia sẻ với R2C6)
  • Số không được chia sẻ của cuối R9C7{2,7} = 7 (2 được chia sẻ với R9C6)
  • Chúng giống nhau! Z = 7
4 Quy trình suy luận:
  • Nếu R2C2=7 → 7 ở đầu chuỗi
  • Nếu R2C2=3 → R2C6 không thể là 3 → R2C6=5 → R9C6 không thể là 5 → R9C6=2 → R9C7 không thể là 2 → R9C7=7 → 7 ở cuối chuỗi
  • Trong cả hai trường hợp, 7 phải ở R2C2 hoặc R9C7
5 Tìm mục tiêu loại bỏ: R2C7 có thể nhìn thấy cả đầu chuỗi R2C2 (cùng hàng) và cuối chuỗi R9C7 (cùng cột).
Kết luận:
XY-Chain: R2C2{3,7} → R2C6{3,5} → R9C6{2,5} → R9C7{2,7}
Có thể loại bỏ ứng viên 7 từ R2C7.

Ví dụ 2: Chuỗi dài 10 nút

XY-Chain có thể rất dài. Đây là ví dụ 10 nút cho thấy khả năng mạnh mẽ của suy luận chuỗi.

Ví dụ XY-Chain 2
Hình 2: XY-Chain R2C5{1,5} → R2C1{1,5} → R1C1{5,8} → R1C7{7,8} → R3C7{7,8} → R3C2{4,8} → R7C2{4,8} → R8C1{4,8} → R8C7{4,9} → R8C3{5,9}, có thể loại bỏ 5 từ R8C5
Mở ví dụ này trong bộ giải

Quy trình phân tích

1 Xác định các nút chuỗi (10 nút):
  • R2C5: {1, 5} (đầu chuỗi)
  • R2C1: {1, 5}
  • R1C1: {5, 8}
  • R1C7: {7, 8}
  • R3C7: {7, 8}
  • R3C2: {4, 8}
  • R7C2: {4, 8}
  • R8C1: {4, 8}
  • R8C7: {4, 9}
  • R8C3: {5, 9} (cuối chuỗi)
2 Xác minh liên kết chuỗi:
  • R2C5 → R2C1: cùng hàng, chia sẻ 1 (hoặc 5)
  • R2C1 → R1C1: cùng cột, chia sẻ 5
  • R1C1 → R1C7: cùng hàng, chia sẻ 8
  • R1C7 → R3C7: cùng cột, chia sẻ 7 (hoặc 8)
  • R3C7 → R3C2: cùng hàng, chia sẻ 8
  • R3C2 → R7C2: cùng cột, chia sẻ 4 (hoặc 8)
  • R7C2 → R8C1: cùng ô, chia sẻ 8
  • R8C1 → R8C7: cùng hàng, chia sẻ 4
  • R8C7 → R8C3: cùng hàng, chia sẻ 9
3 Xác định số loại bỏ:
  • Số không được chia sẻ của đầu R2C5{1,5} = 5 (1 được chia sẻ với R2C1)
  • Số không được chia sẻ của cuối R8C3{5,9} = 5 (9 được chia sẻ với R8C7)
  • Chúng giống nhau! Z = 5
4 Kết luận suy luận: Dù đầu chuỗi R2C5 là 1 hay 5, ứng viên 5 phải xuất hiện ở đầu chuỗi R2C5 hoặc cuối chuỗi R8C3.
5 Tìm mục tiêu loại bỏ: R8C5 có thể nhìn thấy cả đầu chuỗi R2C5 (cùng cột) và cuối chuỗi R8C3 (cùng hàng).
Kết luận:
XY-Chain (10 nút): R2C5 → R2C1 → R1C1 → R1C7 → R3C7 → R3C2 → R7C2 → R8C1 → R8C7 → R8C3
Có thể loại bỏ ứng viên 5 từ R8C5.

Cách tìm XY-Chain

Tìm XY-Chain đòi hỏi cách tiếp cận có hệ thống:

1 Đánh dấu ô hai giá trị: Đầu tiên xác định tất cả các ô chỉ có hai ứng viên.
2 Chọn điểm bắt đầu: Chọn một ô hai giá trị làm đầu chuỗi, ghi lại hai ứng viên {P,Q}.
3 Mở rộng chuỗi: Tìm các ô hai giá trị có thể "nhìn thấy" nút hiện tại và chia sẻ một ứng viên làm nút tiếp theo.
4 Kiểm tra điều kiện kết thúc: Sau mỗi lần mở rộng, kiểm tra xem số không được chia sẻ của cuối có bằng số không được chia sẻ P của đầu không.
5 Tìm mục tiêu loại bỏ: Tìm các ô có thể nhìn thấy cả đầu và cuối chuỗi và chứa P.
Lưu ý quan trọng:
  • Mỗi nút trong chuỗi phải là ô hai giá trị
  • Các nút liền kề phải nhìn thấy nhau (cùng hàng, cột hoặc ô)
  • Các nút liền kề phải chia sẻ một ứng viên
  • Điều kiện loại bỏ: ứng viên không được chia sẻ của đầu và cuối giống nhau
  • XY-Wing là trường hợp đặc biệt của XY-Chain (chuỗi dài 3)

Mối quan hệ giữa XY-Chain và XY-Wing

XY-Wing có thể được xem là XY-Chain dài 3:

  • XY-Wing: Pivot{X,Y} → Wing1{X,Z} → Wing2{Y,Z}... v.v., đây thực sự không phải là dạng chuỗi tiêu chuẩn
  • Mối quan hệ thực tế: Cấu trúc XY-Wing có hình "Y", trong khi XY-Chain là tuyến tính
  • Điểm chung: Cả hai đều sử dụng ô hai giá trị cho loại bỏ logic
  • Sự khác biệt: XY-Chain yêu cầu kết nối chuỗi, XY-Wing yêu cầu pivot nhìn thấy cả hai wing

Tóm tắt kỹ thuật

Những điểm chính để áp dụng XY-Chain:

  • Yêu cầu nút: Tất cả các nút là ô hai giá trị
  • Yêu cầu kết nối: Các nút liền kề có thể nhìn thấy nhau và chia sẻ một ứng viên
  • Điều kiện loại bỏ: Ứng viên không được chia sẻ của đầu và cuối giống nhau
  • Mục tiêu loại bỏ: Ứng viên được chia sẻ trong các ô có thể nhìn thấy cả đầu và cuối
  • Độ dài chuỗi: Về lý thuyết không giới hạn, chuỗi dài hơn khó tìm hơn nhưng mạnh hơn
Thực hành ngay:
Bắt đầu một trò chơi Sudoku và thử sử dụng XY-Chain để loại bỏ! Đầu tiên tìm tất cả các ô hai giá trị, sau đó thử kết nối chúng thành một chuỗi.
XY-Wing Cặp trần Chỉ mục kỹ thuật