Apakah Hidoku NP lengkap?

Sebuah Hidoku adalah grid dengan beberapa bilangan bulat pra-diisi dari 1 sampai . Tujuannya adalah untuk menemukan jalur bilangan bulat berturut-turut (dari 1 hingga ) di grid. Lebih konkret, setiap sel grid harus mengandung bilangan bulat yang berbeda dari 1 ke dan setiap sel dengan nilai harus memiliki sel tetangga dengan nilai (juga bisa secara diagonal). $n \times n$ $n^2$ $n^2$ $n^2$ $z ≠ n^{2}$ $z + 1$

Apakah NP sulit untuk memutuskan apakah Hidoku yang diberikan dapat dipecahkan? Pengurangan apa yang bisa digunakan?

Sunting: sesuai dengan komentar, saya berikan sedikit klarifikasi. Diberikan adalah kisi sel, beberapa di antaranya sudah berisi nilai (bilangan bulat dari 1 hingga n²). Kita harus mengisi semua sel yang tersisa dengan bilangan bulat dari 1 hingga , sehingga tidak ada dua sel yang memiliki nilai yang sama dan bahwa setiap sel dengan nilai memiliki tetangga dengan nilai . Yaitu, setelah mengisi sel, kita harus menemukan jalur . Di kotak, yang secara logis mengunjungi setiap sel. $n^2$ $z ≠ n²$ $z + 1$ $1, 2, 3,\cdots, n^2$

Contoh dari Hidoku akan menjadi http://www.janko.at/Raetsel/Hidoku/018.c.gif . Hidoku yang sudah dipecahkan adalah http://diepresse.com/images/uploads/3/f/7/586743/spectrumsommerraetsel_7august_hidoku_schwer_loesung20100810172340.gif , di mana Anda dapat melihat jalur yang saya maksud.

complexity-theory reductions np-hard ipsec
sumber

Secara intuitif, tanpa banyak memikirkannya, kedengarannya polytime dapat dipecahkan pada pandangan pertama. Sesuatu seperti pemrograman dinamis pada nilai yang diizinkan (

) dan simpul (

). Kedengarannya bisa dipecahkan dalam waktu

1, \dots, n^{2}

$1, \dots, n^2$

v_{1}, \dots v_{n}

$v_1, \dots v_n$

O (n^{3})

$O(n^3)$

Pål GD

Ini dapat dimodelkan ekuivalen sebagai grafik, yang menghubungkan node dengan tepi jika mereka penerus di

. Kemudian, Anda mencari jalur Hamilton. Menurut jalur Hamilton dalam grafik grid oleh Itai et al. (1982) masalah ini adalah NP-complete dalam grafik grid. Ini tidak langsung cocok dengan masalah Anda karena Anda mengizinkan koneksi diagonal, tetapi pertanda buruk.

N

$\mathbb{N}$

Raphael

@ Raphael bukankah grafik yang dibangun adalah DAG?

Pål GD

Saya tidak melihat bagaimana ini DAG. Sejauh yang saya mengerti, input adalah grafik grid (tidak terarah) (mengandung juga tepi diagonal) dan tujuannya adalah untuk menemukan jalur Hamilton, di mana posisi beberapa node pada jalur diberikan.

George

@ George Okey, saya menafsirkan pertanyaan sebagai menemukan jalur maksimum peningkatan nilai dalam kotak!

Pål GD

Jawaban:

Saya pikir itu adalah -Lengkap: sebagai diperhatikan oleh Raphael, siklus Hamiltonian pada grafik kotak dengan lubang masalah adalah NP-lengkap ( Alon Itai, Christos Papadimitriou, Jayme Luiz Szwarcfiter: Hamilton Jalan di Grid Grafik SIAM J. Comput.. 11 (4): 676-686 (1982) ). $\sf{NP}$

Jadi, mengingat grafik kotak dengan lubang, Anda dapat dengan mudah membuat game Hidoku yang setara di mana sel-sel tetap awal mengisi semua diagonal genap; diagonal ganjil kosong membentuk grafik tidak berarah yang setara dengan grafik kotak asli dan Hidoku memiliki solusi jika dan hanya jika grafik kotak asli memiliki jalur Hamilton. $G$ $G$

masukkan deskripsi gambar di sini

Gambar 1: grafik kotak dengan lubang dan ekuivalennya Hidoku puzzle (sel biru mewakili sel bernomor awal tetap ( adalah yang pertama, adalah yang terakhir), sel putih adalah sel yang harus diisi pemain, garis ungu menunjukkan urutan sel bernomor awal tetap). $12 \times 12$ $1$ $144$

Garis bantu (diisi) dapat ditambahkan ke bagian bawah atau kanan untuk menjadikannya persegi.

Contoh lain pengurangan dari grafik kisi ke teka-teki Hidoku: grafik kisi 6x4 tertanam dalam kisi 13x13 yang lebih besar; diagonal genap diisi dengan angka tetap, dan sel bebas yang tersisa setara dengan grafik kisi asli.

masukkan deskripsi gambar di sini

Gambar lengkap dengan transformasi dapat diunduh di sini .

Beberapa catatan tambahan untuk melengkapi jawabannya:

masalahnya juga dikenal sebagai Hidato ; dewan dapat memiliki bentuk yang sewenang-wenang (tetapi sebagai generalisasi dari kotak kuadrat, itu tetap NP-keras);
$n \times n$
Saya pikir aturan asli permainan mengatakan bahwa solusinya harus unik ; jadi masalahnya adalah di AS (AS-keras), dan tidak mungkin di NP.

$n^2$ $\sf{NP}$

Vor
sumber

Bukankah ini DAG? Sudahkah saya salah memahami pertanyaan?

Pål GD

@ PålGD: tidak, saya tidak berpikir itu adalah DAG, ini adalah grafik kotak tidak terarah dengan tepi diagonal. Permainan dimulai dengan papan yang terisi sebagian dan pemain harus mulai dari sel 1 dan mencapai yang terakhir membuat langkah ortogonal atau diagonal (tapi mungkin saya tidak mengingat aturan dengan sangat baik ... sekarang saya memeriksanya)

Vor

Tetapi dikatakan "menemukan jalan bilangan bulat berturut-turut".

Pål GD

Mungkin itu hanya berarti bahwa ia tidak dapat mengunjungi sel yang sama dua kali, dan bahwa semua sel harus dikunjungi

Vor

1

$1$

n^{2}

$n^2$

$n\times n$ $\Omega(n)$ $n$ $\lg n$ $(x_i, y_i, w_i): x_i, y_i\leq n, w_i\leq n^2$ $(x_i, y_i)$ $w_i$ $\lg n + \lg n + \lg n^2 = 4\lg n\in O(\lg n)$ $\Omega(n)$ $o(n)$

$\Omega(n)$

(Untuk diskusi tentang masalah serupa, lihat pertanyaan saya beberapa waktu lalu tentang kompleksitas Nurikabe yang ringkas di situs cstheory.SE.)

Steven Stadnicki
sumber

Tidak menentukan ukuran papan di unary menurut saya sebagai interpretasi yang tidak masuk akal.

David Eisenstat

@ DavidVenstat Itu belum tentu interpretasi alami , tetapi sepertinya yang sempurna bagi saya.

Steven Stadnicki

@StevenStadnicki: Saya setuju dengan Anda, saya membuat catatan serupa dalam bukti NP-kelengkapan Binary Puzzle yang baru-baru ini saya posting di cstheory.stackexchange.com. Padahal representasi non-unary memang tidak begitu masuk akal :-). Saya akan menambahkan catatan pada jawaban saya. Dan saya harus mengatasi masalah keunikan solusi juga; karena saya pikir aturan aslinya mengatakan bahwa solusinya harus unik.

Vor