Arthur Whitney'nin tek satırlık Sudoku çözücüsü (2011)

 (dfns.dyalog.com)
1 puan yazan GN⁺ 2024-10-07 | 1 yorum | WhatsApp'ta paylaş
  • Dyalog APL'deki sudoku, boş hücreleri 0 olan bir bulmaca matrisinden olası tüm çözüm matrislerini döndürür ve aynı problemi APL/K tarzında çeşitli yollarla uygular
  • Temel hedef 9×9 Sudoku'dur; her 3×3 kutu, satır ve sütunda 1'den 9'a kadar rakamlar tekrar etmeden yer almalıdır
  • prob girdisi dolu hücrelerde 1-9, boş hücrelerde 0 içerir; isteğe bağlı sol argüman shape ile 2×3, 3×4 gibi kare olmayan kutular da belirtilebilir
  • Veli-Matti Jantunen'in çözüm algoritması matrisi vektörleştirir, satır·sütun·kutu indekslerini oluşturur ve adayları azaltarak en güçlü kısıta sahip gruptan genişletir
  • s33 ve s22 örneklerinin her biri 3 çözüme, 3 4 sudoku s34 ise 2 çözüme sahiptir; Arthur Whitney'nin K 5 tek satırlık çözümü ve çeşitli APL yeniden uygulamaları da birlikte tanıtılır

Sudoku girdisi ve sudoku fonksiyonunun sonucu

  • Sudoku bulmacası, 3×3 kutuların 3×3 düzenlendiği bir ızgaradır; her hücre ya boştur ya da 1'den 9'a kadar bir sayı içerir
  • Çözüm, tekrar yasağına ilişkin üç koşulun tümünü sağlamalıdır
    • Her 3×3 kutuda 1'den 9'a kadar sayılar tekrar etmeden bulunur
    • Her 9 hücreli satırda 1'den 9'a kadar sayılar tekrar etmeden bulunur
    • Her 9 hücreli sütunda 1'den 9'a kadar sayılar tekrar etmeden bulunur
  • prob matrisi dolu hücrelerde 1-9 sayılarını, boş hücrelerde ise 0 kullanır
  • İsteğe bağlı sol argüman shape, varsayılan kare olmayan bulmacaların kutu şeklini belirtir
    • 6×6 matriste alt bölge 2×3 ise 2 3 sudoku mat biçiminde çağrılır
  • Sonuç, tüm çözüm matrislerini içeren bir vektördür
    • Çözüm yoksa ⍬ döndürür
    • Hata durumları '' ile gösterilebilir; belgede bunun için “olmaması gerekir, ancak sonuç sayısı aşırı fazla olduğunda” ifadesi yer alır

Veli-Matti Jantunen çözümünün akışı

  • Algoritma Sudoku matrisini vektör olarak ele alır; satır, sütun ve Sudoku bölgelerini ayrı ayrı indeks vektörleri olarak gösterir
  • Temel kontrolleri geçtikten sonra aday listesindeki alternatifleri tek tek sınar
  • Her adımda tüm hücrelerin olası öğeleri filtrelenir
    • Olası değeri olmayan tek bir hücre bile varsa çözüm adayından çıkarılır
    • Bir hücrede birden fazla aday sayı varsa en güçlü kısıta sahip gruptan bir hücre seçilir ve o hücrenin aday kombinasyonları listeye eklenir
    • Tüm hücrelerde yalnızca birer sayı kalırsa çözüm olarak işlenir ve bir sonraki adaya geçilir
  • Aynı bölümde mevcut Sudoku tablosunu başka bir tabloya karıştıran Shuffle fonksiyonu da bulunur

Arthur Whitney tek satırlık çözümü ve alternatif uygulamalar

  • David Crossley'nin alternatif sudoku uygulaması girdi olarak N×N yapılandırmasını alır ve kutu boyutu N*÷2 tam sayı olan durumları hedefler
    • Girdi, bazı hücrelerinde 1'den N'ye kadar sayıların bulunduğu, geri kalanlarının 0 olduğu geçerli bir yerleşim olmalıdır
    • Her satır, sütun ve kutu sonuçta 1'den N'ye kadar tüm sayıları içermelidir
    • Uygulama içinde valid, search, rules, sole, singles, uniques, matches, NinN, setup gibi yardımcı fonksiyonlar vardır
  • Arthur Whitney'nin K 5 çözümü tek satır kod olarak sunulur
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~* x
  • Phil Last, Whitney'nin kodunu D-function'a taşıyan bir sudoku uygulaması sağlar
  • Morten Kromberg'in yeniden yazımı, K'nin bazı bileşenlerini açıkça tanımlayarak orijinale daha yakın bir biçim alır
    • K sürümünde olduğu gibi matris değil, 81 öğeli vektör alır ve döndürür
  • Roger Hui'nin Sudoku uygulaması daha genelleştirilmiş bir biçimdedir ve kare olmayan bulmacaları da işler
    • svec çözüm vektörünü oluşturur; pvex ve pvec olası yerleşimleri açar
    • avl olası sayı listesini oluşturur; emt boş hücrelerin satır·sütun indekslerini bulur
    • rcb, box, cmap, CMAP satır·sütun·kutu çakışma ilişkilerini kurar

Örnek bulmacalar ve çözüm sayıları

  • s33 9×9 örnek bir problemdir ve sudoku s33 sonucunda 3 çözüm vardır
  • sbox fonksiyonu, Sudoku ızgarasını okumayı kolaylaştırmak için iç kutulara ayırır
    • 0, nokta (·) olarak gösterilir
    • Kutu sınırları çizilmiş bir karakter matrisi biçiminde çıktı verir
  • s22 4×4 örnek bir problemdir ve sbox¨ sudoku s22 sonucunda 3 çözüm vardır
  • s34, 3×4 kutular kullanan örnek bir problemdir
    • 3 4 sbox s34 ile problem kutu ayrımlı biçimde gösterilir
    • 3 4 sudoku s34 sonucunda 2 çözüm vardır

Referans bağlantıları ve birlikte bakılacak öğeler

  • sudoku_bfs, bu algoritmayı gösteren örneğe bağlanır
  • TryAPL'nin “Learn” bölümünde adım adım demo vardır: http://www.TryAPL.org
  • Çalışma davranışını gösteren bir video vardır: http://www.youtube.com/watch?v=DmT80OseAGs
  • Birlikte bakılacak öğeler olarak queens, sudoku_bfs, X, sudokuX sunulur

İlgili okumalar

1 yorum

 
GN⁺ 2024-10-07
Hacker News yorumları

  • Söz konusu satır K ile yazılmış. K, Arthur Whitney’nin APL ve Scheme temelinde oluşturduğu bir dil
    x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

  • Bazen kod karmaşıklığını, kod satır sayısını aşağıdaki çıktıyla karşılaştırarak kestiriyorum
    tar -cf - . | gzip | base64 | wc -l
    Yani bir bakıma “ne kadar iyi sıkıştırılıyor?” diye bakmak. APL görünce, yanlışlıkla gzip çıktısını terminale gönderdiğim zamanlar aklıma geliyor
    p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵
    Böyle bir kodun izini sürüp “hata bulabilir misin?” aşamasına kadar giden insanların olması etkileyici. Sanki herkesin zaten aynı sözlüğe sahip olduğu sıkıştırılmış ikili veri gibi hissettiriyor

    • APL programcılarının bakım yapılabilirlik ve okunabilirlik hakkında ne düşündüklerini gerçekten merak ediyorum. Kodu çok ayrıntılı yorumlarla mı açıklıyorlar, yoksa ayrı dokümantasyon mu yazıyorlar acaba
    • “Hata bulabilir misin?” denirse hemen birkaç şey görünüyor. Kapatılmamış tek tırnak ve sağ operandı olmayan ∘ gibi sözdizimi hataları var; ayrıca n n←⍴⍵, n’i iki kez ayarlayıp ⍵’nin 2 boyutlu olmasını beklediğine dair bir işaret gibi duruyor, ama niyete göre _ n←⍴⍵ veya n←⊃⌽⍴⍵ daha doğal olurdu
      Ayrıca ⊥, ⍴⍵ tek bir tamsayı ya da boş vektör değilse hata vereceğinden sonuçta n←⍴⍵’den farksız kalıyor ve daha da kafa karıştırıyor. Birden fazla gereksiz , ve ↑⍵ de kaldırılabilir; ifadenin tamamı fiilen p←(n+1)⍴⊂⍳n×n←⍴⍵ ile neredeyse aynı hâle geliyor, yani 1..n² vektörünü n+1 kez çıkaran bir yapı
      Dışarıdan tuhaf görünse de sembolleri ve temel işlemleri öğrenince APL şaşırtıcı ölçüde doğrusal. Yalnız ustalaşmak zaman alıyor; o noktaya gelince de süper güç gibi hissettiriyor
    • İngilizce olmayan karakterleri okuyup yazan milyarlarca insan olduğunu düşününce, APL okuyabilen insanların olması daha özel ya da şaşırtıcı mı emin değilim

  • Dil savunucularının hız, dizi işleme kolaylığı ve ifade gücü yüksek sözdizimi vurgusu yaptığı doğru
    https://en.m.wikipedia.org/wiki/K_(programming_language)

    • Ama bakım yapılabilirlik bunun avantajlarından biri mi, emin değilim

  • Kod satır sayısı iyi bir ölçüt değil; çünkü her dil satırları farklı biçimde kullanıyor
    Daha iyi bir ölçü, “sabit” veya “fonksiyon çağrısı” gibi anlamlı uç olmayan semboller temelinde sözdizim ağacı düğüm sayısını saymak olabilir. Daha da iyisi, o ağacın derinliğini ve dallanma katsayısını da hesaba katmak

    • Yalnızca anlamın önemli olduğu yaklaşımına katılmak zor. Dilin kullanıcı deneyimi, açıklığı, düşünme biçimi ve ifade gücü de önemli; kodun görsel boyutu da bunları etkiliyor
      Tek satırlık çözüm ekranda neredeyse hiç yer kaplamadığından, karmaşık problemlerle uğraşırken büyük avantaj oluyor. Gözleri ekran içinde hareket ettirmek, dosyalar arasında gidip gelerek kaydırma yapmaktan çok daha az zahmetli; bilişsel yük önemli
      K bilmeseniz bile sabitler yan yana göründüğünde, problemin doğrudan veri temsilini kullanıyormuş gibi görünüyor. K kültürü böyle kodları teşvik ediyor ve düşünceyi doğrudanlık ile sadelik tarafına eğiyorsa, ekibe böyle bir özel sos katmak isterim
    • Yerleşik fonksiyonlar ve sistem kütüphanesi API’leri bu tür ölçütleri bozar. Örneğin HQ9+, “Hello, world!” çıktısı verme konusunda oldukça iyi
      https://cliffle.com/esoterica/hq9plus/
    • Bilgi miktarını ölçmek için tercih edilen ölçüt, algoritmik bilgi kuramındaki gibi basitçe bit sayısıdır
      https://en.wikipedia.org/wiki/Algorithmic_information_theory
    • Bu tek satırlık kod belli ki eğlence olsun diye yazılmış; kimse makul biçimde bunun okunması kolay kod olduğunu iddia etmiyor. Burada tanımı tartışmak asıl noktayı kaçırmak olur. Mesele, “K ile aşırı yoğun kod yazılabilir” olması

  • APL/K gibi dilleri kullanınca programcının gerçekten problemler hakkında daha verimli düşünüp düşünemediğini sık sık merak ediyorum

    • Bir kdb+/Q programcısı olarak bunun problem türüne bağlı olduğunu düşünüyorum. Veri dizileriyle uğraşırken, iki diziyi toplayıp ortalamasını alma işini avg a+b diye düşünmek ve yazmak kesinlikle daha kolay
      Dizi merkezli olmayan bir dilde muhtemelen sınır kontrolleri, büyük bir for döngüsü, toplam ve adet tutacak geçici değişkenler gerekir. C gibi bir dilde kabaca 6 satır sürecek bir işin Q’da 6 karakterde bitmesi gibi bir fark
      Yine de her dilde belirli problemleri daha iyi akıl yürütmenizi sağlayan özellikler var. Cebirsel veri tipleri ve pattern matching bulunan fonksiyonel diller, örneğin OCaml veya F#, büyük switch ya da if-else-if yapılarından iyidir; async/await gibi sözdizimsel şeker sunan diller de eşzamanlılık işlemede avantajlıdır
    • Kolayca vektörleştirilebilen problem kümelerinde dizi merkezli diller düşünmeyi ve çözümleri daha verimli kılar. Çünkü veri yapıları ve yinelemenin ayrıntılarını soyutlayabilirsiniz
      Quant olarak çalışırken kdb+/q’yu 5 yıldan uzun süre orta frekanslı stratejilerde yoğun kullandım; ama emir defteri hesaplamaları gibi kolay ya da verimli biçimde vektörleştirilemeyen yüksek frekanslı işlem tarafına geçince, dizi merkezli bir dili kullanmayı sürdürmek problem hakkında akıl yürütmeyi aksine daha karmaşık hâle getirdi
    • Dyalog adlı modern bir APL ailesi dili hakkındaki bir sunumda, bu tür gösterimin belirli idiomları tanımayı kolaylaştırdığı iddiasını duymuştum
      https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
      O bölüm derleyici bağlamındaydı; ancak sunumun geneli Dyalog ve APL’i matematiksel bir gösterim sistemi olarak ele alıyor. Ana akış, matematik ifadelerini optimize etmenin genel kodu optimize etmekten daha kolay olabileceği yönünde
    • Hillel Wayne bülteninde bu konuyu ara sıra ele alıyor. Bazı problemleri gerçekten dizi dillerinde daha iyi düşündüğüne ikna oldum, ama o deneyimin nasıl hissettirdiğini hâlâ pek hayal edemiyorum
    • Dizi dili tarzının güzel yanı, algoritma varyasyonlarını tartışırken ilgili kod parçalarının birkaç karakterden ibaret olması ve doğrudan metnin içine girebilmesi. Aynı şeyi anlatmak için birkaç satır ya da onlarca satır gereken geleneksel dikey dillerde ise kod bloklarıyla açıklama metinlerini sürekli iç içe geçirmek gerekiyor

  • Buradaki en önemli noktalardan biri, üstteki problem üretecinin son derece anlaşılır olması. J ve K dâhil Iverson tarzı sembolik diller ile diğer diller arasındaki fark bu
    Tek satırlık çözümün zarafeti ve gücü yok ama katı yorum satırları olmadan da çok temiz ve anlaşılır. Yalnız lamp'in iyi bir yorum işareti olduğunu düşünmüyorum
    Tek satırlık çözüm şaşırtıcı ve örtük programlama aklı bükecek kadar harika. Glif tabanlı bir dilin kendine özgü sıkıştırma gücünü fonksiyonel programlamayı açıklamak ve gerçekleştirmek için kullanıp, sonra bunu tüm dizilere uygulama fikri dahiyane
    https://www.jsoftware.com/papers/fork.htm

    • Her şeyi boşluksuz tek satıra yazabiliyor olmanız, mutlaka öyle yapmanız gerektiği anlamına gelmez
      Elbette bu yeteneği kaldırırsanız insanları daha ayrıntılı kod yazmaya zorlayabilirsiniz; ama o zaman etkileşimli bir araç olarak güçlü yanı büyük ölçüde azalır. Iverson tarzı diller çok kısa kod yazmaya izin verdiği için etkileşimli çalışma için kullanışlıdır. O sıradaki kod çoğu zaman kaydedilmediğinden gerçekten write-only koddur
      Dosyaya girecek kodu yazarken istediğiniz stili seçebilirsiniz; o durumda daha az sıkıştırılmış yazmayı öneririm. Yine de Iverson tarzı diller, ayrıntılı bir stille yazıldıklarında bile çoğu dilden çok daha kısa kod sunar

  • Çoğu kişi semboller yüzünden uzak duruyor, ama benim sorunum bu değildi
    APL'yi ve dizi dillerini seviyorum; öğrendiklerim başka dilleri kullanırken de bana çok yardımcı oldu. Ama günlük aracım hâline gelmedi; nedeni semboller değil, 3-4 yıl kadar ara ara uğraştıktan sonra aşamadığım bir duvara çarpmamdı
    Diğer dillerde genellikle bir problemi kabaca da olsa çözmeye yarayan genel bir yaklaşım vardır; daha sonra o problemin “püf noktasını” bulunca bunu daha zarif ve verimli hâle getirebilirsiniz. APL'de böyle geçici bir dolambaçlı yol yokmuş, ya püf noktasını biliyorsunuz ya da bilmiyorsunuz gibi hissettirdi
    Gerçekten böyle mi, yeterince püf noktası öğrenince problem çözme sezgisi gelişiyor mu, sonuna kadar sadece püf noktalarından mı ibaret, yoksa ben temel strateji belgelerini mi okumadım, tam emin değilim

    • Bu his yanlış değil. Dizi dillerini öğrenirken böyle bir izlenime kapılmak çok kolay. Uzun süredir kullanan birinin probleme bakıp “Neden bu kadar karmaşık çözdün ki, sadece ⍸⍣¯1 kullansaydın yeterdi?” demesi kolay; ama büyük olasılıkla kimse size ⍸'nin ters işlemi olduğunu ve nasıl kullanılacağını söylememiştir
      Yıllardır bu dilleri kullanıyor olsam da bazı dizi programcılarının oluşturduğu kod duvarları hâlâ biraz göz korkutucu geliyor. Neden öyle yazdıklarını anlıyorum, ama şahsen kodda biraz boşluk olmasını tercih ediyorum
      APL tabanlı bir dizi dili geliştiriyorum; ilk hedeflerimden biri, if deyimi gibi şeyler kullanan yeni başlayanları cezalandırmadan emirsel stili birinci sınıf vatandaş yapmak oldu. Bu stili saf APL tarzı ile genel emirsel diller arasında bir yerde görüyorum
      https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap
    • Bahsettiğiniz duvar, mevcut APL'ye giriş yollarının gerçek bir sorunu. Geçen yıl tam da bu konuda bir sunum yaptım; kesinlikle kişisel bir kusur değil
      Öte yandan bu, dilin kendi sınırı da değil. Benim deneyimimde o duvarı aşma süreci, paradigmanın yerine oturma sürecinin ta kendisiydi. Bir yıl boyunca bir YAML ayrıştırıcı prototipi üzerinde yaklaşık 500 saat hack'ledikten sonra parçalar yerine oturmaya başladı
      Esas mesele; veri odaklı tasarım ilkeleri, iyi notasyonun Iverson tarzı özelliklerini yazılım mimarisinde somut olarak kullanma biçimleri ve deyimlere ve bunların alan kavramlarını ifade etme yollarına alışmanın birleşimi gibi geliyor
      https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4
      https://www.jsoftware.com/papers/tot.htm

  • Bu konu hakkında bir video var
    https://www.youtube.com/watch?v=DmT80OseAGs
    Çözümü https://tryapl.org/ üzerinden kendiniz deneyebilirsiniz

  • Bu tek satırı çeşitli programlama dillerindeki code golf çözümleriyle karşılaştırmak ilginç olabilir
    https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes

    • İlginçtir ki belirli bir problemde, yani kaba kuvvetle Sudoku çözmede birinci sıradaki çözüm doğrudan bir K parçası. İkinci sıradaki ise K çözümünü örnek alan bir J çözümü
      https://codegolf.stackexchange.com/a/5030