Kompleksitas permainan puzzle Net

8

Net (dikenal juga sebagai FreeNet, atau NetWalk) adalah permainan puzzle yang dimainkan di kotak dengan objek-objek berikut:n×n

  • ada komputer ; setiap komputer menempati satu sel dan memiliki satu kabel tautan;m
  • setiap komputer harus terhubung ke unit pusat yang menempati satu sel dan memiliki 1, 2 atau 3 kabel tautan;
  • sisa grid diisi dengan kabel (tidak ada sel kosong); sebuah sel kawat dapat dari tiga jenis: garis lurus, sudut, atau T-koneksi.

masukkan deskripsi gambar di sini

Tujuan permainan ini adalah untuk memutar setiap sel untuk menghubungkan semua komputer ke unit pusat tanpa membuat loop (yaitu konfigurasi akhir harus pohon) dan tanpa kabel dengan jalan buntu (daun dari konfigurasi akhir adalah komputer) .

* Apakah kompleksitas game ini telah dipelajari?
* Dan / atau apakah Anda melihat pengurangan cepat dari masalah NP-complete serupa yang diketahui?

Eric Goles dan Ivan Rapaport dalam " Kompleksitas masalah rotasi ubin " membuktikan bahwa masalah serupa adalah NP-lengkap tetapi mereka menggunakan 5 ubin (kita dapat mengasumsikan bahwa game Net menggunakan 4 ubin, karena kita dapat mengganti unit pusat dengan T- konektor tanpa mengubah struktur gim), dan dalam loop buktinya tidak dilarang.

cc.complexity-theory reference-request np-hardness puzzles Marzio De Biasi
sumber
Bagaimana cara mengganti unit pusat dengan konektor-T ketika unit pusat memiliki 4 kabel tautan yang tidak mengubah struktur game?
@ RickyDemer: Saya pikir bahwa unit pusat tidak berpengaruh, dan bahwa permainan "kesulitan" tidak berubah jika dibatasi hingga 3 tautan dan digantikan oleh T-wire (atau bahkan sudut). Namun unit sentral 4 tautan dapat disimulasikan menggunakan dua konektor T yang berdekatan, dan memundurkan level yang memperpanjang / mengisi kabel pada kolom yang ditambahkan. Saya akan mengubah pertanyaan dan membatasi tautan unit pusat ke 3.
Marzio De Biasi
Tampaknya bagi saya seolah-olah Anda mungkin dapat mengurangi jalur Hamiltonian planar ke masalah ini. Namun, itu akan membutuhkan banyak pembuatan gadget.
Peter Shor
@PeterShor: memang saya menemukan gadget yang memungkinkan untuk membangun game Net setara dengan grafik grid dengan derajat , dan yang memiliki solusi jika ada siklus Hamiltonian di grafik asli: tapi saya tidak memposting diri -menjawab belum karena saya masih memeriksanya dan saya mencoba mencari tahu apakah elemen lain dari permainan (sejenis kawat, atau bahkan terminal) dapat dibuang dan membuat permainan tetap sulit. Mungkin saya harus memposting gambar mereka. ≤3
Marzio De Biasi
Bagus! Tidak perlu terburu-buru; tunggu sampai Anda siap memposting jawaban.
Peter Shor

Jawaban:

3

Hanya sebagian jawaban sendiri: Saya pikir masalahnya adalah NP-lengkap.

16×16≤3

masukkan deskripsi gambar di sini

Gadget HARUS memiliki properti berikut (saya akan mencoba memeriksanya dengan pemecah kendala):

  • SEBUAHBC
  • dua kabel dari pasangan antarmuka harus diarahkan ke luar atau keduanya ke dalam (jika tidak ada kabel ujung terbuka atau siklus di bagian dalam gadget);
  • gadget harus dimasukkan / keluar tepat dua kali dan dari tepat dua pasangan antarmuka (zona hijau dari tiga angka pertama menunjukkan traverse AC, BC, AB);
  • tepat dua pasangan antarmuka harus diarahkan ke luar (zona merah pada gambar menunjukkan apa yang terjadi jika ketiga pasangan antarmuka semuanya diarahkan ke luar);

Gadget yang setara dengan node derajat 2 dan 1 serupa (dan kami juga dapat membuat gadget "isi" untuk mengisi lubang grafik kisi asli).

Sekarang menggantikan dua sel pusat dari satu gadget dengan unit pusat yang mengirimkan daya pada satu arah dan terminal di titik akhir lainnya, permainan HARUS memiliki solusi jika grafik asli memiliki siklus Hamiltonian.

Marzio De Biasi
sumber
btw apakah ini berfungsi untuk varian pada torus?
Suresh Venkat
@ SureshVenkat: varian pada torus tidak bisa lebih mudah, karena saya pikir ada pengurangan yang mudah dari versi normal: tambahkan perbatasan semua dibuat dengan terminal (seperti batas bawah gadget di atas); dengan cara ini sisi torus diisi dengan terminal yang tidak dapat memindahkan sinyal di antara mereka.
Marzio De Biasi
Saya sekarang kecanduan jaring :) - logicgamesonline.com/netwalk/?g=Expert - dan menemukan versi toroidal menjadi lebih sulit :)
Suresh Venkat
Saya ingin tahu bagaimana teka-teki NET dalam game terprogram yang sebenarnya dihasilkan. Apakah mereka dihasilkan sehingga dapat dipecahkan oleh semacam logika? Untuk memiliki solusi unik? (Mereka semua tampaknya memiliki solusi unik.)
Peter Shor
Ini dijawab pada SO . Teka-teki tidak dijamin memiliki solusi unik. Saya bertanya-tanya seberapa sering mereka tidak melakukannya.
Peter Shor