Di HabrƩ ada beberapa artikel tentang generasi teka-teki silang. Dalam salah satu dari mereka,
"Teka-teki Silang Paling Kompleks Disusun oleh Komputer", dikatakan tentang teka-teki silang yang sangat rumit yang dibuat oleh komputer, yang "harus sedikit membantu" secara manual. Artikel kedua,
"Crossword Puzzle Generation Algorithm," berbicara tentang algoritma yang dibuat oleh penulis untuk menyusun teka-teki silang, dan mencatat bahwa "teka-teki silang paling sulit" ini tetap tidak terkalahkan dan mengatakan bahwa "mungkin puncak yang tidak ditaklukkan ini akan menginspirasi seseorang untuk mengambil badai lagi!" Nah, Anda bisa menerima tantangan itu. Apa yang terjadi, lihat di bawah luka.
Pada awalnya saya akan memberikan teka-teki silang yang paling rumit ini:
Hal pertama yang perlu Anda temukan adalah daftar kata-kata yang digunakan dalam menyusun teka-teki silang ini. Karena itu daftar tersebut diambil dua file dari artikel di atas - satu file dengan kata-kata Rusia, satu file dengan bahasa Inggris. Maka perlu untuk memecahkan pertanyaan utama - algoritma mana yang digunakan untuk menyusun teka-teki silang ini. Sebenarnya, teka-teki silang ini tidak "rumit" oleh jumlah kata, tetapi oleh jumlah persimpangannya. Jelas bahwa serangan brute-force tidak cocok di sini, karena akan terlalu banyak waktu untuk memilah-milah semua opsi. Dalam artikel tersebut, banyak heuristik dianggap mempercepat proses pencarian, namun teka-teki silang ini tidak pernah dikompilasi dalam versi Rusia atau Inggris. Anda dapat terus menghasilkan heuristik lain untuk mempercepat solusinya, tetapi kebanyakan dari mereka telah ditemukan dan diimplementasikan dalam solver SAT. Oleh karena itu, Anda dapat menerjemahkan tugas ke dalam bentuk yang dapat dimengerti oleh pemecah SAT dan menggunakan salah satunya.
Apa solver SAT dan informasi apa yang diharapkannya pada input, saya pertimbangkan dalam artikel
"Memecahkan masalah ubin dengan bantuan solver SAT menggunakan contoh pentamino" . Dalam hal membuat teka-teki silang, diperlukan pendekatan yang sedikit berbeda untuk merumuskan masalah dalam bentuk konjungtif yang normal, yang sekarang akan saya uraikan.
Hal pertama yang harus dilakukan adalah mengurutkan semua kata dalam daftar menjadi grup. Setiap grup akan berisi kata-kata dengan panjang yang sama. Jelas, untuk setiap kata dalam kisi teka-teki silang, Anda dapat memilih kata dari grup dengan panjang yang sesuai. Kami mengaitkan setiap kata dari grup yang dapat ditulis dalam satu kata dari kisi dengan variabel Boolean. Variabel ini akan benar jika kata yang diberikan dari grup ditulis dalam kata ini dari grid dan false jika tidak.
Sekarang mari kita buat formula yang menggambarkan masalah kita, yaitu, kita akan benar-benar memberlakukan batasan pada variabel kita. Temukan semua persimpangan kata secara vertikal dengan kata-kata secara horizontal. Untuk setiap persimpangan, kami menentukan pasangan kata mana yang digabungkan satu sama lain dan yang tidak. Namun, masalah muncul di sini, karena jumlah pasangan tersebut dapat melebihi satu juta untuk satu persimpangan. Karena itu, kami akan menggunakan pendekatan yang berbeda. Kami mengurutkan kata-kata dalam grup yang sesuai dengan kata secara horizontal dengan huruf, yang berdiri di persimpangan dua kata ini. Lakukan hal yang sama untuk kata secara vertikal. Rupanya, kata-kata yang cocok akan memiliki huruf yang sama di persimpangan. Kami memperkenalkan variabel tambahan untuk setiap huruf yang muncul dalam setidaknya satu kata secara horizontal dan vertikal. Sekarang syarat bahwa kedua kata tersebut digabungkan satu sama lain adalah bahwa setidaknya satu variabel seperti itu benar. Dengan demikian, untuk setiap persimpangan, satu klausa akan ditambahkan yang terdiri dari variabel yang sesuai dengan huruf. Sekarang Anda perlu mengaitkan variabel yang sesuai dengan huruf tertentu dengan kata-kata yang mengandung huruf ini di posisi persimpangan kata-kata. Ini dilakukan oleh seperangkat klausa yang menjamin bahwa dua variabel Boolean akan memiliki nilai yang sama. Dan akhirnya, Anda perlu memastikan bahwa tidak ada kata yang identik dalam teka-teki silang. Untuk melakukan ini, untuk setiap kata dari database kami menambahkan klausa formulir (bukan x_i V bukan x_j), di mana x_i adalah variabel yang sesuai dengan instance-nya dalam satu kata dari kisi teka-teki silang, dan x_j adalah variabel yang sesuai dengan instance di kata lain dari kisi teka-teki silang.
Menghasilkan "teka-teki silang paling rumit" ini menggunakan kata-kata Rusia membutuhkan waktu beberapa menit pada Intel 2600K 3,5 GHz dengan memori 16 gigabytes. Membuat teka-teki silang menggunakan kata-kata bahasa Inggris membutuhkan waktu sekitar dua puluh menit.
Setelah itu, saya mencoba teka-teki silang lainnya. Sebagai contoh, saya berhasil menyusun teka-teki silang kata-kata bahasa Inggris dan Rusia dalam bentuk persegi 6 dengan 6, di mana semua kata berpotongan.
Selanjutnya, saya berikan teka-teki silang yang dihasilkan. Mereka yang berharap dapat menyelesaikannya.
Opsi dengan kata-kata Rusia:1 Horizontal Pesawat gerak lambat dengan hidung melotot
6 Alat Musik Senar Jepang Horizontal
10 Horisontal Dalam mitologi Skandinavia, raksasa yang muncul dari kekacauan prematur dunia jurang
14 Pengasingan Horisontal genus
15 Mineral Horisontal
16 Penyair Ceko Horisontal (20 c.)
17 Pulau Horisontal di Teluk Guinea (Guinea Ekuatorial)
18 Mulut Horisontal, bibir (ketinggalan jaman)
19 Kebencian Horisontal, Kemarahan
20 Horisontal Hanya satu partai politik yang hadir
23 Sungai Horizontal terbesar di Irlandia
24 Pakaian Ulama Horisontal
25 Sungai Horisontal di Angola dan Zaire, meninggalkan anak sungai dari Sungai Kwango
27 Merek Horizontal bus Hungaria
32 Kota Horisontal dan pelabuhan di DPRK
35 Horisontal Ibu mertua atau ibu mertua
37 tanaman Solanaceae Horisontal
38 Horisontal Seseorang yang terlibat dalam carding wool
41 Horizontal Female Name (Bahasa Yunani baik, baik)
42 Satelit buatan Kanada horisontal
43 Karakter Horisontal dari opera Weber '' Shooter Gratis ''
44 Horizontal City di Slovakia
46 Pengeluaran Horizontal
48 Ikan budidaya Horizontal dari keluarga ikan mas
50 Horisontal Dalam mitologi Jepang, dewa banyak telinga padi
54 Fosfor kristal anorganik horizontal
59 Horisontal Nabi Iran, pendiri Manichaeisme (3 c.)
60 Rumah Petani Horisontal di Kepulauan Hindia Barat
61 Jenis anjing Gembala Horisontal (mirip dengan rubah)
62 Horisontal (trans.) Orang bodoh yang keras kepala dan bodoh
63 Horizontal City di wilayah Orenburg di sungai Ural
64 Horisontal Dalam mitologi Yunani, seorang pemburu raksasa dibunuh oleh Artemis
65 Horisontal penyanyi dan penyair Chili
66 Horisontal Karakter teater rakyat India, gambar seorang playman yang hancur, parasit dengan pelindung yang kaya
67 Chechen Horizontal dan tanah induk Ingush
1 Nama Panggilan Vertikal dari salah satu pemimpin pemberontakan populer 1413 di Paris
2 Perasaan Tidak Puas Vertikal
3 Ahli paleontologi Jerman Vertikal (1800-1862)
4 Vertikal Penaklukan wilayah yang direbut oleh bangsa Moor oleh penduduk asli Semenanjung Iberia
5 Master gitar Rusia Vertikal
6 Pemimpin militer Swedia dan Rusia Vertikal, jenderal, rekan Peter I (1667-1717)
7 Vertical Musician memainkan alat musik
8 Speaker Vertikal, Pria Eloquent
9 Vertical Ridge di Jepang, Pulau Honshu
10 Alat musik perkusi vertikal Korea, drum segi delapan
11 Vertical Latvian Conductor (1917-1967)
12 Keramahtamahan Vertikal, Musang
13 Vertikal Dalam mitologi Slavik, roh, perwujudan kematian
21 Genre Animasi Vertikal yang berasal dari Jepang
22 Katoda lampu pemanas ulir vertikal
26 Danau Vertikal di Daerah Arkhangelsk
28 Sungai Vertikal di Spanyol
29 Vertikal Hutan kecil pohon gugur
30 Item Langka Vertikal
31 Windmaster Belgia Vertikal, penemu saksofon
32 Bingkai Kecil Vertikal
33 Vertikal Hitam
34 Vertikal Ukuran lama berat farmasi = 62,21 mg
36 Provinsi Vertikal di Arab Saudi
39 Pelumas Anti-Gesekan Vertikal
40 Dekorasi pahatan vertikal ibu kota, cornice, dll. Dalam bentuk batang dan daun bergaya tanaman
45 Penulis Rusia Vertikal, penyair, penulis naskah film, penulis naskah untuk film A. Sokurov ('' Moloch '', '' Taurus '')
47 Karet Polisulfida Vertikal, sejenis karet sintetis
49 Vertical English Pathologist (Hadiah Nobel 1945)
51 Vertikal Dalam mitologi Muslim, jin dengan kekuatan khusus
52 Vertical Goose Cry
53 Nama Wanita Vertikal (nama Yunani dari dewi hidup damai; damai)
54 Grandmaster Catur Vertikal
55 Vertikal Kelompok manusia yang terbentuk secara historis, disatukan oleh asal yang sama
56 Vertikal Hibrida dari melintasi unta berpunuk tunggal (Dromedar) dengan dua berpunuk (Bactrian), Nar
57 Nilai Mekanikal Vertikal menyebabkan akselerasi
58 Penulis Jepang Vertikal (1909-1989, `` Catatan tahanan '', `` Lampu di lapangan '', `` Battle on Leyte '')
Opsi dengan kata-kata bahasa Inggris:1 Horizontal Tempat yang menarik banyak pengunjung
6 Horisontal Salah satu dari sejumlah ikan dari keluarga Carangidae
10 Horisontal Kumpulan fakta yang dapat ditarik kesimpulannya
14 Horisontal Nintu)
15 Penutup tubuh mendatar hewan yang hidup
16 Horisontal Rasa sakit yang persisten (biasanya sedang)
17 Horizontal Respons jaringan tubuh terhadap cedera atau iritasi
18 Tipe Horizontal genus bebek air tawar Anatidae
19 Horisontal Dinasti yang menguasai sebagian besar Manchuria dan Cina timur laut dari 947 hingga 1125
20 Horisontal Senyawa kristal putih digunakan sebagai analgesik dan juga sebagai antipiretik
23 Horisontal Sebuah kota di Tanzania tengah
24 Dewa Kematian Horisontal
25 Bentuk horisontal dan adonan kering terbuat dari tepung dan air dan kadang-kadang telur
27 Horizontal Seorang anggota masyarakat Siouan di Virginia dan North Carolina
32 Horisontal Keinginan kuat yang gelisah
35 Prelatus Afrika Selatan horisontal dan pemimpin perjuangan antiapartheid (lahir tahun 1931)
37 Horisontal Dokumen komersial yang digunakan untuk meminta seseorang memberikan sesuatu sebagai imbalan untuk pembayaran
38 Pengusir hulu Menggigit Horizontal
41 Horisontal Sebuah kota kuno di Portugal utara
42 Horisontal Sebuah gubuk Eskimo
43 Mekanisme Rotasi Horisontal dalam bentuk roda pemintalan yang dipasang secara universal yang menawarkan ketahanan terhadap belokan ke segala arah
44 Horisontal Ibukota Bahrain
46 Horizontal Tindakan memberi warna terang pada rambut
48 Tipe Horizontal genus Majidae
50 Horisontal Salah satu dari beberapa tanaman dari genus Camassia
54 gurnard Terbang Horisontal
59 Horisontal Seluruh tanaman dapat dipanen sekaligus
60 Horisontal Sebuah undang-undang yang disahkan oleh Kongres AS untuk mencegah karyawan dari cedera atau tertular penyakit dalam pekerjaan mereka
61 Horisontal Blok besi atau baja berat tempat logam panas dibentuk oleh palu
62 Negarawan Inggris Horisontal yang menentang perceraian Henry VIII dari Catherine dari Aragon dan dipenjara dan dipenggal
63 Horisontal Pria yang merayu seorang wanita
64 Pemain baseball Horizontal Amerika Serikat
65 Horizontal Tampilan rahasia
66 Horizontal Camar ramping kecil yang memiliki sayap sempit dan ekor bercabang
67 Horizontal Dikenal karena anggur dan zaitun dan minyak zaitun
1 Pemimpin revolusioner Prancis Vertikal (lahir di Swiss) yang merupakan pemimpin dalam menggulingkan kaum Girondis dan ditikam hingga mati di pemandiannya oleh Charlotte Corday (1743-1793)
2 Vertikal Tahunan untuk jamu abadi di wilayah Mediterania
3 Vertikal Tropis tenggara pohon anggur shrubby yang mengandung buah berry seperti pedas
4 Ani Vertikal
5 Vertical Cahaya pertama hari ini
6 Judul Vertikal untuk mantan raja keturunan Iran
7 Vertical Seorang fotografer yang mengoperasikan kamera film
8 Vertikal Sebuah kota di Turki selatan di Sungai Seyhan
9 Vertikal Suatu daerah gersang dengan sedikit atau tidak ada vegetasi
10 Pelukis Spanyol Vertikal Surrealis (1904-1989)
11 Vertikal Setiap dari berbagai senyawa yang larut dalam air yang memiliki rasa asam dan mampu mengubah merah lakmus dan bereaksi dengan basa membentuk garam
12 Vertikal Berasal atau penduduk Thailand
13 Vertikal (dalam Gnostisisme) kekuatan ilahi atau sifat yang berasal dari Yang Mahatinggi dan memainkan berbagai peran dalam operasi alam semesta
21 Vertikal Gunung berapi aktif di Kolombia tenggara di Andes
22 Vertikal Sebuah lepton dengan massa yang sangat besar
26 Vertikal Seorang anggota masyarakat Indian Amerika Selatan yang tinggal di Brasil dan Paraguay
28 Vertikal Saraf sensorik utama wajah dan saraf motorik untuk otot pengunyahan
29 Vertikal Sebuah pusaran air miniatur atau angin puyuh yang dihasilkan ketika arus fluida naik dua kali lipat dengan sendirinya
30 artis dan penulis Vertikal Inggris ayat nonsense (1812-1888)
31 Kue Cokelat Vertikal dengan isian krim putih
32 Vertikal Sebuah rudal balistik yang mampu melakukan perjalanan dari satu benua ke benua lain
33 Vertikal Bahasa Chadic tiga-nada
34 Vertikal Unit kapasitas yang digunakan untuk mengukur herring segar
36 Vertikal Besar Hibrida berair besar antara jeruk keprok dan jeruk bali memiliki kulit keriput yang tebal
39 Kain wol atau wol dan kapas dari tenunan polos (sering berlapis kaca) yang digunakan sebelumnya untuk lapisan dan pakaian serta gorden
40 Vertikal Satu unit berat apotek sama dengan 480 butir atau satu per dua belas pon
45 Vertikal Sebuah kota di Belgia tengah
47 Vertical Selendang panjang berwarna cerah
49 Vertikal Sebuah buku dalam Perjanjian Lama yang menggambarkan bagaimana Yosua memimpin orang Israel ke Kanaan (Tanah Perjanjian) setelah kematian Musa
51 Vertikal Obat antiinflamasi nonsteroid (nama dagang Advil dan Motrin dan Nuprin) digunakan untuk meredakan nyeri artritis dan sebagai analgesik dan antipiretik.
52 Kijang vertikal mirip Kambing dari pusat Eurasia memiliki hidung pendek seperti belalai
53 Pemain tenis Vertikal Amerika Serikat (lahir di Yugoslavia pada tahun 1973)
54 Vertikal Sedikit basah
55 Vertikal Tanaman sukulen memiliki mawar daun biasanya dengan serat seperti rami dan paku bunga mencolok
56 Aktivitas Vertikal terlibat dalam menjaga sesuatu agar tetap berfungsi dengan baik
57 Vertikal (Afrika Selatan) perjalanan dengan gerobak sapi (terutama migrasi terorganisir oleh sekelompok pemukim)
58 Vertikal Danau gunung (terutama yang dibentuk oleh gletser)
Teka-teki silang 6 pada 6 dalam bahasa Rusia:1 uji coba Soviet Horisontal, Pahlawan Uni Soviet, salah satu peserta dari penerbangan non-stop Moskow - Kutub Utara - Vancouver
2 Telinga Horisontal
3 Diviner Horisontal
4 Kota Horisontal di Italia di pulau Sisilia
5 Benang bertekstur Horizontal Melengkung diperoleh dengan bergelombang di ruang panas
6 pembuat film Perancis Horisontal, penulis skenario ('' Bad Blood '', '' Boyfriend Meets Girl '')
7 Koin Perak Vertikal Grand Duchy of Lithuania abad ke-16
8 Ahli biokimia Amerika Vertikal, pertama kali mensintesis gen tRNA (Hadiah Nobel 1968)
9 Vertical City di Federasi Rusia, Ossetia Utara, di Sungai Ardon, di Jalan Ossetia Militer
10 Vertikal Horizontal niche di dinding kamar pemakaman, di mana almarhum diletakkan dan digantung atau digantung dengan kanopi
11 Vertikal Paha bangkai
12 Vertical City di tenggara Perancis
Crossword 6 on 6 dalam bahasa Inggris:1 Horisontal Seorang anggota masyarakat India di California utara dan Oregon selatan
2 Horisontal Anggota dari salah satu dari empat divisi dari Yunani prasejarah
3 Horizontal Dapat menjadi adiktif
4 Dewa cahaya Yunani Horisontal
5 Horisontal Barang pribadi atau pakaian atau menjahit kecil
6 Pohon kayu Horisontal yang Berharga di Selandia Baru menghasilkan kayu kemerahan keras yang digunakan untuk perabotan, jembatan, dan dermaga
7 Vertikal Garis lurus yang memotong kurva pada dua titik atau lebih
8 Vertikal Salah satu dari beberapa burung Dunia Lama jambul dengan paruh melengkung yang ramping
9 Novelis Vertikal Amerika terkenal karena buku anak-anak (1832-1888)
10 bluebirds Vertikal Amerika Utara
11 Vertikal Seseorang yang pekerjaannya membuat dan mengubah pakaian
12 Genus Tipe Vertikal Annonaceae
Kesimpulan
Penggunaan pemecah SAT meningkatkan kompleksitas teka-teki silang yang dapat dihasilkan. Seperti pada artikel sebelumnya, saya ingin menanyakan puncak yang tidak terbantahkan berikutnya - untuk membuat teka-teki silang kata-kata Rusia atau Inggris dalam bentuk kotak 7 oleh 7. Siapa yang akan menerima tantangan?