Solver Sudoku one-liner Arthur Whitney (2011)

 (dfns.dyalog.com)
1 poin oleh GN⁺ 2024-10-07 | 1 komentar | Bagikan ke WhatsApp
  • sudoku di Dyalog APL mengembalikan semua matriks solusi yang mungkin dari matriks puzzle dengan sel kosong bernilai 0, dan mengimplementasikan masalah yang sama dalam berbagai cara dengan gaya APL/K
  • Target dasarnya adalah Sudoku 9×9, dengan angka 1 sampai 9 harus masuk tanpa pengulangan di setiap kotak 3×3, baris, dan kolom
  • Input prob berisi 1-9 untuk sel yang terisi dan 0 untuk sel kosong; argumen kiri opsional shape juga dapat menentukan kotak non-persegi seperti 2×3 atau 3×4
  • Algoritme solusi Veli-Matti Jantunen memvektorisasi matriks, membuat indeks baris·kolom·kotak, lalu mengurangi kandidat sambil memperluas mulai dari grup dengan batasan paling kuat
  • Contoh s33 dan s22 masing-masing memiliki 3 solusi, 3 4 sudoku s34 memiliki 2 solusi, dan one-liner K 5 dari Arthur Whitney beserta beberapa reimplementasi APL juga diperkenalkan

Input Sudoku dan hasil fungsi sudoku

  • Puzzle Sudoku adalah kisi dengan kotak 3×3 yang tersusun 3×3, dan setiap sel kosong atau berisi angka 1 sampai 9
  • Solusi harus memenuhi ketiga kondisi tanpa duplikasi berikut
    • Setiap kotak 3×3 berisi angka 1 sampai 9 tanpa pengulangan
    • Setiap baris 9 sel berisi angka 1 sampai 9 tanpa pengulangan
    • Setiap kolom 9 sel berisi angka 1 sampai 9 tanpa pengulangan
  • Matriks prob menggunakan angka 1-9 untuk sel yang terisi dan 0 untuk sel kosong
  • Argumen kiri opsional shape menentukan bentuk kotak untuk puzzle yang bukan persegi standar
    • Pada matriks 6×6 dengan subwilayah 2×3, panggil dalam bentuk 2 3 sudoku mat
  • Hasilnya adalah vektor yang berisi semua matriks solusi
    • Jika tidak ada solusi, mengembalikan ⍬
    • Situasi error dapat ditandai dengan ''; dokumentasinya menyebutkan “seharusnya tidak terjadi, tetapi ketika hasilnya sangat banyak”

Alur solusi Veli-Matti Jantunen

  • Algoritme memperlakukan matriks Sudoku sebagai vektor, dan merepresentasikan baris·kolom·wilayah Sudoku masing-masing sebagai vektor indeks
  • Setelah lolos pemeriksaan dasar, algoritme memeriksa alternatif satu per satu dari daftar kandidat
  • Pada setiap langkah, elemen yang mungkin untuk semua sel disaring
    • Jika ada satu saja sel tanpa nilai yang mungkin, kandidat solusi tersebut dikeluarkan
    • Jika sebuah sel memiliki lebih dari satu kandidat angka, algoritme memilih sel dari grup dengan batasan paling kuat dan menambahkan kombinasi kandidat sel itu ke daftar
    • Jika semua sel hanya menyisakan masing-masing satu angka, kandidat itu diproses sebagai solusi lalu beralih ke kandidat berikutnya
  • Bagian yang sama juga mencakup fungsi Shuffle untuk mengacak tabel Sudoku yang sudah ada menjadi tabel lain

One-liner Arthur Whitney dan implementasi alternatif

  • Implementasi alternatif sudoku dari David Crossley menerima konfigurasi N×N sebagai input, dan menargetkan kasus ketika ukuran kotak N*÷2 adalah bilangan bulat
    • Input harus berupa susunan valid dengan angka 1 sampai N di sebagian sel dan 0 di sisanya
    • Setiap baris, kolom, dan kotak harus memuat semua angka 1 sampai N pada hasilnya
    • Di dalam implementasi terdapat fungsi pembantu seperti valid, search, rules, sole, singles, uniques, matches, NinN, setup
  • Solusi K 5 dari Arthur Whitney disajikan sebagai kode satu baris
x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~* x
  • Phil Last menyediakan implementasi sudoku yang memindahkan kode Whitney ke D-function
  • Penulisan ulang oleh Morten Kromberg mendefinisikan secara eksplisit sebagian komponen K, sehingga bentuknya lebih dekat ke sumber asli
    • Seperti versi K, input dan outputnya bukan matriks, melainkan vektor 81 elemen
  • Implementasi Sudoku dari Roger Hui lebih tergeneralisasi dan juga menangani puzzle non-persegi
    • svec membuat vektor solusi, sementara pvex dan pvec mengembangkan susunan yang mungkin
    • avl membuat daftar angka yang mungkin, dan emt mencari indeks baris·kolom untuk sel kosong
    • rcb, box, cmap, CMAP menyusun hubungan konflik baris·kolom·kotak

Contoh puzzle dan jumlah solusi

  • s33 adalah contoh soal 9×9, dan hasil sudoku s33 memiliki 3 solusi
  • Fungsi sbox membagi kotak-kotak internal agar kisi Sudoku lebih mudah dibaca
    • 0 ditampilkan sebagai titik (·)
    • Output berupa matriks karakter dengan batas kotak yang digambar
  • s22 adalah contoh soal 4×4, dan hasil sbox¨ sudoku s22 memiliki 3 solusi
  • s34 adalah contoh soal yang menggunakan kotak 3×4
    • 3 4 sbox s34 menampilkan soal dalam bentuk dengan pemisah kotak
    • Hasil 3 4 sudoku s34 memiliki 2 solusi

Tautan referensi dan item terkait

Bacaan terkait

1 komentar

 
GN⁺ 2024-10-07
Komentar Hacker News

  • Baris tersebut ditulis dalam K. K adalah bahasa yang dibuat Arthur Whitney berdasarkan APL dan Scheme
    x(,/{@[x;y;]'(!10)^x*|/p[;y]=p,:,3/:-3!p:!9 9}')/&~*x

  • Kadang kompleksitas kode saya taksir dengan membandingkan jumlah baris kode dengan hasil keluaran berikut
    tar -cf - . | gzip | base64 | wc -l
    Dengan kata lain, melihat “seberapa baik ia bisa dikompresi?”. Melihat APL mengingatkan saya pada saat tanpa sengaja mengirim keluaran gzip ke terminal
    p←{(↑⍵)∘{(⍺∨.=⍵)/⍳n×n∘}¨,⍵},(n*÷2){⍵,⍺⊥⌊⍵÷⍺}'⍳n n←⍴⍵
    Menarik bahwa ada orang yang bisa menelusuri kode seperti ini sampai ke tahap “bisakah menemukan bug?”. Rasanya seperti data biner terkompresi yang kamusnya sudah sama-sama dimiliki semua orang

    • Saya benar-benar penasaran bagaimana programmer APL memandang maintainability dan keterbacaan. Apakah mereka memberi komentar sangat rinci pada kode, atau membuat dokumentasi terpisah?
    • Kalau pertanyaannya “bisakah menemukan bug?”, beberapa hal langsung terlihat. Ada syntax error seperti tanda petik tunggal yang tidak ditutup dan ∘ tanpa operand kanan, dan n n←⍴⍵ tampak seperti sinyal bahwa n diset dua kali dan ⍵ diharapkan berdimensi 2, tetapi tergantung maksudnya, _ n←⍴⍵ atau n←⊃⌽⍴⍵ terasa lebih alami
      Selain itu, ⊥ akan error jika ⍴⍵ bukan integer tunggal atau vektor kosong, sehingga pada akhirnya tidak berbeda dari n←⍴⍵ dan malah lebih membingungkan. Beberapa , yang redundan dan ↑⍵ juga bisa dihapus, dan seluruh ekspresi pada dasarnya menjadi hampir sama dengan p←(n+1)⍴⊂⍳n×n←⍴⍵, yaitu struktur yang mengeluarkan vektor 1..n² sebanyak n+1 kali
      Meski tampak aneh dari luar, setelah mempelajari simbol dan operasi dasarnya, APL ternyata cukup lurus. Hanya saja butuh waktu untuk mahir, dan begitu mencapai titik itu rasanya seperti punya kekuatan super
    • Mengingat ada miliaran orang yang membaca dan menulis karakter non-Inggris, saya tidak yakin bahwa adanya orang yang bisa membaca APL itu lebih istimewa atau mengejutkan

  • Memang benar para pendukung bahasa ini menekankan kecepatan, kemudahan pemrosesan array, dan sintaks yang ekspresif
    https://en.m.wikipedia.org/wiki/K_(programming_language)

    • Namun saya tidak tahu apakah maintainability juga bisa disebut keunggulan

  • Jumlah baris kode bukan metrik yang baik karena tiap bahasa punya cara berbeda dalam memakai baris
    Ukuran yang lebih baik mungkin menghitung jumlah node pohon sintaks berdasarkan simbol nonterminal bermakna seperti “konstanta” atau “pemanggilan fungsi”. Lebih jauh lagi, akan lebih baik jika juga mempertimbangkan kedalaman pohon dan faktor percabangannya

    • Saya sulit setuju dengan gagasan bahwa yang penting hanya makna. Pengalaman pengguna bahasa, kejelasan, cara berpikir, dan daya ekspresi juga penting, dan ukuran visual kode memengaruhi semua itu
      Solusi satu baris hampir tidak memakan ruang layar, sehingga menjadi keuntungan besar saat menangani masalah kompleks. Menggerakkan mata di dalam layar jauh lebih ringan daripada berpindah-pindah file dan menggulir, dan beban kognitif itu penting
      Bahkan jika tidak tahu K, ketika konstanta-konstanta terlihat berjajar, itu tampak seperti memakai representasi data langsung dari masalahnya. Jika budaya K mendorong kode seperti ini dan mengarahkan cara berpikir ke arah kelangsungan dan kesederhanaan, saya ingin membawa saus spesial seperti itu ke dalam tim
    • Fungsi bawaan dan API pustaka sistem merusak metrik semacam ini. Misalnya HQ9+ cukup bagus khusus untuk mencetak “Hello, world!”
      https://cliffle.com/esoterica/hq9plus/
    • Metrik favorit untuk mengukur jumlah informasi hanyalah jumlah bit, seperti dalam teori informasi algoritmik
      https://en.wikipedia.org/wiki/Algorithmic_information_theory
    • Kode satu baris ini jelas dibuat sebagai lelucon, dan tidak ada orang yang secara masuk akal mengklaimnya sebagai kode yang mudah dibaca. Berdebat soal definisi di sini berarti melewatkan inti pembahasannya. Poinnya adalah “di K, kita bisa menulis kode yang sangat padat”

  • Saya sering bertanya-tanya apakah memakai bahasa seperti APL/K benar-benar membuat programmer bisa memikirkan masalah dengan lebih efisien

    • Sebagai programmer kdb+/Q, menurut saya itu tergantung jenis masalahnya. Saat menangani array data, memang jauh lebih mudah memikirkan dan menulis pekerjaan seperti menjumlahkan dua array lalu mengambil rata-ratanya sebagai avg a+b
      Dalam bahasa yang tidak berpusat pada array, kemungkinan besar perlu pemeriksaan batas, loop for besar, variabel sementara untuk menyimpan jumlah dan hitungan, dan sebagainya. Bedanya, sesuatu yang kira-kira butuh 6 baris di bahasa seperti C selesai dalam 6 karakter di Q
      Namun setiap bahasa punya fitur yang membuat masalah tertentu lebih mudah ditalar. Bahasa fungsional dengan algebraic data type dan pattern matching, misalnya OCaml atau F#, lebih baik daripada switch besar atau if-else-if, dan bahasa dengan syntactic sugar seperti async/await unggul untuk menangani konkurensi
    • Untuk kelompok masalah yang mudah divektorkan, bahasa berpusat array membuat pemikiran dan solusi lebih efisien. Sebab detail struktur data dan iterasi bisa diabstraksikan
      Saat bekerja sebagai quant, saya banyak memakai kdb+/q selama lebih dari 5 tahun untuk strategi frekuensi menengah, tetapi ketika pindah ke perdagangan frekuensi tinggi yang tidak mudah atau tidak efisien divektorkan, seperti perhitungan order book, terus memakai bahasa berpusat array justru membuat penalaran masalah menjadi lebih rumit
    • Dalam presentasi tentang Dyalog, bahasa modern turunan APL, saya pernah mendengar klaim bahwa notasi seperti ini membuat idiom tertentu lebih mudah dikenali
      https://youtu.be/PlM9BXfu7UY?si=ORtwI1qmfmzhJGZX&t=3598
      Bagian tersebut berada dalam konteks compiler, tetapi keseluruhan presentasinya memperlakukan Dyalog dan APL sebagai sistem notasi matematis. Alur utamanya adalah bahwa mengoptimalkan ekspresi matematika bisa jadi lebih mudah daripada mengoptimalkan kode umum
    • Hillel Wayne kadang membahas topik ini di newsletter-nya. Saya sudah diyakinkan bahwa ia memang memikirkan sebagian masalah dengan lebih baik dalam bahasa array, tetapi saya masih belum bisa membayangkan seperti apa rasanya pengalaman itu
    • Hal baik dari gaya bahasa array adalah, ketika mendiskusikan variasi algoritma, potongan kode terkait hanya beberapa karakter sehingga bisa langsung masuk ke dalam teks utama. Dalam bahasa vertikal tradisional, yang membutuhkan beberapa baris atau puluhan baris untuk mengatakan hal yang sama, kita harus terus mencampur blok kode dan paragraf penjelasan

  • Salah satu hal terpenting di sini adalah generator soal di bagian atas sangat jelas. Inilah perbedaan antara bahasa notasi ala Iverson, termasuk J dan K, dengan bahasa lain
    Memang tidak memiliki keanggunan dan kekuatan solusi satu baris, tetapi sangat rapi dan dapat dipahami bahkan tanpa komentar yang ketat. Namun, menurut saya lamp bukan simbol komentar yang bagus
    Solusi satu baris itu menakjubkan, dan pemrograman implisit begitu keren sampai membuat pikiran terasa terpelintir. Gagasan menggunakan kompresibilitas unik bahasa berbasis glif untuk menjelaskan dan menjalankan pemrograman fungsional, lalu menerapkannya lagi ke seluruh array, benar-benar jenius
    https://www.jsoftware.com/papers/fork.htm

    • Hanya karena semuanya bisa ditulis dalam satu baris tanpa spasi, bukan berarti harus begitu
      Tentu, kalau kemampuan itu dihilangkan, orang bisa dipaksa menulis kode yang lebih verbose, tetapi itu akan sangat mengurangi kekuatannya sebagai alat interaktif. Bahasa ala Iverson berguna untuk pekerjaan interaktif karena dapat menulis kode yang sangat singkat. Kode saat itu bahkan tidak disimpan, jadi benar-benar kode write-only
      Saat menulis kode yang akan masuk ke file, pilih saja gaya yang diinginkan, dan dalam kasus itu saya menyarankan gaya yang tidak terlalu terkompresi. Meski begitu, bahkan ketika ditulis dengan gaya verbose, bahasa ala Iverson tetap menyediakan kode yang jauh lebih pendek daripada kebanyakan bahasa

  • Kebanyakan orang enggan karena simbol-simbolnya, tetapi bagi saya masalahnya bukan itu
    Saya menyukai APL dan bahasa array, dan hal-hal yang saya pelajari sangat membantu bahkan saat memakai bahasa lain. Namun, itu tidak pernah menjadi alat harian saya; bukan karena simbolnya, melainkan karena setelah memakainya sesekali selama sekitar 3–4 tahun, saya menabrak tembok yang tidak bisa saya lewati
    Di bahasa lain biasanya ada pendekatan umum untuk menyelesaikan masalah secara kasar, lalu nanti jika menemukan “trik” untuk masalah itu, kita bisa memperbaikinya agar lebih elegan dan efisien. APL terasa tidak punya jalan memutar sementara seperti itu; rasanya hanya ada dua kemungkinan: tahu triknya atau tidak
    Saya tidak yakin apakah memang begitu kenyataannya, apakah setelah mempelajari cukup banyak trik akan muncul intuisi pemecahan masalah, apakah sampai akhir isinya hanya trik, atau apakah saya saja yang belum membaca dokumen strategi intinya

    • Perasaan itu tidak salah. Saat belajar bahasa array, sangat mudah mendapatkan kesan seperti itu. Orang yang sudah lama memakainya bisa saja melihat sebuah masalah lalu berkata, “Kenapa dibuat serumit itu, cukup pakai ⍸⍣¯1 saja,” padahal kemungkinan besar tidak pernah ada yang memberi tahu bahwa ⍸ punya operasi invers dan bagaimana memakainya
      Saya pun sudah bertahun-tahun memakai bahasa seperti ini, tetapi dinding kode yang dibuat sebagian programmer array masih terasa sedikit membebani. Saya paham mengapa mereka menulisnya begitu, tetapi secara pribadi saya lebih suka ada sedikit spasi di dalam kode
      Saya sedang membuat bahasa array berbasis APL, dan salah satu tujuan awalnya adalah menjadikan gaya imperatif sebagai warga kelas satu tanpa menghukum pemula yang memakai hal-hal seperti pernyataan if. Saya melihat gaya ini berada kira-kira di tengah antara gaya APL murni dan bahasa imperatif biasa
      https://codeberg.org/loke/array/src/branch/master/array/standard-lib/output3.kap
    • Tembok yang Anda sebutkan adalah masalah nyata dalam jalur masuk APL saat ini. Tahun lalu saya juga memberi presentasi tentang topik ini, dan ini sama sekali bukan salah individu
      Meski begitu, ini juga bukan keterbatasan bahasa itu sendiri. Dalam pengalaman saya, proses menembus tembok itu justru merupakan proses saat paradigmanya mulai terasa cocok. Baru setelah mengutak-atik prototipe parser YAML selama sekitar 500 jam dalam setahun, potongan-potongannya mulai menyatu
      Intinya terasa seperti kombinasi antara prinsip desain berbasis data, cara memanfaatkan karakter ala Iverson dari notasi yang baik secara konkret dalam arsitektur perangkat lunak, serta membiasakan diri dengan idiom dan cara idiom itu mengekspresikan konsep domain
      https://dyalog.tv/Dyalog23/?v=J4cg6SV92C4
      https://www.jsoftware.com/papers/tot.htm

  • Ada video tentang topik ini
    https://www.youtube.com/watch?v=DmT80OseAGs
    Solusinya bisa dicoba langsung di https://tryapl.org/

  • Akan menarik jika membandingkan satu baris ini dengan solusi code golf dalam berbagai bahasa pemrograman
    https://codegolf.stackexchange.com/questions/tagged/sudoku?tab=Votes

    • Menariknya, solusi peringkat pertama untuk masalah tertentu, yaitu pemecah Sudoku brute force, adalah potongan K. Peringkat kedua adalah solusi J yang dibuat mengikuti solusi K
      https://codegolf.stackexchange.com/a/5030