Buat teka-teki silang yang dapat dipecahkan secara unik ... tanpa petunjuk

21

Bisakah Anda bayangkan memecahkan teka-teki silang New York Times tanpa petunjuk? Mungkin tidak dengan semua kreativitas dan kata-kata dan frase baru yang muncul dalam teka-teki silang modern, tetapi dengan daftar kata tetap ada beberapa harapan. Dalam tantangan ini, Anda membuat kisi teka-teki silang yang secara teori memungkinkan.

Tantangan

Maksimalkan jumlah kotak putih dalam kisi teka-teki silang 15x15 berwarna putih dan hitam, sehingga kotak putih dapat menjadi unik diisi dengan huruf sehingga setiap kata lintas dan turun muncul dalam daftar kata internasional Scrabble.

Klarifikasi konstruksi grid

Di surat kabar AS, kisi - kisi teka-teki silang biasanya dibuat sehingga setiap huruf "dicentang", artinya adalah bagian dari kata "seberang" dan kata "turun". Di Inggris dan di tempat lain (terutama di teka-teki silang samar ), ini belum tentu demikian: jika kata "lintas" atau "turun" hanya akan menjadi satu huruf, kata itu tidak harus berupa kata yang sebenarnya (seperti "A" atau "I" "). Untuk tantangan ini, ikuti aturan yang lebih santai: kata-kata satu huruf tidak perlu muncul dalam daftar kata.

Ada berbagai tradisi lain (di AS dan di tempat lain), tidak ada yang perlu diikuti dalam tantangan ini. Misalnya, kata-kata hanya dapat terdiri dari dua huruf, kata-kata diizinkan untuk diulang, dan kisi tidak perlu memiliki simetri (rotasi).

Apakah ini mungkin?

Iya nih! Orang dapat menulis skrip pendek untuk memverifikasi bahwa solusi unik untuk kisi kosong berikut di sebelah kiri adalah kisi yang diisi di sebelah kanan:

Kotak 15x15 dengan empat kata 15 huruf disilangkan pada huruf keempat dan kelima mereka

Seseorang dapat menampilkan kisi yang diisi dalam format yang dapat dibaca komputer sebagai berikut:

###CH##########
###YE##########
###AM##########
CYANOCOBALAMINE
HEMOCHROMATOSES
###CH##########
###OR##########
###BO##########
###AM##########
###LA##########
###AT##########
###MO##########
###IS##########
###NE##########
###ES##########

Solusi Anda

Kotak di atas memiliki 56 kotak putih dari total 225 kotak di kotak 15x15. Ini berfungsi sebagai garis dasar untuk tantangan ini. Kisi-kisi dengan kotak putih lebih sedikit mungkin juga menarik untuk alasan selain skor mereka, misalnya jika mereka memenuhi beberapa tradisi estetika yang disebutkan di atas.

Silakan kirimkan solusi Anda dalam format yang sama dengan baseline yang dapat dibaca komputer di atas. Harap sertakan kode yang memverifikasi bahwa ada solusi unik untuk kisi Anda.

Cuplikan kode yang menarik (misalnya untuk mencari ruang kemungkinan) dan diskusi tentang bagaimana Anda menemukan kisi Anda dihargai.

Daftar kata

Daftar kata internasional Scrabble sebelumnya dikenal sebagai SOWPODS dan sekarang disebut Collins Scrabble Words (CSW). Ini digunakan di sebagian besar negara (kecuali AS). Kami lebih suka menggunakan daftar ini karena termasuk ejaan bahasa Inggris dan umumnya memiliki banyak kata secara signifikan daripada daftar kata Amerika. Ada beberapa edisi dari daftar ini yang sedikit berbeda. Anda dapat menemukan berbagai versi daftar ini yang ditautkan dari Wikipedia , di Github , di Natural Language Corpus karya Peter Norvig dan di tempat lain, sering kali masih disebut "SOWPODS".

Tantangan ini sangat sensitif terhadap sifat luas dari pilihan daftar kata, tetapi kurang begitu detail kecil. Misalnya, contoh dasar di atas berfungsi dengan CSW edisi apa pun, tetapi CHbukan kata dalam daftar kata American Scrabble. Dalam hal terjadi perbedaan, kami lebih suka menggunakan CSW19, edisi CSW terbaru. (Jika kami menggunakan daftar ini, yang dirilis tahun ini, kami dapat mengharapkan jawaban untuk tantangan ini tetap berlaku lebih lama). Anda dapat meminta daftar ini secara interaktif di situs pencari kata Scrabble resmi atau mengunduhnya (serta edisi sebelumnya, CSW15) dari Board & Card Games Stack Exchange atau r / scrabble Reddit .

Tldr : daftar kata resmi untuk tantangan ini tersedia sebagai file teks biasa (279.496 kata, satu per baris) di atas Board & Card Games Stack Exchange .

Diskusi lebih lanjut

Satu masalah yang diangkat dalam jawaban dan komentar awal adalah mengapa teka-teki silang yang ada (misalnya, di NYT) tidak menjawab pertanyaan ini. Secara khusus, catatan untuk jumlah kotak hitam paling sedikit (dan dengan demikian jumlah kotak putih terbesar) untuk teka-teki silang NYT yang diterbitkan sudah merupakan rekor paling terkenal dalam teka-teki silang. Kenapa kita tidak bisa menggunakan kisi catatan ? Ada beberapa masalah:

  • Banyak jawaban dalam teka-teki silang NYT tidak muncul di daftar kata kami. Sebagai contoh, kotak catatan mencakup PEPCID(nama merek), APASSAGETOINDIA(nama empat kata yang tepat untuk sebuah film dan novel, ditulis tanpa spasi), dan STE(singkatan untuk "Sainte"). Tampaknya kotak catatan tidak dapat dipecahkan dengan kata-kata Scrabble.

  • Hanya memperluas daftar kata untuk memasukkan lebih banyak kata tidak selalu membantu dengan tantangan ini: bahkan jika semua kata dalam kisi catatan muncul di daftar kata kami, solusinya tidak akan unik tanpa petunjuk. Seringkali dimungkinkan untuk mengubah beberapa huruf di akhir jawaban sambil tetap menjaga segala sesuatunya sepatah kata pun. (Misalnya, huruf paling kanan bawah dapat diubah dari a Dmenjadi R.) Memang, ini adalah bagian dari proses konstruksi (manusia) ketika menulis teka-teki silang, berusaha mendapatkan kata-kata "lebih baik".

    Alasan teka-teki silang biasa (biasanya) memiliki solusi unik adalah bahwa petunjuknya membantu mempersempit jawaban yang benar. Jika Anda hanya mencoba mengisi kotak dengan kata - kata tanpa menggunakan petunjuk, kemungkinan tidak akan ada kemungkinan atau banyak kemungkinan. Berikut adalah contoh dari tiga isian berbeda (menggunakan daftar kata untuk tantangan ini!) Untuk kisi yang sama (yang relatif sering digunakan di NYT):

Kotak teka-teki silang NYT yang paling umum, diisi dengan tiga cara berbeda dengan kata-kata Scrabble.

  • Masalah lain yang diangkat dalam komentar adalah sejumlah ketidakpercayaan bahwa pertanyaan ini merupakan tantangan pengkodean . Mungkin itu tidak segera jelas, tetapi sulit untuk bahkan menemukan satu jawaban yang valid untuk tantangan ini . Menemukan garis dasar di atas melibatkan beberapa program pencarian yang dibuat khusus yang tidak dijamin untuk menemukan jawaban. Saya pribadi bahkan tidak tahu cara umum untuk menyelesaikan grid yang sewenang-wenang, jika Anda ingin jawabannya dalam waktu yang wajar. Program konstruksi teka-teki silang yang ada dapat membantu, tetapi saya berasumsi (mungkin secara keliru) bahwa mereka tidak benar-benar melakukan pencarian penuh kemungkinan. (Saya menggunakan program seperti itu untuk tiga kisi-kisi berdampingan di atas; ini berhasil karena kisi tertentu memungkinkan banyak solusi.)
A. Rex
sumber
2
Meta post terkait dengan jenis pertanyaan umum ini: codegolf.meta.stackexchange.com/questions/18117/…
A. Rex
3
1. Jatuhkan opsi estetika (" Grids with fewer white squares may also be interesting for reasons other than their score, for example if they satisfy some of the aesthetic traditions mentioned above.") - sama dengan menghindari bonus dalam kode golf, saya lebih suka tantangan kode hanya tentang satu hal. Ini berarti semua jawaban dapat dibandingkan seperti untuk. Ini juga membuatnya jelas obyektif, yang akan membantu dengan membuka kembali suara.
trichoplax
4
2. Pilih satu daftar kata dan bersikeras untuk semua jawaban. Tldr menyebutkan daftar kata yang otoritatif, tetapi diskusi sebelumnya mungkin membuat orang berpikir mereka dapat memilih salah satu dari yang disebutkan. Mungkin membantu menjaga persyaratan ketat di dekat bagian atas pos, dan untuk membuatnya sangat jelas bahwa perincian lain bukan bagian dari spesifikasi tantangan. Idealnya, hilangkan apapun yang tidak perlu untuk spek agar posnya singkat dan segera tidak ambigu.
trichoplax
2
3. Buat penyertaan kode yang digunakan untuk menemukan solusi persyaratan untuk jawaban yang valid.
trichoplax
3
Ini adalah jenis tantangan yang dapat memanfaatkan ruang obrolan bagi orang-orang untuk membahas pendekatan. Jika Anda mengatur ruang obrolan dan menautkannya dari akhir spesifikasi, Anda dapat memposting diskusi di sana sebagai posting awal, dan menyebutkan ini dalam tantangan bagi orang yang ingin tahu lebih banyak.
trichoplax

Jawaban:

9

180 kotak putih

Kotak kosong Larutan

Strategi saya adalah menemukan kotak yang lebih kecil tanpa kotak hitam, sehingga dapat diisi secara unik. Semua 2×kpersegi panjang memiliki beberapa solusi. Untuk 3×kpersegi panjang, ada beberapa solusi untuk kantara 3 dan 14, tetapi ada satu solusi tepat untuk k=15.

Saya kemudian memasukkan 4 persegi panjang tersebut di grid. Ini berarti bahwa setiap kata muncul 4 kali dalam solusi, yang biasanya disukai dalam konstruksi teka-teki silang, tetapi OK untuk tantangan ini. Di sisi lain, solusi ini memiliki simetri kiri / kanan dan atas / bawah!

Kotak yang dapat dibaca komputer:

HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES

Berikut adalah kode R yang saya gunakan untuk menemukan semua solusi untuk ukuran kotak yang diberikan. Melilit semua tiga kali lipat kata-kata 15 huruf terlalu lambat. Sebagai gantinya, saya mencoba mengisi dengan persegi panjang

  • mengatur dua kolom pertama (dua kata 3 huruf)
  • kemudian mengulang semua kata 15-huruf dimulai dengan dua huruf pertama yang sekarang diselesaikan.
  • untuk setiap pilihan kata 15-huruf, saya kemudian memverifikasi apakah semua kata 3-huruf yang dihasilkan ada dalam kamus.

Sebagai contoh, untuk solusi akhirnya, kode yang pertama dimasukkan ke dalam HOPdan EVO, kemudian menyelesaikan dalam HETERNORMATIVE, OVEROPINIONATEDdan POSSESSEDNESSES, dan akhirnya diverifikasi semua kata 3 huruf ( HOP, EVO, TES, ERS, ROE, OPS, NIS, ONE, RID, MON, ANE, TAS, ITS, VEE, EDS).

Kode r

library(fastmatch)
f = "scrabble-wordlist.txt"
d = read.table(f, skip=2, as.is=T, na.strings=NULL)

d$l = apply(d, 2, nchar)
d3 = d[d$l==3, 1]

sp = function(s) strsplit(s, "")[[1]]
cm = function(v) paste0(v, collapse="")
d3s = sapply(d3, sp)

f3 = function(l){
  m = matrix("", 3, l)

  md = sapply(d[d$l == l, 1], sp)
  nf = 0

  a1 = seq(1, 3*l, by=3); a2 = a1 + 1; a3 = a1 + 2

  for(i in 1:ncol(d3s)){
    m[, 1] = d3s[, i]

    id1 = as.matrix(md[, md[1, ] == m[1, 1]])
    id2 = as.matrix(md[, md[1, ] == m[2, 1]])
    id3 = as.matrix(md[, md[1, ] == m[3, 1]])

    if(any(ncol(id1) == 0, ncol(id2) == 0, ncol(id3) == 0)) next

    for(j in 1:ncol(d3s)){
      m[, 2] = d3s[, j]

      jd1 = as.matrix(id1[, id1[2, ] == m[1, 2]])
      jd2 = as.matrix(id2[, id2[2, ] == m[2, 2]])
      jd3 = as.matrix(id3[, id3[2, ] == m[3, 2]])

      if(any(ncol(jd1) == 0, ncol(jd2) == 0, ncol(jd3) == 0)) next

      for(k1 in 1:ncol(jd1)){
        m[1, ] = jd1[, k1]

        for(k2 in 1:ncol(jd2)){
          m[2, ] = jd2[, k2]

          for(k3 in 1:ncol(jd3)){
            m[3, ] = jd3[, k3]

            w = paste0(m[a1], m[a2], m[a3])
            if(all(w %fin% d3)){
              nf = nf + 1
              print(m)
            }
            if(nf >= 2){
              print(c(l, nf))
              return()
            }
          }
        }
      }
    }
  }

  return(nf)
}

Disebut sebagai f3(15). Butuh beberapa jam di komputer pribadi saya.

Robin Ryder
sumber
@ downvoter Bisakah Anda berkomentar?
Robin Ryder
Jawaban saya juga diturunkan. 🤷
A. Rex
1

182 kotak putih

Empat wilayah 3x15 dihubungkan oleh beberapa kotak putih.

Terinspirasi oleh jawaban Robin Ryder , saya mencoba memeras beberapa kotak putih lagi. Saya yakin solusi ini unik, dan saya akan segera mengirimkan kode verifikasi yang sesuai.

Kotak yang dapat dibaca komputer:

HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
B##############
INCOMMUNICATIVE
NEUROANATOMICAL
DETERMINATENESS
###############
HETERONORMATIVE
OVEROPINIONATED
POSSESSEDNESSES
B##############
INCOMMUNICATIVE
NEUROANATOMICAL
DETERMINATENESS
A. Rex
sumber
184 karena mon? Cot dapat diselesaikan secara unik dengan monocot
Jonathan Allan
... buat itu "mungkin ..." karena saya belum memverifikasi itu tidak akan merusak keunikan di papan!
Jonathan Allan
Saya ingin tahu melihat kode verifikasi Anda. Semua upaya saya untuk memverifikasi kisi Anda sangat lambat.
Robin Ryder