İpuçları

XY-Chain Tekniği: İki Değerli Hücrelerle Zincir Akıl Yürütme

2025-06-05 · 10 dk okuma
Bilgi Tabanı / Teknikler İndeksi / XY-Chain

XY-Chain, ileri Sudoku teknikleri arasında güçlü bir zincir akıl yürütme yöntemidir. XY-Wing'in bir uzantısıdır ve birden fazla iki değerli hücre (sadece iki adayı olan hücreler) tarafından oluşturulan zincir yapıları kullanarak aday elemesi yapar.

Temel Prensip:
Bir XY-Chain, bitişik hücrelerin bir adayı paylaştığı bir dizi iki değerli hücreden oluşur. Zincirin başı ve sonu her biri paylaşılmayan bir adaya sahiptir. Bu iki sayı aynıysa (Z olarak adlandırılır), o zaman hem zincir başını hem de zincir sonunu görebilen hücreler Z adayını eleyebilir. Çünkü: zincir mantığını takip ederek, Z ya zincir başında ya da zincir sonunda görünmelidir.
XY-Zincir Prensibi Animasyonu
XY-Zincir Prensibi: Başlangıç{Z,A} ve Bitiş{C,Z} aday Z'yi paylaşır, Z Başlangıç veya Bitişte olmalı, ortak görünür alandan Z'yi eleyin

Bu makaleyi okumadan önce, Sudoku adlandırma kurallarını, Çıplak İkililer ve XY-Wing temellerini anlamanız önerilir.

XY-Chain Yapısı

XY-Chain şu anahtar öğeleri içerir:

  • Zincir Düğümleri: Her düğüm iki değerli bir hücredir {A,B}
  • Zincir Bağlantıları: Bitişik düğümler birbirini "görmeli" (aynı satır, sütun veya kutu) ve bir adayı paylaşmalıdır
  • Zincir Başı ve Sonu: Her biri bitişik düğümle paylaşılmayan bir adaya sahiptir
  • Eleme Koşulu: Baş ve sonun paylaşılmayan adayları aynı olduğunda, eleme mümkündür

Zincir gösterimi: A(x,y) → B(y,z) → C(z,w) → ... burada parantezler adayları içerir, oklar zincir yönünü gösterir ve bitişik düğümler bir sayıyı paylaşır (y, z gibi).

XY-Chain Neden Çalışır?

1 Zincir Yayılımı: Zincirin A{X,Y} → B{Y,Z} → C{Z,W} olduğunu varsayalım. A=X ise, o zaman B=Z olmalı (çünkü B=Y olamaz), sonra C=W olmalı (çünkü C=Z olamaz).
2 İki Olasılık: Zincir başının iki adayı {P,Q} vardır, burada Q bir sonraki düğümle paylaşılır. Baş=P ise, akıl yürütme biter; baş=Q ise, mantık zincir boyunca sona kadar yayılır.
3 Anahtar Sonuç: Zincir başının paylaşılmayan sayısı P, zincir sonunun paylaşılmayan sayısına eşitse, o zaman P ya zincir başında ya da sonunda görünmelidir.
4 Eleme Hedefi: Hem zincir başını hem de sonunu görebilen hücreler P'yi içeremez (çünkü P başta veya sonda olmalıdır).

Örnek 1: 4-Düğümlü XY-Chain

Basit bir 4-düğümlü XY-Chain örneğine bakalım.

XY-Chain Örnek 1
Şekil 1: XY-Chain R2C2{3,7} → R2C6{3,5} → R9C6{2,5} → R9C7{2,7}, R2C7'den 7 elenebilir
Bu örneği çözücüde aç

Analiz Süreci

1 Zincir düğümlerini belirle:
  • R2C2: adaylar {3, 7} (zincir başı)
  • R2C6: adaylar {3, 5}
  • R9C6: adaylar {2, 5}
  • R9C7: adaylar {2, 7} (zincir sonu)
2 Zincir bağlantılarını doğrula:
  • R2C2 ve R2C6 aynı satırda (Satır 2), aday 3'ü paylaşıyor
  • R2C6 ve R9C6 aynı sütunda (Sütun 6), aday 5'i paylaşıyor
  • R9C6 ve R9C7 aynı satırda (Satır 9), aday 2'yi paylaşıyor
3 Eleme sayısını belirle:
  • Baş R2C2{3,7}'nin paylaşılmayan sayısı = 7 (3, R2C6 ile paylaşılıyor)
  • Son R9C7{2,7}'nin paylaşılmayan sayısı = 7 (2, R9C6 ile paylaşılıyor)
  • Aynılar! Z = 7
4 Akıl yürütme süreci:
  • R2C2=7 ise → 7 zincir başında
  • R2C2=3 ise → R2C6 3 olamaz → R2C6=5 → R9C6 5 olamaz → R9C6=2 → R9C7 2 olamaz → R9C7=7 → 7 zincir sonunda
  • Her iki durumda da 7, R2C2 veya R9C7'de olmalıdır
5 Eleme hedefini bul: R2C7 hem zincir başı R2C2'yi (aynı satır) hem de zincir sonu R9C7'yi (aynı sütun) görebilir.
Sonuç:
XY-Chain: R2C2{3,7} → R2C6{3,5} → R9C6{2,5} → R9C7{2,7}
R2C7'den aday 7 elenebilir.

Örnek 2: 10-Düğümlü Uzun Zincir

XY-Chain'ler çok uzun olabilir. İşte zincir akıl yürütmenin güçlü yeteneğini gösteren 10-düğümlü bir örnek.

XY-Chain Örnek 2
Şekil 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}, R8C5'ten 5 elenebilir
Bu örneği çözücüde aç

Analiz Süreci

1 Zincir düğümlerini belirle (10 düğüm):
  • R2C5: {1, 5} (zincir başı)
  • 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} (zincir sonu)
2 Zincir bağlantılarını doğrula:
  • R2C5 → R2C1: aynı satır, 1 (veya 5) paylaşıyor
  • R2C1 → R1C1: aynı sütun, 5 paylaşıyor
  • R1C1 → R1C7: aynı satır, 8 paylaşıyor
  • R1C7 → R3C7: aynı sütun, 7 (veya 8) paylaşıyor
  • R3C7 → R3C2: aynı satır, 8 paylaşıyor
  • R3C2 → R7C2: aynı sütun, 4 (veya 8) paylaşıyor
  • R7C2 → R8C1: aynı kutu, 8 paylaşıyor
  • R8C1 → R8C7: aynı satır, 4 paylaşıyor
  • R8C7 → R8C3: aynı satır, 9 paylaşıyor
3 Eleme sayısını belirle:
  • Baş R2C5{1,5}'in paylaşılmayan sayısı = 5 (1, R2C1 ile paylaşılıyor)
  • Son R8C3{5,9}'un paylaşılmayan sayısı = 5 (9, R8C7 ile paylaşılıyor)
  • Aynılar! Z = 5
4 Akıl yürütme sonucu: Zincir başı R2C5 ister 1 ister 5 olsun, aday 5 ya zincir başı R2C5'te ya da zincir sonu R8C3'te görünmelidir.
5 Eleme hedefini bul: R8C5 hem zincir başı R2C5'i (aynı sütun) hem de zincir sonu R8C3'ü (aynı satır) görebilir.
Sonuç:
XY-Chain (10 düğüm): R2C5 → R2C1 → R1C1 → R1C7 → R3C7 → R3C2 → R7C2 → R8C1 → R8C7 → R8C3
R8C5'ten aday 5 elenebilir.

XY-Chain'ler Nasıl Bulunur?

XY-Chain bulmak sistematik bir yaklaşım gerektirir:

1 İki değerli hücreleri işaretle: Önce sadece iki adayı olan tüm hücreleri belirle.
2 Başlangıç noktası seç: Zincir başı olarak iki değerli bir hücre seç, iki adayını {P,Q} kaydet.
3 Zinciri uzat: Mevcut düğümü "görebilen" ve bir adayı paylaşan iki değerli hücreleri sonraki düğüm olarak bul.
4 Sonlandırma koşulunu kontrol et: Her uzatmadan sonra, sonun paylaşılmayan sayısının başın paylaşılmayan sayısı P'ye eşit olup olmadığını kontrol et.
5 Eleme hedeflerini bul: Hem zincir başını hem de sonunu görebilen ve P'yi içeren hücreleri bul.
Önemli Notlar:
  • Zincirdeki her düğüm iki değerli hücre olmalıdır
  • Bitişik düğümler birbirini görmeli (aynı satır, sütun veya kutu)
  • Bitişik düğümler bir adayı paylaşmalı
  • Eleme koşulu: baş ve sonun paylaşılmayan adayları aynı
  • XY-Wing, XY-Chain'in özel bir durumudur (uzunluğu 3 olan bir zincir)

XY-Chain ve XY-Wing Arasındaki İlişki

XY-Wing, uzunluğu 3 olan bir XY-Chain olarak görülebilir:

  • XY-Wing: Pivot{X,Y} → Kanat1{X,Z} → Kanat2{Y,Z}... vb., bu aslında standart bir zincir formu değildir
  • Gerçek ilişki: XY-Wing yapısı "Y" şeklindedir, XY-Chain ise doğrusaldır
  • Ortak nokta: Her ikisi de mantıksal eleme için iki değerli hücreleri kullanır
  • Fark: XY-Chain zincir bağlantısı gerektirir, XY-Wing pivotin her iki kanadı da görmesini gerektirir

Teknik Özeti

XY-Chain uygulamanın anahtar noktaları:

  • Düğüm gereksinimi: Tüm düğümler iki değerli hücrelerdir
  • Bağlantı gereksinimi: Bitişik düğümler birbirini görebilir ve bir adayı paylaşır
  • Eleme koşulu: Baş ve sonun paylaşılmayan adayları aynıdır
  • Eleme hedefi: Hem başı hem de sonu görebilen hücrelerdeki paylaşılan aday
  • Zincir uzunluğu: Teorik olarak sınırsız, daha uzun zincirler bulmak daha zordur ama daha güçlüdür
Şimdi Pratik Yap:
Bir Sudoku oyunu başlat ve eleme için XY-Chain kullanmayı dene! Önce tüm iki değerli hücreleri bul, sonra onları bir zincire bağlamaya çalış.
XY-Wing Çıplak İkililer Teknik İndeksi