Apakah game buku puzzle klasik ini NP-complete?

Ada sebuah puzzle buku permainan klasik sangat mirip dengan teka-teki silang, kecuali daftar kata yang diberikan dan kemudian papan persegi terdiri dari unit kuadrat diberikan, dengan beberapa kotak dihitamkan seperti teka-teki silang, dan beberapa kotak memiliki surat yang sudah ditulis di dalamnya. Tujuannya adalah untuk menulis setiap kata dari daftar sekali dan hanya sekali dalam teka-teki, di mana setiap kata ditulis baik secara horizontal (kiri ke kanan) atau secara vertikal (atas ke bawah) ke dalam kotak yang tidak dihitamkan berturut-turut, dan ketika Anda menulis kata , kedua kotak yang mengapit ujung kata harus dihitamkan atau dihapus dari papan. Juga untuk surat-surat pra-ditulis ke dalam beberapa kotak, kata-kata yang ditulis yang tumpang tindih kotak-kotak ini harus menghormati surat pra-ditulis.$N \times N$

Sekarang, jika kita mengasumsikan alfabet ukuran tetap untuk kata-kata, memutuskan apakah kita dapat mengisi papan dengan solusi yang valid menggunakan persis setiap kata dalam daftar sekali dan hanya sekali masalah NP-lengkap, jika panjang sisi papan adalah tidak tetap?

Maaf telah menjawab pos lama.

Saya sudah memikirkannya dan saya pikir masalah dengan alfabet tetap adalah NP-complete juga.

Saya akan mengurangi 1-in-3 SAT positif untuk masalah kata ini

Kemarin saya mengalami masalah dengan ide untuk menyelesaikan masalah. Saya mengalami masalah dalam membuat setiap variabel berbeda hingga saya melihat kembali pertanyaannya dan saya menyadari bahwa Anda mengizinkan kotak dengan simbol yang ditanam. Ini menyederhanakan pengurangan banyak. Ide saya yang lain adalah memiliki kata-kata dengan panjang yang berbeda untuk setiap variabel yang berbeda.

PENGURANGAN

Sekarang saya akan menjelaskan gadget yang akan kita gunakan:

Gadget variabel

Kami memberi label pada setiap variabel dengan indeks numerik yang berbeda dan kami akan memiliki angka yang berbeda untuk setiap variabel. Kami memilih indeks terbesar dan kami mewakili angka dalam biner, kami akan memanggil rantai biner ini .$n$

Kemudian kita membuat dua kata vertikal berbeda untuk setiap variabel. Semua kata akan memiliki panjang (Hanya jika kami mengizinkan kata-kata rangkap dalam daftar kata), di mana | n | adalah panjang rantai biner n .$3 + |n|$$|n|$$n$

Misalnya, biarkan indeks terbesar menjadi nomor . Ketika kita mengubah angka ini dalam biner, kita mendapatkan rantai 100 dalam biner, rantai ini memiliki panjang tiga. Jadi setiap kata variabel akan memiliki panjang 6 dalam contoh ini.$4$$100$$6$

$3$$2$$n$$3$

$4$$3$

$4$$1$

$320013$$420014$

$1$$|n|$

Kita harus menyalin kata-kata ini berkali-kali, kita akan membutuhkan satu salinan dari setiap kata untuk setiap kemunculan variabel dalam instance SAT. Ini akan membuat duplikat dalam daftar kata. Kita bisa menghilangkan duplikat dengan menambahkan rantai biner lain ke rantai biner yang secara unik mengidentifikasi variabel. Rantai baru ini akan secara unik mengidentifikasi setiap arus suatu variabel.

Untuk melakukan itu, kita cukup menetapkan setiap arus variabel rantai biner lain dan kami menempatkan rantai itu di akhir representasi biner variabel.

$n_i$$i$$n_i$$|n_i|$$|n_i|$

Ini akan menghilangkan duplikat di dalam kata-kata variabel.

$x_2$

$32010013$ $42010014$$32010103$ $42010104$$32010113$ $42010114$

Gadget klausa

$6$

$535354$$535453$$545353$

$4$$3$$5$

$m$$m$$|m|$$|m|$. Kami menambahkan setiap rantai biner ke kata-kata klausa yang termasuk dalam klausa.

Sekarang, mari kita lihat gambar gadget klausa di papan tulis:

$(x_2 \lor x_3 \lor x_4)$$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

$4$

Jika kami tidak mengizinkan duplikat di dalam daftar kata, kami harus memodifikasi gambar.

$5b5b5b10$

$b201010b$$b201110b$$b21001b$

$b$

Lihat sebuah contoh:

Gadget konsistensi variabel

Ini adalah gadget yang memastikan bahwa pemain hanya dapat menetapkan nilai yang sama untuk semua kolom literal dari suatu variabel.

Kami akan memiliki gadget baru untuk setiap variabel

Kami akan membuat dua kata baru untuk setiap gadget.

$2 * k$$k$$x_2$$63$ $k$$64$ $k$

$x_2$

$6363$$6464$

Jika kita ingin menghindari kata-kata berulang, perhatikan bahwa setiap gadget konsistensi milik variabel yang berbeda. Jadi kita dapat menambahkan rantai biner yang mengidentifikasi setiap variabel ke dua kata yang kami buat untuk gadget ini.

Sekarang mari kita lihat contoh gambar gadget ini:

$x_2$$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

$3$$4$$3$$4$. Kita dapat menempatkan kata sisa dari gagdet ini di baris lain

Jika kami tidak mengizinkan duplikat dalam daftar kata, kata-kata di dalam gambar contoh akan:

Untuk baris:

$6b6b010$$6b6b010$

Untuk kolom:

$b201001b$$b201010b$

$b$

Lihat sebuah contoh:

Gadget tempat sampah

Ini adalah gadget yang dibuat untuk menempatkan kata-kata klausa yang tidak digunakan. Untuk melakukan itu, kita hanya perlu menempatkan dua baris untuk setiap kata klausa di bagian kosong dari papan. Baris-baris ini tidak terhubung ke baris atau kolom lainnya.

Dengan ini kami menyelesaikan pengurangan, karena kami mengklaim kami hanya perlu 6 simbol untuk pengurangan.

Contoh

Jika penjelasan sebelumnya membingungkan, berikut adalah contoh gambar instance positif 1 in 3 SAT yang telah direduksi menjadi masalah kata ini:

Jika kita melarang kata-kata berulang:

Contoh yang telah dikurangi adalah:

$(x_1 \lor x_2 \lor x_3) \land (x_2 \lor x_3 \lor x_4)$

Saya pikir pengurangan berikut dari Directed Hamiltonian path works:

$G=(V,E)$$s,t\in V$

$V\cup \{*\}$$*$$V$

$v*v$$v\in V$$vu$$(u,v)\in E$

$|V|$

$|E|-(|V|-1)$

$s*s$$t*t$

Sekarang, untuk mengisi tangga, hanya kata-kata simpul yang dapat diletakkan di dalam langkah-langkah, dan untuk menghubungkan dua simpul, kata tepi harus diletakkan di antara mereka, yang sesuai dengan tepi yang ada dalam grafik. Tepi yang tidak digunakan dapat diletakkan di bagian kedua papan. Arah kedua sepele.

Saya pikir ini bekerja (bukti kebenaran saya buat sketsa adalah melambaikan tangan yang terbaik, tapi tetap saja).