Apakah masalah N Queens NP-hard?

Masalah N-queen adalah ini:

Input: N

Keluaran: Penempatan N "ratu" pada papan catur NXN sehingga tidak ada dua ratu yang berada di baris, kolom, atau diagonal yang sama.

Melakukan pencarian google pada ini, saya menemukan bahwa banyak slide oleh banyak profesor mengklaim ini adalah masalah NP-Hard. (Mis. Web.mst.edu/~ercal/387/slides/NP-Hard.ppt)

Namun saya belum dapat menemukan bukti (atau mendapatkan satu). Alasan saya mengajukan pertanyaan ini adalah karena saya pikir saya memiliki algoritma yang memecahkan contoh masalah tertentu yaitu dengan N bukan kelipatan 2 atau 3 (N adalah jumlah ratu) Masalah Terkait - Dapatkah kita menganggap ukuran input sebagai N (di mana N adalah jumlah ratu)? Atau apakah kita mengambil ukuran input menjadi log (N), karena angka 'N' dapat direpresentasikan dalam bit log (N)?

cc.complexity-theory np-hardness csp Anshul Singhle
sumber

(1) Mengapa Anda menggunakan N dan n? Apakah mereka variabel yang sama atau variabel yang berbeda? (2) Untuk setiap bilangan bulat n kecuali untuk 2 dan 3, ada cara untuk meletakkan n ratu di papan n × n memenuhi kondisi n-ratu (lihat Wikipedia ), jadi saya tidak tahu masalah apa yang Anda bicarakan saat Anda mengatakan "ini adalah masalah NP-keras."

Tsuyoshi Ito

Saya ingat ada hasil kekerasan ketika papan tidak harus persegi: yaitu, bentuk papan diberikan sebagai bagian dari input.

Sasho Nikolov

n \times n

$n \times n$

n

$n$

Mungkin menghitung solusi adalah masalah yang sedikit lebih menarik (di luar kelas #P sebagaimana dibuktikan dalam "Pada kesulitan menghitung masalah pemetaan lengkap").

Marzio De Biasi

Lihat juga: dl.acm.org/citation.cfm?id=122322

Jeffε

Jawaban:

Seperti yang dinyatakan, jawaban untuk pertanyaan ini adalah TIDAK.

Referensi: Algoritma waktu polinomial http://dl.acm.org/citation.cfm?id=101343 [courtesy: vzn]

Teknik lain yang jauh lebih sederhana: http://dl.acm.org/citation.cfm?id=122322 [courtesy: Jeffe]

Anshul Singhle
sumber

Anda mungkin mempertimbangkan menerima jawaban ini sehingga tidak terus muncul kembali sebagai tidak dijawab.

Suresh Venkat

Algoritma polinomial-waktu dalam referensi pertama tidak dijamin untuk menghasilkan solusi. Apakah algoritme berhasil atau tidak tergantung pada konfigurasi awal, yang dipilih secara acak, dan penulis hanya memberikan bukti empiris bahwa tampaknya akan mengambil sejumlah uji coba polinomial hingga berhasil.

Tsuyoshi Ito

Referensi kedua juga bukan bukti. Hanya karena satu solusi yang layak untuk n-queens dengan n = 500000 ditemukan, tidak berarti itu ada dalam P. (Itu hanya membuatnya lebih mungkin)

Geoffrey De Smet

Sebenarnya, ini baru terbukti.

https://blogs.cs.st-andrews.ac.uk/csblog/2017/08/31/n-queens-completion-is-np-complete/ ]

Kasper
sumber

N

$N$

@ClementC. Sebenarnya, karena pertanyaan awal tidak cukup tepat, saya pikir Kasper ada benarnya bahkan jika caranya menyatakannya mungkin tidak lengkap. Memutuskan, mengingat n, jika ada penempatan jelas dalam P karena masalah selalu memiliki solusi untuk n> 3. Dengan demikian, masalah penyelesaian n-queens (memutuskan apakah seseorang dapat memperluas solusi parsial tertentu) tampaknya masalah keputusan alami untuk melihat untuk memahami kompleksitas masalah.

Serigala

@ holf Itu memang poin yang Anda buat, tapi satu yang tidak disebutkan oleh jawaban ini (dan bahwa pembaca sama sekali tidak akan mendapatkannya dengan membacanya). Memiliki jawaban yang menyesatkan untuk pertanyaan yang ambigu tidak sepenuhnya optimal.

Clement C.